The generalized tree quorum protocol: an efficient approach for managing replicated data

ABSTRACT

In this paper, we present a low-cost fault-tolerant protocol for managing replicated data. We impose a logical tree structure on the set of copies of an object and develop a protocol that uses the information available in the logical structure to reduce the communication requirements for read and write operations. The tree quorum protocol is a generalization of the static voting protocol with two degrees of freedom for choosing quorums. In general, this results in significantly lower communication costs for comparable data availability. The protocol exhibits the property of graceful degradation, i.e., communication costs for executing operations are minimal in a failure-free environment but may increase as failures occur. This approach in designing distributed systems is desirable since it provides fault-tolerance without imposing unnecessary costs on the failure-free mode of operations.

REFERENCES

• 1: D. Agrawal , A. El Abbadi, Efficient solution to the distributed mutual exclusion problem, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.193-200, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72994]
• 2: 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]
• 3: Divyakant Agrawal , Amr El Abbadi, Locks with constrained sharing (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.85-93, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298545]
• 4: 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
• 5: M. Ahamad , M. H. Ammar, Performance Characterization of Quorum-Consensus Algorithms for Replicated Data, IEEE Transactions on Software Engineering, v.15 n.4, p.492-496, April 1989 [doi>10.1109/32.16608]
• 6: BERNSTEIN, P. A., AND GOODMAN, N. A proof technique for concurrency control and recovery algorithms for replicated databases. In Distributed Comput. 2, 1 (Jan. 1987), 32-44.
• 7: Dančo Davčev , Walter A. Burkhard, Consistency and recovery control for replicated files, Proceedings of the tenth ACM symposium on Operating systems principles, p.87-96, December 1985, Orcas Island, Washington, United States
• 8: 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]
• 9: Derek L. Eager , Kenneth C. Sevcik, Achieving robustness in distributed database systems, ACM Transactions on Database Systems (TODS), v.8 n.3, p.354-381, Sept. 1983 [doi>10.1145/319989.319992]
• 10: Amr El Abbadi , Dale Skeen , Flaviu Cristian, An efficient, fault-tolerant protocol for replicated data management, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.215-229, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325443]
• 11: A. El Abbadi , S. Toueg, Maintaining availability in partitioned replicated databases, ACM Transactions on Database Systems (TODS), v.14 n.2, p.264-290, June 1989 [doi>10.1145/63500.63501]
• 12: K. P. Eswaran , J. N. Gray , R. A. Lorie , I. L. Traiger, The notions of consistency and predicate locks in a database system, Communications of the ACM, v.19 n.11, p.624-633, Nov. 1976 [doi>10.1145/360363.360369]
• 13: 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]
• 14: 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]
• 15: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 16: Maurice Herlihy, A quorum-consensus replication method for abstract data types, ACM Transactions on Computer Systems (TOCS), v.4 n.1, p.32-53, Feb. 1986 [doi>10.1145/6306.6308]
• 17: Maurice Herlihy, Dynamic quorum adjustment for partitioned data, ACM Transactions on Database Systems (TODS), v.12 n.2, p.170-194, June 1987 [doi>10.1145/22952.22953]
• 18: S. Jajodia , David Mutchler, Dynamic voting algorithms for maintaining the consistency of a replicated database, ACM Transactions on Database Systems (TODS), v.15 n.2, p.230-280, June 1990 [doi>10.1145/78922.78926]
• 19: KUMAR, A. PeWormance analysis of a hierarchical quorum consensus algorithm for replicated objects. In Proceedings of the Tenth International Conference on Dtstrlbuted Computing Systems (Paris, May 1990), pp. 320-327.
• 20: H. T. Kung , John T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), v.6 n.2, p.213-226, June 1981 [doi>10.1145/319566.319567]
• 21: 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]
• 22: 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]
• 23: Jehan-François Pâris , Darrell D. E. Long, Efficient Dynamic Voting Algorithms, Proceedings of the Fourth International Conference on Data Engineering, p.268-275, February 01-05, 1988
• 24: D. P. Reed, NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 25: Richard D. Schlichting , Fred B. Schneider, Fail-stop processors: an approach to designing fault-tolerant computing systems, ACM Transactions on Computer Systems (TOCS), v.1 n.3, p.222-238, August 1983 [doi>10.1145/357369.357371]
• 26: Abraham Silberschatz , Zvi Kedem, Consistency in Hierarchical Database Systems, Journal of the ACM (JACM), v.27 n.1, p.72-80, Jan. 1980 [doi>10.1145/322169.322176]
• 27: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design

General Terms:
Algorithms, Economics, Experimentation, Measurement, Performance