An efficient and fault-tolerant solution for distributed mutual exclusion

ABSTRACT

In this paper, we present an efficient and fault-tolerant algorithm for generating quorums to solve the distributed mutual exclusion problem. The algorithm uses a logical tree organization of the network to generate tree quorums, which are logarithmic in the size of the network in the best case. Our approach is resilient to both site and communication failures, even when such failures lead to network partitioning. Furthermore, the algorithm exhibits a property of graceful degradation, i.e., it requires more messages only as the number of failures increase in the network. We describe how tree quorums can be used for various distributed applications for providing mutually exclusive access to a distributed resource, managing replicated objects, and atomically commiting a distributed transaction.

REFERENCES

• 1: D. Agrawal , A. El Abbadi, Exploiting logical structures in replicated databases, Information Processing Letters, v.33 n.5, p.255-260, January 1990 [doi>10.1016/0020-0190(90)90194-3]
• 2: D. Agrawal , A. El Abbadi, The tree quorum protocol: an efficient approach for managing replicated data, Proceedings of the sixteenth international conference on Very large databases, p.243-254, September 1990, Brisbane, Australia
• 3: Peter A. Alsberg , John D. Day, A principle for resilient sharing of distributed resources, Proceedings of the 2nd international conference on Software engineering, p.562-570, October 13-15, 1976, San Francisco, California, United States
• 4: José M. Bernabéu-Aubán , Mustaque Ahamad, Applying a Path-Compression technique to Obtain an Efficient Distributed Mutual Exclusion Algorithm, Proceedings of the 3rd International Workshop on Distributed Algorithms, p.33-44, September 26-28, 1989
• 5: Susan B. Davidson , Hector Garcia-Molina , Dale Skeen, Consistency in a partitioned network: a survey, ACM Computing Surveys (CSUR), v.17 n.3, p.341-370, Sept. 1985 [doi>10.1145/5505.5508]
• 6: Hector Garcia-Molina , Daniel Barbara, How to assign votes in a distributed system, Journal of the ACM (JACM), v.32 n.4, p.841-860, Oct. 1985 [doi>10.1145/4221.4223]
• 7: David K. Gifford, Weighted voting for replicated data, Proceedings of the seventh ACM symposium on Operating systems principles, p.150-162, December 10-12, 1979, Pacific Grove, California, United States [doi>10.1145/800215.806583]
• 8: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 9: J. M. Helary , N. Plouzeau , M. Raynal, A distributed algorithm for mutual exclusion in an arbitrary network, The Computer Journal, v.31 n.4, p.289-295, August 1988
• 10: 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]
• 11: N. A. Lynch , M. Merritt, INTRODUCTION TO THE THEORY OF NESTED TRANSACTIONS, Massachusetts Institute of Technology, Cambridge, MA, 1986
• 12: 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]
• 13: Stephen R. Mahaney , Fred B. Schneider, Inexact agreement: accuracy, precision, and graceful degradation, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.237-249, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323618]
• 14: Jayadev Misra, Detecting termination of distributed computations using markers, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.290-294, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806729]
• 15: J. E.B. Moss, Nested transactions: an approach to reliable distributed computing, Massachusetts Institute of Technology, Cambridge, MA, 1985
• 16: Mohamed Naimi , Michel Trehel, How to Detect a Failure and Regenerate the Token in the Log(N) Distributed Algorithm for Mutual Exclusion, Proceedings of the 2nd International Workshop on Distributed Algorithms, p.155-166, July 08-10, 1987
• 17: Kerry Raymond, A tree-based algorithm for distributed mutual exclusion, ACM Transactions on Computer Systems (TOCS), v.7 n.1, p.61-77, Feb. 1989 [doi>10.1145/58564.59295]
• 18: 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]
• 19: 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]
• 20: 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]
• 21: Dale Skeen, Nonblocking commit protocols, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582339]
• 22: SKEIN, D A quorum based commit protocol. In Procee&ngs of the 6th Berkeley' Workshop on D~strtbuted Data Management and Computer Networks (Feb. 1982), 69-80
• 23: Ichiro Suzuki , Tadao Kasami, A distributed mutual exclusion algorithm, ACM Transactions on Computer Systems (TOCS), v.3 n.4, p.344-349, Nov. 1985 [doi>10.1145/6110.214406]
• 24: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 25: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 26: VAN DE S~Et'SCHEUT, J. L Fair mutual exclusmn on a graph of processes Dzstrtbut Comput 2 (1987), 113-115.

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

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Reliability