Method for distributed transaction commit and recovery using Byzantine Agreement within clusters of processors

ABSTRACT

This paper describes an application of Byzantine Agreement [DoSt82a, DoSt82c, LyFF82] to distributed transaction commit. We replace the second phase of one of the commit algorithms of [MoLi83] with Byzantine Agreement, providing certain trade-offs and advantages at the time of commit and providing speed advantages at the time of recovery from failure. The present work differs from that presented in [DoSt82b] by increasing the scope (handling a general tree of processes, and multi-cluster transactions) and by providing an explicit set of recovery algorithms. We also provide a model for classifying failures that allows comparisons to be made among various proposed distributed commit algorithms. The context for our work is the Highly Available Systems project at the IBM San Jose Research Laboratory [AAFKM83].

REFERENCES

• 1: Aghili, H., Astrahan, M., Finkelstein, S., Kim, W., McPherson, J., Schkolnick, M., Strong, R. "A Highly Available Database System", IBM Research Report RJ3755, January 1983.
• 2: Borr, A. "Transaction Monitoring in ENCOMPASS: Reliable Distributed Transaction Processing", Proc. International Conference on Very Large Data Bases, September 1981.
• 3: Dolev, D., Fischer, M., Fowler, R., Lynch, N., Strong, H.R. "An Efficient Byzantine Agreement Without Authentication", Information and Control to appear. See also IBM Research Report RJ3428, March 1982.
• 4: Danny Dolev , H. Raymond Strong, Polynomial algorithms for multiple processor agreement, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.401-407, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802215]
• 5: Dolev, D., Strong, H.R. "Distributed Commit with Bounded Waiting", Proc. Second IEEE Symposium on Reliability in Distributed Software and Database Systems, Pittsburgh, July 1982. See also IBM Research Report RJ3417, 1982.
• 6: Dolev, D., Strong, H.R. "Authenticated Algorithms for Byzantine Agreement", SIAM Journal on Computing, to appear. See also IBM Research Report RJ3416, March 1982.
• 7: 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.
• 8: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 9: Gray, J. "The Transaction Concept: Virtues and Limitations", Proc. Seventh Int. Conf. on Very Large Data Bases, October 1981.
• 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: 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.
• 12: Lamport, L., Melliar-Smith, P.M. "Synchronizing Clocks in the Presence of Faults", Technical Report, SRI International, March 1982.
• 13: Butler W. Lampson, Atomic Transactions, Distributed Systems - Architecture and Implementation, An Advanced Course, p.246-265, January 1981
• 14: 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
• 15: 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 IW. Draffan and F. Poole, Cambridge University Press, 1980. Also Available as "Notes on Distributed Databases", IBM Research Report RJ2571, San Jose, July 1979.
• 16: Lynch, N., Fischer, M., Fowler, R. "A Simple and Efficient Byzantine Generals Algorithm", Proc. Second IEEE Symposium on Reliability in Distributed Software and Database Systems, Pittsburgh, July 1982.
• 17: C. Mohan , B. Lindsay, Efficient commit protocols for the tree of processes model of distributed transactions, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.76-88, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806711]
• 18: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 19: Schneider, F.B. "Fail-Stop Processors", Proc. COMPCON Spring '83, San Francisco, March 1983, pp. 66-70.
• 20: 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]
• 21: Skeen, D. "A Quorum-based Commit Protocol", Proc. 6th Berkeley Workshop on Distributed Data Management and Computer Networks, May 1982, pp. 69-90.

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:
Management