Consensus on transaction commit

By Jim Gray, Leslie Lamport. TODS, 2004

405 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/2e702e5f18330f8aab4c976bb4b06e7c6b767121

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

SoK: Consensus in the Age of Blockchains (2017, background): “In fact the traditional literature on byzantine consensus does not discuss distribution of resources, in the context of a distributed or sharded database, with the exception of a less known joint work by Gray and Lamport on combining atomic broadcast with atomic commit [50].”
A comprehensive study of Convergent and Commutative Replicated Data Types (2011, methodology): “In first approximation, this requires an atomic, unanimous agreement between all replicas, i.e., a commitment protocol such as 2-Phase Commit or Paxos Commit [15].”
Spanner: Google's Globally-Distributed Database (2012, neutral): “Gray and Lamport [18] describe a non-blocking commit protocol based on Paxos.”
Want to scale in centralized systems? Think P2P (2015, background): “…support the reconfiguration of these groups ( e.g. , to accommodate shifting workloads, node failures, or new resources), Scatter further stacks a two-phase commit protocol on top of Paxos (a combination proposed earlier by Leslie Lamport and Jim Gray [28], and also found in Google’s Spanner [24]).”
Megastore: Providing Scalable, Highly Available Storage for Interactive Services (2011, methodology): “SCALARIS is one example that uses the Paxos commit protocol [22] to implement replication for a distributed hash table [30].”
Mencius: Building Efficient Replicated State Machine for WANs (2008, positive): “And, we seek a solution that comes with a derivation, like the popular consensus protocol Paxos has [22], so it can be modified to apply it to a specific application [15].”
Chainspace: A Sharded Smart Contracts Platform (2017, methodology): “We propose the use of a simple two-phase commit protocol [BHG87], composed with an agreement protocol to achieve this—loosely inspired by Lamport and Gray [GL06].”
Sinfonia: a new paradigm for building scalable distributed systems (2007, background): “Paxos Commit [Gray and Lamport 2006] is a nonblocking commit protocol, whose basic ideas are: (1) to replace participants with state machines running Paxos, (2) to consider a transaction to be committed if and only if all the state machines have voted to commit, and (3) various optimizations to save”