Consensus on transaction commit

ABSTRACT

The distributed transaction commit problem requires reaching agreement on whether a transaction is committed or aborted. The classic Two-Phase Commit protocol blocks if the coordinator fails. Fault-tolerant consensus algorithms also reach agreement, but do not block whenever any majority of the processes are working. The Paxos Commit algorithm runs a Paxos consensus algorithm on the commit/abort decision of each participant to obtain a transaction commit protocol that uses 2F + 1 coordinators and makes progress if at least F + 1 of them are working properly. Paxos Commit has the same stable-storage write delay, and can be implemented to have the same message delay in the fault-free case as Two-Phase Commit, but it uses more messages. The classic Two-Phase Commit algorithm is obtained as the special F = 0 case of the Paxos Commit algorithm.

REFERENCES

• 1: Marcos Kawazoe Aguilera , Carole Delporte-Gallet , Hugues Fauconnier , Sam Toueg, Stable Leader Election, Proceedings of the 15th International Conference on Distributed Computing, p.108-122, October 03-05, 2001
• 2: Alpern, B. and Schneider, F. B. 1985. Defining liveness. Inf. Process. Lett. 21, 4 (Oct.), 181--185.
• 3: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 4: Borr, A. J. 1981. Transaction monitoring in encompass: Reliable distributed transaction processing. In Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data (Ann Arbor, MI, April 29-May 1), Y. E. Lien, Ed. ACM Press, New York, NY, 155--165.
• 5: Charron-Bost, B. and Schiper, A. 2000. Uniform consensus is harder than consensus (extended abstract). Tech. rep. DSC/2000/028. École Polytechnique Fédérale de Lausanne, Switzerland.
• 6: Roberto De Prisco , Butler W. Lampson , Nancy A. Lynch, Revisiting the Paxos Algorithm, Proceedings of the 11th International Workshop on Distributed Algorithms, p.111-125, September 24-26, 1997
• 7: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 8: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 9: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 10: Rachid Guerraoui, Revistiting the Relationship Between Non-Blocking Atomic Commitment and Consensus, Proceedings of the 9th International Workshop on Distributed Algorithms, p.87-100, September 13-15, 1995
• 11: Reducing the cost for non-blocking in atomic commitment, Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS '96), p.692, May 27-30, 1996
• 12: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 13: Lamport, L. 2001. Paxos made simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Dec.), 18--25.
• 14: Lamport, L. 2003. Specifying Systems. Addison-Wesley, Boston, MA. A link to an electronic copy can be found online at http://lamport.org.
• 15: Butler W. Lampson, How to Build a Highly Available System Using Consensus, Proceedings of the 10th International Workshop on Distributed Algorithms, p.1-17, October 09-11, 1996
• 16: 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]
• 17: Newcomer, E. 2002. Understanding Web Services. Addison-Wesley, Boston, MA.
• 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: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Reliability

Keywords:
Consensus, Paxos, two-phase commit