A fault-tolerant commit protocol for replicated databases

ABSTRACT

When failures occur during the execution of distributed commit protocols, the protocols may block in some partitions to avoid inconsistent termination of the transaction, thus making data items in these partitions unavailable for accesses. We present a protocol that incorporates two new ideas with the goal of improving data availability. First, a new two-level voting scheme is proposed for deciding in which partitions to terminate the transaction. In this scheme, a choice is made based on the number of data items available in the partition rather than on the number of individual nodes. Indeed, in replicated systems, a criterion based on the number of nodes may be misleading. Second, we propose a way to reduce blocking caused by accumulating network fragmentation. The idea employs the views mechanism previously used in replica management.

REFERENCES

• 1: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 2: Shun Yan Cheung , Mostafa H. Ammar , Mustaque Ahamad, The Grid Protocol: A High Performance Scheme for Maintaining Replicated Data, Proceedings of the Sixth International Conference on Data Engineering, p.438-445, February 05-09, 1990
• 3: 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]
• 4: H. Garcia-Molina. Elections in a distributed computing system. IEEE Trans. Computers, C-31 (1), pp. 48-59, January 1982.
• 5: 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]
• 6: Ching-Liang Huang , Victor O. K. Li, A Quorum-Based Commit and Termination Protocol for Distributed Database Systems, Proceedings of the Fourth International Conference on Data Engineering, p.136-143, February 01-05, 1988
• 7: 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]
• 8: A. Kumar. Performance analysis of a hierarchical quorum consensus algorithm for replicated objects. In Proc. of lOth Symp. on Distributed Computing Sys., pp. 378- 385, IEEE, 1990.
• 9: Barbara Liskov, Distributed programming in Argus, Communications of the ACM, v.31 n.3, p.300-312, March 1988 [doi>10.1145/42392.42399]
• 10: Michael Rabinovich , Edward D. Lazowska, Improving fault tolerance and supporting partial writes in structured coterie protocols for replicated objects, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.226-235, June 02-05, 1992, San Diego, California, United States
• 11: 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]
• 12: D. Skeen. A quorum-based commit protocol. In Proc. of the 6th Berkeley Workshop on Distr. Data Management and Comp. Networks, pp. 69-80, 1982.
• 13: D. Skeen and M.Stonebraker. A formal model of crash recovery in a distributed system. IEEE Trans. on Software Eng., 9(3), pp. 219-228, May 1983.
• 14: 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]
• 15: Frank Schmuck , Jim Wylie, Experience with transactions in QuickSilver, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.239-253, October 13-16, 1991, Pacific Grove, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms