Kerry Raymond
Abstract
We present an algorithm for distributed mutual exclusion in a computer network of N nodes that communicate by messages rather than shared memory. The algorithm uses a spanning tree of the computer network, and the number of messages exchanged per critical section depends on the topology of this tree. However, typically the number of messages exchanged is O(log N) under light demand, and reduces to approximately four messages under saturated demand.
Each node holds information only about its immediate neighbors in the spanning tree rather than information about all nodes, and failed nodes can recover necessary information from their neighbors. The algorithm does not require sequence numbers as it operates correctly despite message overtaking.
- 1 LAMPORT, L. Time, clocks, and the ordering of events in a distributed system. Comrnun. ACM 21, 7 (July 1978), 558-565. Google Scholar
- 2 MAEKAWA, M. A 4~ algorithm for mutual exclusion in decentralized systems. ACM Trans. Comput. Syst. 3, 2 (May 1985), 145-159. Google Scholar
- 3 RICART, G., AND AGRAWALA, A.K. An optimal algorithm for mutual exclusion in computer networks. Commun. ACM 24, 1 (Jan. 1981), 9-17. Google Scholar
- 4 SuzuKI, I., AND KASAMI, T. A distributed mutual exclusion algorithm. A CM Trans. Comput. Syst. 3, 4 (Nov. 1985), 344-49. Google Scholar
Index Terms
- A tree-based algorithm for distributed mutual exclusion
Recommendations
A distributed mutual exclusion algorithm
A distributed algorithm is presented that realizes mutual exclusion among N nodes in a computer network. The algorithm requires at most N message exchanges for one mutual exclusion invocation. Accordingly, the delay to invoke mutual exclusion is smaller ...
A Fair Distributed Mutual Exclusion Algorithm
This paper presents a fair decentralized mutual exclusion algorithm for distributed systems in which processes communicate by asynchronous message passing. The algorithm requires between $N-1$ and $2(N-1)$ messages per critical section access, where $N$ ...
Distributed mutual exclusion on hypercubes
Hypercube have been commercially available in the past few years to their high degree of connectivity, symmetry, and low degree of diameter. In this paper, we analyse the performance in number of messages on d-dimensional hypercube, for two groups of ...
Reviews
Charles N. Schroeder
This interesting and well-written paper presents an algorithm for distributed mutual exclusion in a computer network. The algorithm uses messages, rather than shared memory, to pass the equivalent of a token that allows the node holding the privilege to enter the critical section. The author compares the algorithm to others, suggests ways to improve it, and lists some possible problems. The network topology affects the algorithm's performance (the number of messages passed); Raymond discusses best and worst cases as well as two variations of the algorithm's implementation. I found the paper easy to read and to follow. One could easily scan it for the major concepts, and even a novice at distributed systems and networking should be able to follow the flow of the paper and most of the proofs. I recommend this interesting approach to the general reader interested in distributed systems and networks.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments