Efficient commit protocols for the tree of processes model of distributed transactions

ABSTRACT

This paper describes two efficient distributed transaction commit protocols, the Presumed Abort (PA) and Presumed Commit (PC) protocols, which have been implemented in the distributed data base system R* [DSHLM82, LHMWY83]. PA and PC are extensions of the well-known two-phase (2P) commit protocol [Gray78, Lamp80, LSGGL80]. PA is optimized for read-only transactions and a class of multi-site update transactions, and PC is optimized for other classes of multi-site update transactions. The optimizations result in reduced inter-site message traffic and log writes, and, consequently, a better response time for such transactions. We derive the new protocols in a step-wise fashion by modifying the 2P protocol.

REFERENCES

• 1: Borr, A. "Transaction Monitoring in ENCOMPASS: Reliable Distributed Transaction Processing", Proc. International Conference on Very Large Data Bases, September 1981.
• 2: Eric C. Cooper, Analysis of distributed commit protocols, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582385]
• 3: Daniels, D., Selinger, P., Haas, L., Lindsay, B., Mohan, C., Walker, A., Wilms, P. "An Introduction to Distributed Query Compilation in R*", Proc. Second International Symposium on Distributed Data Bases, Berlin, September 1982. Also IBM Research Report RJ3497.
• 4: Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981 [doi>10.1145/356842.356847]
• 5: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 6: Gray, J. "The Transaction Concept: Virtues and Limitations", Proc. Seventh Int. Conf. on Very Large Data Bases, October 1981.
• 7: Harder, T., Reuter, A. "Principles of Transaction Oriented Database Recovery - A Taxonomy", Technical Report 50/82, University of Kaiserslautern, W. Germany, April 1982.
• 8: 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]
• 9: Haas, L.M., Selinger, P.G., Bertino, E., Daniels, D., Lindsay, B., Lohman, G., Masunaga, Y., Mohan, C., Ng, P., Wilms, P., Yost, R. "R*: A Research Project on Distributed Relational DBMS", Database Engineering, Volume 5, Number 2, December 1982. Also IBM Research Report RJ3653, October 1982.
• 10: Butler W. Lampson, Atomic Transactions, Distributed Systems - Architecture and Implementation, An Advanced Course, p.246-265, January 1981
• 11: Bruce G. Lindsay , Laura M. Haas , Paul F. Wilms , Robert A. Yost, Computation & communication in R: a distributed database manager, Proceedings of the ninth ACM symposium on Operating systems principles, p.1-2, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 12: Lindsay, B., Selinger, P., Galtieri, C., Gray, J., Lorie, R., Putzolu, F., Traiger, I., Wade, B. "Single and Multi-Site Recovery Facilities", In Distributed Data Bases, Edited by I.W. Draffan and F. Poole, Cambridge University Press, 1980. Also Available as "Notes on Distributed Databases", IBM Research Report RJ2571, San Jose, July 1979.
• 13: C. Mohan , R. Strong , S. Finkelstein, Method for distributed transaction commit and recovery using Byzantine Agreement within clusters of processors, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.89-103, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806712]
• 14: 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]
• 15: 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]
• 16: Skeen, D. "A Quorum-Based Commit Protocol", Proc. 6th Berkeley Workshop on Distributed Data Management and Computer Networks, May 1982, pp. 69-90.
• 17: Stonebraker, M. "Concurrency Control and Consistency of Multiple Copies of Data in Distributed INGRES", IEEE Transactions on Software Engineering, Vol. 5, No. 3, May 1979.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

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

General Terms:
Management