A distributed transaction processing protocol based on majority consensus

ABSTRACT

An n-failure-resilient protocol for distributed transaction processing regarding site crash, network partitioning, and local failures like abort of subtransactions is specified. The three-phased protocol contains concurrency control, a mechanism enforcing mutual consistency, and commitment based on majority consensus w.r.t. multiple copies of entities. To cope with transaction manager failures, backup processes for the manager are used. Data redundancy given by multiple copies in a partially redundant database is utilized to improve the resiliency of the protocol, i.e. to improve especially the successful commitment of update transactions processed by the protocol. The protocol is n-failure-resilient if the least redundant entity to be accessed by a transaction is mapped onto at least 2n+1 file copies in the distributed database.

REFERENCES

• 1: 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
• 2: J. L. Baer , G. Gardarin , C. Girault , G. Roucairol, The two-step commitment protocol: Modeling, specification and proof methodology, Proceedings of the 5th international conference on Software engineering, p.363-373, March 09-12, 1981, San Diego, California, United States
• 3: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 4: Boudenant, J.: Some solutions for database recovery in SIRIUS-DELTA, Proc. 2nd Seminar on Distributed Data Sharing Systems, Amsterdam, 1981
• 5: Breitwieser, H.; Leszak, M.: Improving availability of partially redundant databases by majority consensus protocols, Proc. 2nd Int. Symp. on Distributed Databases, Berlin, Sept. 1982
• 6: Cheng, W.K.: The resiliency of fully replicated distributed databases, Proc. 6th Berkeley Workshop, 1982
• 7: Fraboul, C.: Robust mechanisms for maintaining a redundant distributed database, Proc. Int. Conf. on Databases, Aberdeen, 1980
• 8: 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]
• 9: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 10: Micael Hammer , David Shipman, Reliability mechanisms for SDD-1: a system for distributed databases, ACM Transactions on Database Systems (TODS), v.5 n.4, p.431-466, Dec. 1980 [doi>10.1145/320610.320621]
• 11: International Organization for Standardization: Data processing - Open Systems Interconnection - Basic Reference Model, Draft proposal, ISO/DP 7498, January 1982
• 12: Lampson, B.; Sturgis, H.: Crash recovery in a distributed data storage system, Research Report, XEROX PARC, 1979
• 13: Lindsay, B.G. et.al: Notes on distributed databases, IBM Research Report RJ2571, 1979
• 14: Daniel A. Menasce , Gerald J. Popek , Richard R. Muntz, A locking protocol for resource coordination in distributed databases, ACM Transactions on Database Systems (TODS), v.5 n.2, p.103-138, June 1980 [doi>10.1145/320141.320143]
• 15: Munz, R.: Transaction management in the distributed database system VDN, Proc. IFIP Congress, Tokyo, 1981
• 16: Popek, G.J. et.al: Detection of mutual inconsistencies in distributed systems, Proc. 5th Berkeley Workshop, 1981
• 17: J. B. Rothnie, Jr. , P. A. Bernstein , S. Fox , N. Goodman , M. Hammer , T. A. Landers , C. Reeve , D. W. Shipman , E. Wong, Introduction to a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.5 n.1, p.1-17, March 1980 [doi>10.1145/320128.320129]
• 18: 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]
• 19: Skeen, D.: A quorum-based commit protocol, Proc. 6th Berkeley Workshop, 1982
• 20: Stonebraker, M.: Concurrency control and consistency of multiple copies of data in distributed INGRES, IEEE TSE 3 (1979) 5, pp. 188-194
• 21: 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]
• 22: Toth, K.C.; Mahmoud, S.A.; Riordon, J.S.: Query processing strategies in a distributed database architecture, Proc. of the 2nd Sem. on Distributed Data Sharing Systems, Amsterdam, 1981
• 23: Walter, B.: A robust and efficient protocol for checking the availability of remote sites, Proc. 6th Berkeley Workshop, February 1982

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Applications (SMTP, FTP, etc.)

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

General Terms:
Design, Management