Open commit protocols tolerating commission failures

ABSTRACT

To ensure atomicity of transactions in distributed systems so-called 2-phase commit (2PC) protocols have been proposed. The basic assumption of these protocols is that the processing nodes involved in transactions are “sane,” i.e., they only fail with omission failures, and nodes eventually recover from failures. Unfortunately, this assumption is not realistic for so-called Open Distributed Systems (ODSs), in which nodes may have totally different reliability characteristics. In ODSs, nodes can be classified into trusted nodes (e.g., a banking server) and nontrusted nodes (e.g., a home PC requesting a remote banking service). While trusted nodes are assumed to be sane, nontrusted nodes may fail permanently and even cause commission failures to occur. In this paper, we propose a family of 2PC protocols that tolerate any number of omission failures at trusted nodes and any number of commission and omission failures at nontrusted nodes. The proposed protocols ensure that (at least) the trusted nodes participating in a transaction eventually terminate the transaction in a consistent manner. Unlike Byzantine commit protocols, our protocols do not incorporate mechanisms for achieving Byzantine agreement, which has advantages in terms of complexity: Our protocols have the same or only a slightly higher message complexity than traditional 2PC protocols.

REFERENCES

• 1: Arvola Chan , Umeshwar Dayal , Stephen Fox , Nathan Goodman , Daniel R. Ries , Dale Skeen, Overview of an Ada compatible distributed database manager, ACM SIGMOD Record, v.13 n.4, May 1983
• 2: DECNET General Descrtptton. Doc. AA-K179A-TK. Digital Equipment Corporation.
• 3: DOLEV, D., AND STRONG, H.R. Distributed commit with bounded waiting. In Proceedings of the Second IEEE Syrup. on Reliability in Distributed Software and Database Systems (1982); see also IBM Research Report RJ3417, 1982.
• 4: Jeffrey L. Eppinger , Lily B. Mummert , Alfred Z. Spector, Camelot and Avalon: a distributed transaction facility, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 5: GARCIA-MOLINA, H., AND ABBOTT, R.K. Reliable distributed database management. Proceedings of the IEEE 75, 5 (1987), 601 620.
• 6: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 7: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• 8: Rober Haskin , Yoni Malachi , Gregory Chan, Recovery management in QuickSilver, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.82-108, Feb. 1988 [doi>10.1145/35037.35060]
• 9: Information Processing Systems Open Systems Interconnection Basic Reference Model. International Standard ISO 7498, 1984.
• 10: Information Processing Systems Open Systems Interconnection--Definition of Common Application Service Elements--Commitment, Concurrency and Recovery. Draft Internationa} Standard ISO 9804/2, 1989.
• 11: Information Processing Systems--Open Systems Interconnection Distributed Transaction Processing-Part 1: Model, Part 2: Service Definition, Part 3: Protocol Specification Draft Proposal ISO 10026/1-3, 1989.
• 12: Butler W. Lampson, Atomic Transactions, Distributed Systems - Architecture and Implementation, An Advanced Course, p.246-265, January 1981
• 13: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 14: LELANN, G. Error Recovem,. Lecture Notes in Computer Science 105, Springer, 1981, 371-376.
• 15: Bruce G. Lindsay , Laura M. Haas , C. Mohan , Paul F. Wilms , Robert A. Yost, Computation and communication in R*: a distributed database manager, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.24-38, February 1984 [doi>10.1145/2080.357390]
• 16: 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]
• 17: C. Mohan , B. Lindsay , R. Obermarck, Transaction management in the R* distributed database management system, ACM Transactions on Database Systems (TODS), v.11 n.4, p.378-396, Dec. 1986 [doi>10.1145/7239.7266]
• 18: 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]
• 19: Roger M. Needham , Michael D. Schroeder, Using encryption for authentication in large networks of computers, Communications of the ACM, v.21 n.12, p.993-999, Dec. 1978 [doi>10.1145/359657.359659]
• 20: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 21: ROTHERMEL, K., AND PAPPE, S. Open commit protocols for the tree of processes model. In Proceedings of the lOth {nternatmnal Conference on Dzstrzbuted Computer Systems (Paris, 1990), 236 244.
• 22: Marshall T. Rose, The open book: a practical perspective on OSI, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 23: 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]
• 24: SKEEN, D., AND STONEBRAKER, M. A formal model of crash recovery in a distributed system In Procee&ngs of the 5th Internatzonal Workshop on Dlstrzbuted Data Management and Computer Netu,orks (1981), 129 142
• 25: Systems Network Architecture Concepts and Products. IBM Corporation, GC30-3072, 1985
• 26: Systems Network Architecture, Format and Protocol Reference Manual: Architecture Logic For LU Type 6.2 IBM Corporation, GC30-3269, 1985.
• 27: SPECTOR, h., THOMPSON, n., PAUSCH, R,, EPPINGER, J. L., DAVES, R., DUCHAMP, D., DANIELS, D. S., AND BLOCH, J.J. Camelot: A distributed transaction facility for Mach and the Internet--an interim report. Tech. Rep, CMU-CS-87-129, Dept. of Computer Science, Carnegie Mellon Univ., Pittsburgh, Pa, 1987.
• 28: Andrew S. Tanenbaum, Computer Networks, Prentice Hall PTR, Upper Saddle River, NJ, 1985
• 29: Introductmn to the Transactmn Momtorzng Fac~l~(~ (TMF) Tandem Computers Incorporated.
• 30: WALTER, B. A robust and efficmnt protocol for checking the availability of remote sites Comput. Netw. 6, 3 (1982), 173 188.
• 31: X/OPEN Portabihty GuLde. Elsevier, New York, 1987.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

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

General Terms:
Algorithms, Performance, Reliability

Keywords:
commit protocols, open systems