Distributed Transactions and Two-Phase Commit

A distributed transaction is a transaction whose effects span multiple independent nodes — for instance, separate database shards, separate microservices, or separate storage replicas. Each node performs its local piece of the transaction (a branch), and the whole transaction is correct only if ACID properties hold globally: either all branches commit, or all branches abort, with no partial outcomes visible to any observer. This all-or-nothing requirement is called atomic commitment, and it is strictly harder than single-node atomicity because a single-node system controls its own clock, its own disk, and never has to ask permission from a remote machine that might be unreachable. The core obstacle is that nodes can independently fail, messages can be delayed or lost, and there is no shared memory to consult for a "true" global state — the same fundamental limitation explored in the study of Global State and Distributed Snapshots. A node cannot simply commit its own branch as soon as it is ready, because another node's branch might later fail; it must wait for confirmation that everyone is ready. This creates a chicken-and-egg problem: nodes must synchronize a decision without a central authority that is always available, which is exactly the same tension formalized by the CAP Theorem between consistency and availability during a partition.

Two-Phase Commit solves this by introducing a distinguished coordinator (also called the transaction manager) and a set of participants (resource managers), which typically communicate via Remote Procedure Calls. The protocol proceeds in two rounds: a voting phase, where the coordinator asks every participant whether it can commit, and a commit phase, where the coordinator broadcasts the final, binding decision. The key invariant that makes this safe is the prepared state: once a participant votes "yes," it has made an irrevocable promise — it must be able to commit later, regardless of crashes, until it hears otherwise from the coordinator. This promise is what lets the coordinator make a unilateral, unanimous decision, but it is also exactly what causes the protocol's central weakness: a participant stuck in the prepared state, unable to reach the coordinator, cannot safely proceed on its own.

Phase 1 — Voting (the "can you commit?" round). The coordinator sends a `PREPARE` (also called `VOTE-REQUEST`) message to every participant. Each participant executes its part of the transaction up to the point of commit, writes a durable log record recording its intended outcome, and replies `VOTE-COMMIT` if it is able to guarantee a future commit, or `VOTE-ABORT` if it cannot (due to a constraint violation, deadlock, or local failure). A participant that votes `VOTE-COMMIT` is now prepared: its log entry survives crashes, and it holds all necessary locks/resources so that it can commit later on command, even if it forgets everything in volatile memory in between.

Phase 2 — Decision (the "here's what happens" round). The coordinator collects all votes.

• If every participant voted `VOTE-COMMIT`, the coordinator writes a `COMMIT` decision to its own durable log (this is the transaction's true commit point), then sends `GLOBAL-COMMIT` to all participants.
• If any participant voted `VOTE-ABORT` (or timed out), the coordinator writes `ABORT` to its log and sends `GLOBAL-ABORT` to all participants.

Each participant, upon receiving the final decision, commits or aborts its local branch, releases its locks, and sends an `ACK` back to the coordinator. Once the coordinator has all acknowledgments, it can safely discard its log record for that transaction. ```pseudocode // ---------- COORDINATOR ---------- function Coordinator_Run(transaction T, participants P[1..n]): // Phase 1: Voting for each p in P: send PREPARE(T) to p votes = {} for each p in P: v = receive_with_timeout(p, TIMEOUT) if v == TIMEOUT or v == VOTE-ABORT: votes[p] = VOTE-ABORT else: votes[p] = v // VOTE-COMMIT // Phase 2: Decision if all votes are VOTE-COMMIT: write_log(T, "COMMIT") // durable: the commit point decision = GLOBAL-COMMIT else: write_log(T, "ABORT") decision = GLOBAL-ABORT for each p in P: send decision to p acks = {} for each p in P: acks[p] = receive_with_retry(p, decision) // resend until ACKed write_log(T, "COMPLETE") // safe to garbage-collect log return decision

// ---------- PARTICIPANT ---------- function Participant_Handle(transaction T): on receive PREPARE(T): if can_commit_locally(T): write_log(T, "PREPARED") // durable, before replying reply VOTE-COMMIT state[T] = PREPARED else: write_log(T, "ABORT") reply VOTE-ABORT state[T] = ABORTED release_resources(T) on receive GLOBAL-COMMIT(T): commit_locally(T) write_log(T, "COMMITTED") release_resources(T) reply ACK on receive GLOBAL-ABORT(T): rollback_locally(T) write_log(T, "ABORTED") release_resources(T) reply ACK on timeout while state[T] == PREPARED: // THE BLOCKING WINDOW: // cannot unilaterally decide commit or abort — // must query other participants or coordinator's backup, // else wait until coordinator recovers query_other_participants_or_block(T) ``` The state machine each participant walks through is small and deliberate — it is exactly this small state space that makes correctness arguments tractable.

Message complexity. For $n$ participants, the fault-free execution of 2PC uses exactly $2n$ messages in each direction pair: $n$ `PREPARE` messages out, $n$ votes back, $n$ decision messages out, $n$ acknowledgments back — a total of $4n$ messages, or $O(n)$. This is optimal up to constant factors: any protocol that reaches a unanimous decision must, at minimum, let the coordinator hear from every participant once and inform every participant once, giving an unavoidable $\Omega(n)$ lower bound.

Latency. The protocol takes exactly two sequential round trips in the failure-free case: one for voting, one for deciding. This is the price of the "ask, then tell" structure; it cannot be collapsed to one round trip because the coordinator cannot announce the final decision before knowing every vote.

Durability / log writes. Each participant performs at least one synchronous, durable log write (`PREPARED`, before replying `VOTE-COMMIT`) and one more on receiving the final decision. The coordinator performs one durable write for the decision itself. These forced writes are what make the protocol survive individual node crashes (as opposed to only network delays) — a crashed and rebooted participant can consult its log to know it must honor a previously made promise.

Space. Each node needs $O(1)$ persistent state per in-flight transaction (its current phase and vote/decision), plus $O(n)$ transient state at the coordinator to track outstanding votes — so overall $O(n)$ per transaction system-wide, which is unavoidable since the coordinator inherently must remember something about each participant.

Correctness — the safety invariant. The central claim is: > No two participants reach different final outcomes for the same transaction. Proof sketch. The coordinator's decision is made exactly once and written durably before any `GLOBAL-COMMIT`/`GLOBAL-ABORT` message is sent. Because the coordinator only decides `COMMIT` when it has received `VOTE-COMMIT` from every participant, and every participant that has voted `VOTE-COMMIT` is contractually bound (by having written a durable `PREPARED` record) to honor whatever final decision it receives, the coordinator's single decision is the only source of truth. Even if messages are delayed, duplicated, or a participant crashes and recovers, that participant will consult its log, see it is `PREPARED`, and (upon reconnecting) ask the coordinator for the actual decision rather than inventing its own. Since the coordinator's log contains exactly one recorded decision per transaction, all participants that eventually apply a decision apply the same one. This gives agreement (safety); it does not, by itself, give termination (liveness) in all failure scenarios — that is the blocking problem below.

The blocking flaw. Suppose all participants vote `VOTE-COMMIT` and enter the `PREPARED` state, but the coordinator crashes before sending any `GLOBAL-COMMIT`/`GLOBAL-ABORT` message (or after sending it to only some participants). A prepared participant cannot safely decide on its own:

• It cannot abort, because the coordinator might have already decided `COMMIT` and told some other participant, which then committed.
• It cannot commit, because the coordinator might have decided `ABORT` (e.g., if one other participant had actually voted no, or crashed).

The only safe move is to wait for the coordinator to recover, or to query surviving participants (some 2PC variants add a "cooperative termination protocol" where participants ask each other if anyone already knows the decision — this shrinks but does not remove the uncertainty window, since if all surviving participants are still `PREPARED`, none of them can resolve the ambiguity either). During this wait, the participant typically still holds locks on the affected data, so other transactions can also stall. This is why 2PC is called a blocking protocol: a single coordinator failure at the wrong instant can suspend a subtransaction and its resource locks indefinitely, trading correctness for potentially unbounded unavailability — exactly the tension formalized abstractly in the CAP Theorem.

Why it's still correct, just not always live. Safety (agreement) holds unconditionally as long as the durability guarantees hold — logs are written before replies are sent, and logs survive crashes. What 2PC sacrifices is guaranteed termination under coordinator failure; it never sacrifices consistency. This safety-over-liveness bias is a deliberate design choice, and it is exactly the gap that later three-phase commit and full consensus protocols (like Paxos-based atomic commit) try to narrow, at the cost of extra rounds or extra assumptions about the failure model.

Consider an online order that must debit a wallet balance (Participant W) and decrement inventory stock (Participant S), coordinated by an order service (Coordinator C).

Now trace the failure case: suppose at step 4, right after C writes `COMMIT` to its log but crashes before sending any `GLOBAL-COMMIT` message.

• W and S are both stuck in `PREPARED`. They have locks held (balance frozen, stock frozen) and cannot decide locally.
• C reboots. It reads its durable log and finds `COMMIT` already recorded for this transaction — its own crash-recovery procedure resumes exactly where it left off: it re-sends `GLOBAL-COMMIT` to W and S (idempotently; participants that already committed simply re-ACK).
• W and S receive `GLOBAL-COMMIT`, apply it (or discover they already did, if they'd somehow retried), and release locks.

This shows the mechanism functioning correctly and the danger point clearly: had C's disk failed permanently at that exact moment (rather than merely rebooting), W and S would remain `PREPARED` forever unless a human operator, an external oracle, or a cooperative-termination sub-protocol intervened — this is the blocking scenario made concrete. Contrast with an abort case: suppose Participant S finds stock is zero at step 2 and replies `VOTE-ABORT`. Then at step 3, C sees not all votes are `VOTE-COMMIT`, so at step 4 it writes `ABORT` instead, and at step 5 sends `GLOBAL-ABORT` to both W and S — W, despite having voted "yes" and being fully prepared to debit the wallet, must roll back and release its lock without ever executing the debit. This is precisely why the `PREPARED` state must be reversible: preparedness is a promise of readiness, not a promise of a specific outcome.

Two-Phase Commit was formalized in the distributed database literature of the late 1970s, growing out of work on making transaction processing systems robust to network partitions and node crashes — the same era that produced foundational ideas about replicated logs and distributed consistency.

2PC and its descendants appear throughout production infrastructure. Relational databases supporting XA transactions (Oracle, PostgreSQL, MySQL with XA) use 2PC to coordinate commits across multiple database instances or across a database and a message queue. Distributed SQL systems and NewSQL databases (Google Spanner, CockroachDB, YugabyteDB) use 2PC-like commit protocols internally to make multi-shard transactions atomic, often layering it on top of a consensus protocol (like Paxos or Raft) per shard to solve exactly the blocking weakness described above — the coordinator itself becomes replicated rather than a single point of failure. Message-oriented middleware (JMS, MSMQ) and application servers implementing the Java Transaction API (JTA) use 2PC to coordinate a database write with a message send, so that "process order, then notify shipping" either both happen or neither does. Cloud storage systems and distributed file systems use atomic commit protocols for multi-object metadata updates. Even outside databases, the conceptual pattern — collect votes, then broadcast a binding decision — recurs in configuration management and orchestration systems that must roll out a change to many machines atomically. Understanding 2PC's blocking limitation is also the natural on-ramp to appreciating why systems facing malicious or arbitrarily faulty nodes need the stronger guarantees studied under the Byzantine Generals Problem.

Ask the tutor: How would you redesign 2PC's coordinator using a consensus protocol like Raft to eliminate its single point of failure?