Two-Phase Commit Protocol

Two-Phase Commit Protocol (2PC) is a distributed atomic commitment algorithm in computation and algorithms that ensures a transaction spanning multiple independent database nodes or resource managers either commits on all participating nodes or aborts on all participating nodes. Formalized by database pioneer Jim Gray in his 1978 operating-systems monograph (and refined with Butler Lampson and Howard Sturgis in the X/Open XA distributed transaction standard), 2PC enforces the Atomicity and Durability ensures of ACID transactions across partitioned data shards.

In distributed systems and computational complexity theory, a multi-partition transaction T cannot simply send a single one-way "commit" message to N participant nodes: if N − 1 nodes execute the commit while the N-th node rejects it due to a local integrity constraint violation, disk-full error, or crash before writing to stable storage, the distributed database enters a permanently torn state. The Two-Phase Commit protocol resolves this by appointing a single Transaction Coordinator that separates voting (Phase 1: Prepare) from decision execution (Phase 2: Commit or Abort), using synchronous write-ahead logging (WAL) on non-volatile storage so that any node recovering from a crash can reconstruct its commitment obligation.

Safety and Liveness Conditions of Atomic Commitment

Let T be a distributed transaction involving a coordinator C and a set of N participant nodes (cohorts) P = {p₁, p₂, ..., p_N}. Each participant p_i initially casts a local vote v_i ∈ {YES, NO} reflecting whether p_i has validated all local constraints and can durably guarantee the execution of its sub-transaction. An Atomic Commitment Protocol (ACP) must satisfy four formal invariants (Bernstein, Hadzilacos, & Goodman, 1987):

1. Agreement (Uniformity): No two participants decide differently; if any participant commits T, then no participant aborts T.
2. Validity (Unanimity for Commit):
   • A participant may decide COMMIT only if every participant p₁, ..., p_N voted YES (v₁ = v₂ = ... = v_N = YES).
   • If any participant votes NO (v_i = NO for some i), the only permissible decision is ABORT.
3. Non-Triviality: If all participants vote YES and no failures or timeouts occur during the execution, the decision must be COMMIT.
4. Weak Termination: If all failures are eventually repaired and no new failures occur for sufficiently long, every participant eventually reaches a decision.

Phase 1 (Prepare / Voting) and Phase 2 (Commit / Completion)

To survive crash-recovery failures, both the coordinator C and every participant p_i maintain a durable Write-Ahead Log (WAL) flushed to non-volatile disk (via fsync) before transmitting protocol messages:

1. Phase 1 — Voting (Prepare Phase):
   • 1a. Coordinator Prepare Broadcast: Coordinator C writes a 〈BEGIN-COMMIT, T〉 record to its log and sends a PREPARE(T) message to all N participants p₁, ..., p_N.
   • 1b. Participant Evaluation and Durable Vote: Upon receiving PREPARE(T), participant p_i verifies whether it can commit T:
   • If p_i can commit, it flushes all undo and redo log records for T plus a 〈PREPARED, T〉 record to its local durable WAL, and replies VOTE-YES(T) to C. By entering the Prepared (In-Doubt) state, p_i surrenders its unilateral right to abort T and holds its row/page locks until instructed by C.
   • If p_i cannot commit, it writes 〈ABORT, T〉 to its WAL, releases local locks, rolls back T locally, and replies VOTE-NO(T) to C (unilateral abort).

1. Phase 2 — Completion (Decision Phase):
   • 2a. Coordinator Global Decision:
   • Commit Case: If C receives VOTE-YES(T) from all N participants within its timeout window, C force-writes 〈COMMIT, T〉 to its durable WAL. The instant this single log record hits stable storage at C, the transaction is irrevocably committed. C then sends GLOBAL-COMMIT(T) to all N participants.
   • Abort Case: If C receives even a single VOTE-NO(T) or times out waiting for any participant's vote, C force-writes 〈ABORT, T〉 to its WAL and sends GLOBAL-ABORT(T) to all participants that did not already vote NO.
   • 2b. Participant Completion and Acknowledgment: Upon receiving GLOBAL-COMMIT(T) (or GLOBAL-ABORT(T)), participant p_i force-writes 〈COMMIT, T〉 (or 〈ABORT, T〉) to its WAL, applies the commit (or undo rollback), releases all locks held by T, and sends ACK(T) back to C. Once C receives ACK(T) from all participants, C writes a non-forced 〈END, T〉 record and forgets T.

Why 2PC is a Blocking Protocol Under Dual Failure

The fundamental limitation of Two-Phase Commit—proved inevitable for any single-coordinator protocol in asynchronous networks by the Skeen–Stonebraker (1983) theorem and the Fischer–Lynch–Paterson (FLP, 1985) impossibility result—is that 2PC is a blocking protocol.

Suppose participant p₁ has voted VOTE-YES(T) and is waiting in the Prepared (In-Doubt) state while holding exclusive database locks on modified rows. If the coordinator C crashes before p₁ receives GLOBAL-COMMIT or GLOBAL-ABORT, p₁ cannot safely decide on its own:

• p₁ cannot unilaterally abort T, because every participant might have voted YES and C might have already committed T (and notified another participant p₂ before crashing).
• p₁ cannot unilaterally commit T, because another participant p_k might have voted NO or timed out before C crashed.

Under a Cooperative Termination Protocol (Bernstein et al., 1987), p₁ can query its peer participants p₂, ..., p_N: if any peer has already committed or aborted, p₁ adopts that decision; if any peer has not yet voted, that peer can unilaterally abort and all peers abort. However, if all reachable peers are also in the Prepared state (or if one peer p_k crashed simultaneously with C after receiving C's decision), the surviving participants remain blocked—holding database locks until the coordinator C recovers and reads its durable WAL.

Mohan–Lindsay Presumed Abort (PrA) and Presumed Commit (PrC)

In 1986, C. Mohan, Bruce Lindsay, and Ron Obermarck (IBM System R* project) introduced two industry-standard log and message optimizations for 2PC:

1. Presumed Abort (PrA): Whenever the coordinator C has no information about a transaction T in its active table or WAL (for instance, after C crashes and reboots), C presumes T aborted and replies GLOBAL-ABORT(T) to any inquiring participant. Consequently, on an abort decision, C does not need to force-write 〈ABORT, T〉 to disk before sending GLOBAL-ABORT, and participants do not need to send ACK messages for aborts—saving 1 forced disk write and N messages on every aborted or read-only transaction.
2. Presumed Commit (PrC): In workloads where > 99% of prepared transactions succeed, PrC reverses the default: absence of a record in C's table after recovery means T committed. To make this safe if C crashes before deciding, C force-writes a 〈COLLECTING, T, P〉 log record before sending PREPARE(T), which allows C to omit ACK messages and 〈END, T〉 records on the commit path.

Paxos Commit (Gray & Lamport, 2006)

Rather than using Dale Skeen's (1981) Three-Phase Commit (3PC)—which inserts a PRE-COMMIT phase to avoid blocking under pure fail-stop crashes, but violates safety and splits brain during asynchronous network partitions (see the CAP theorem)—modern cloud-native NewSQL databases (Google Spanner, CockroachDB, YugabyteDB) combine 2PC across shards with Paxos or Raft consensus inside each shard. Formalized by Jim Gray and Leslie Lamport in 2006 as Paxos Commit, replacing the single coordinator C with a 2F + 1 consensus state machine eliminates single-node coordinator blocking while preserving ACID serializability alongside vector clock or TrueTime commit timestamps and Chandy–Lamport algorithm snapshots.

How does the Read-Only Optimization in Two-Phase Commit save an entire phase for read-only participants?

If a participant p_i determines during Phase 1 (PREPARE) that transaction T performed only reads and modified zero rows at p_i, p_i does not matter to the commit/abort outcome on other shards. Therefore, p_i writes zero log records, releases its read locks directly, and replies VOTE-READONLY(T) to the coordinator C, which excludes p_i from Phase 2 altogether.

Why is Three-Phase Commit (3PC) rarely used in production databases compared to 2PC + Paxos?

Three-Phase Commit (3PC) assumes a synchronous fail-stop network with a known upper bound on message latency so timeouts accurately distinguish a crashed node from a slow network link. In real-world TCP/IP networks subject to asymmetric partitions or garbage-collection pauses, a partitioned subset of nodes in 3PC can time out and abort while another partitioned subset advances from PRE-COMMIT to COMMIT, violating atomic agreement—whereas Paxos Commit requires an overlapping majority quorum (⌊M/2⌋ + 1) and never splits brain under any network partition.

1. Gray, J. (1978). "Notes on data base operating systems." Operating Systems: An Advanced Course, LNCS Vol. 60, Springer, 393–481. https://doi.org/10.1007/3-540-08755-9_9
2. Skeen, D. (1981). "Nonblocking commit protocols." Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data (SIGMOD '81), 133–142. https://doi.org/10.1145/582318.582339
3. Mohan, C., Lindsay, B., & Obermarck, R. (1986). "Transaction management in the R* distributed database management system." ACM Transactions on Database Systems, 11(4), 378–396. https://doi.org/10.1145/7239.7266
4. Gray, J., & Lamport, L. (2006). "Consensus on transaction commit." ACM Transactions on Database Systems, 31(1), 133–160. https://doi.org/10.1145/1132863.1132867
5. Corbett, J. C., Dean, J., Epstein, M., Fikes, A., Frost, C., Furman, J. J., Ghemawat, S., Gubarev, A., Heiser, C., Hochschild, P., Hsieh, W., Kanthak, S., Kogan, E., Li, H., Lloyd, A., Melnik, S., Mwaura, D., Nagle, D., Quinlan, S., Rao, R., Rolig, L., Saito, Y., Szymaniak, M., Taylor, C., Wang, R., & Woodford, D. (2013). "Spanner: Google's globally distributed database." ACM Transactions on Computer Systems, 31(3), 8:1–8:22. https://doi.org/10.1145/2491245