𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An improved √N algorithm for mutual exclusion in decentralized systems

✍ Scribed by Takeshi Fuchi

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
684 KB
Volume
24
Category
Article
ISSN
0882-1666

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An algorithm is proposed which realizes mutual exclusion in a computer network system where communications are conducted by messages only without using a shared memory. With this method, and by transferring a token representing the exclusion the exclusion right, the mutual exclusion is realized.

A node wanting to execute a critical section first sends messages requesting exclusion to a set of nodes (members) assigned to it. The members keep this message, after receiving a finish exclusion message from some other node, transfer the exclusion request messages to the sender. The node receiving the token processes the critical section, and when finished, sends finish exclusion messages to the members. The members return information on nodes requesting exclusion known to them. According to this information, the next receiver of the token is determined. By contriving the selection of members and gathering information on nodes requesting exclusion, the mutual exclusion can be realized using √N + 1 or more but less than or equal to 3√N + 1 messages.

📜 SIMILAR VOLUMES

An Improved Algorithm for Module Allocat
An Improved Algorithm for Module Allocation in Distributed Computing Systems
✍ Ajith Tom P.; C. Siva Ram Murthy 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 159 KB

We consider the problem of finding an optimal and sub-optimal allocation of program modules onto processors of a distributed computing system. A module causes two types of cost to be incurred at the processor to which it is allocated-an execution cost for processing the module, and a communication c