Decentralized mutual exclusion in the presence of link failures

ABSTRACT

A distributed algorithm for achieving mutual exclusion in a point-to-point network with lossy communication links is presented. A communication link is said to be lossy if it loses messages at will. The algorithm tolerates any number of lossy communication links, as long as the link failures do not partition the communication network. The message network is completely asynchronous and, hence, link failures are not detectable. In a network with n nodes and e links, the algorithm requires no more than 2e(2√n + 1) message transmissions per mutual exclusion request.

REFERENCES

• ALBE68: A. A. Albert and R. Sandier, An Introduction to Finite Projective Planes. Holt, Rinehart and Winston, New York, 1968.
• DIJK65: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• FISC85: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• LAKS86: T. V. Lakshman , Ashok K. Agrawala, Efficient decentralized consensus protocols, IEEE Transactions on Software Engineering, v.12 n.5, p.600-607, May 1986
• LAMP74: Leslie Lamport, A new solution of Dijkstra's concurrent programming problem, Communications of the ACM, v.17 n.8, p.453-455, Aug. 1974 [doi>10.1145/361082.361093]
• LAMP78: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• LAMP84: Leslie Lamport, Using Time Instead of Timeout for Fault-Tolerant Distributed Systems., ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.2, p.254-280, April 1984 [doi>10.1145/2993.2994]
• LAMP86a: Leslie Lamport, The mutual exclusion problem: part I—a theory of interprocess communication, Journal of the ACM (JACM), v.33 n.2, p.313-326, April 1986 [doi>10.1145/5383.5384]
• LAMP86b: Leslie Lamport, The mutual exclusion problem: part I—a theory of interprocess communication, Journal of the ACM (JACM), v.33 n.2, p.313-326, April 1986 [doi>10.1145/5383.5384]
• MAEK85: Mamoru Maekawa, A N algorithm for mutual exclusion in decentralized systems, ACM Transactions on Computer Systems (TOCS), v.3 n.2, p.145-159, May 1985 [doi>10.1145/214438.214445]
• MCCU86: R McCurley , F B Schneider, Derivation of a distributed algorithm for finding paths in directed networks, Science of Computer Programming, v.6 n.1, p.1-9, Jan. 1986
• RICA81: 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]
• ROBE84: Fred S. Roberts, Applied combinatorics, 1984
• SAND87: Beverly A. Sanders, The information structure of distributed mutual exclusion algorithms, ACM Transactions on Computer Systems (TOCS), v.5 n.3, p.284-299, Aug. 1987 [doi>10.1145/24068.28052]
• SCHN82: Fred B. Schneider, Synchronization in Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.2, p.125-148, April 1982 [doi>10.1145/357162.357163]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms