A distributed mutual exclusion algorithm

ABSTRACT

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 than in an algorithm of Ricart and Agrawala, which requires 2*(N - 1) message exchanges per invocation. A drawback of the algorithm is that the sequence numbers contained in the messages are unbounded. It is shown that this problem can be overcome by slightly increasing the number of message exchanges.

REFERENCES

• 1: Glenn Ricart , Ashok K. Agrawala, An optimal algorithm for mutual exclusion in computer networks, Communications of the ACM, v.24 n.1, p.9-17, Jan. 1981 [doi>10.1145/358527.358537]
• 2: SUZUKI, I., AND KASAMI, T. An optimality theory for mutual exclusion algorithms in computer networks. In Proceedings of the 3rd International Conference on Distributed Computing Systems (Oct. 18-22, Fort Lauderdale, Fla.), IEEE, N.Y., 365-370.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Mutual exclusion

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms