Two-Phase Commit (2PC) for Distributed Transactions

Distributed transactions are fundamental to distributed systems. Coordinating multiple autonomous nodes to agree on committing or aborting a transaction is notoriously challenging. When updating data across multiple independent storage engines or microservices, the system must guarantee atomicity: either every node applies the update, or every node discards it.

The Two-Phase Commit (2PC) protocol is an atomic commitment protocol designed to achieve unanimous agreement across distributed nodes while preventing data from settling into an inconsistent state.

---

The Distributed Transaction Problem

Consider a distributed database cluster consisting of three nodes: $N_1$, $N_2$, and $N_3$. A client issues a write operation:

$\text{PUT } k = 10$

For this transaction to be successful, the write must be committed durably across all three nodes. If even a single node fails, rejects the write, or encounters a constraint violation, the transaction must abort globally. Allowing partial writes compromises the safety properties of the database, yielding divergent state across nodes.

          +-----------------------------------------+
          |          Client: PUT k = 10             |
          +-------------------+---------------------+
                              |
         +--------------------+--------------------+
         |                    |                    |
         v                    v                    v
    +---------+          +---------+          +---------+
    | Node 1  |          | Node 2  |          | Node 3  |
    | [Write] |          | [Write] |          | [FAIL?] |
    +---------+          +---------+          +---------+

To ensure consistency, nodes must participate in a coordinated protocol that guarantees unanimous, uniform execution.

---

Core Protocol Assumptions

Before analyzing 2PC, we establish the underlying system model and assumptions:

1. No Message Loss: The communication layer is reliable. If Node $A$ sends a message to Node $B$, the message is delivered. Underlying transport protocols like TCP handle retransmissions. Transient network disconnects can trigger retries, but silent packet drops without detection do not occur.
2. Crash-Recovery Process Model: Individual participant nodes or the coordinator can crash unexpectedly at any stage of execution. Despite crashes, the protocol must prevent divergent decisions.
3. Fully Connected Network Topology: The network graph is complete. Every node knows about and can communicate directly with every other node in the cluster.
4. Uniformity and Unanimity: No two processes can decide on contradictory outcomes. If one node commits, all must commit; if one node aborts, all must abort.

---

Protocol Architecture and Execution Phases

Let a cluster consist of $n$ processes (databases, partitions, or services). One distinguished process acts as the Coordinator (denoted as $A$), while the remaining $n - 1$ processes act as Participants (e.g., $B, C, D$).

The coordinator can be elected via a leader election algorithm, designated statically, or selected as the primary node that accepted the initial client write.

sequenceDiagram
    autonumber
    participant C as Coordinator (Node A)
    participant P1 as Participant (Node B)
    participant P2 as Participant (Node C)

    Note over C, P2: Phase 1: Prepare Phase
    C->>P1: Prepare / Can you commit?
    C->>P2: Prepare / Can you commit?
    P1-->>C: Vote YES (Commit)
    P2-->>C: Vote YES (Commit)

    Note over C, P2: Phase 2: Commit Phase
    C->>P1: Global Commit
    C->>P2: Global Commit
    P1-->>C: Acknowledged
    P2-->>C: Acknowledged

Phase 1: The Prepare Phase (Voting Phase)

1. Prepare Request: The coordinator sends a Prepare message to all participants asking: “Can you commit this transaction?”
2. Local Evaluation: Each participant verifies whether it can safely commit the transaction (e.g., acquiring necessary locks, verifying data integrity constraints, writing changes to a Write-Ahead Log (WAL)).
3. Vote Dispatch:
   • If the participant can guarantee a commit, it votes YES.
   • If the participant encounters an issue or constraint failure, it votes NO (Abort).
   • If the coordinator does not receive a response from a participant within a predefined timeout, it assumes a default vote of NO.
4. Decision Synthesis: The coordinator gathers all votes along with its own local decision:
   • Global Commit: Chosen if and only if every participant votes YES.
   • Global Abort: Chosen if at least one participant votes NO or fails to respond.

Phase 2: The Commit Phase (Decision Phase)

1. Broadcasting Decision: The coordinator broadcasts the global decision (GLOBAL_COMMIT or GLOBAL_ABORT) to all participants.
2. Local Execution:
   • On receiving GLOBAL_COMMIT, participants apply changes, release locks, and persist the final state.
   • On receiving GLOBAL_ABORT, participants roll back local uncommitted changes and release locks.
3. Participant Compliance: Even if a participant crashed or failed to vote in Phase 1, it must strictly honor the global decision transmitted by the coordinator in Phase 2.

---

Complexity Analysis

For a network containing $n$ nodes ($1$ coordinator and $n-1$ participants):

Time Complexity

• The protocol completes in $2$ rounds of network communication:
  • Round 1: Voting (Coordinator queries participants; participants reply).
  • Round 2: Commit/Abort Broadcast (Coordinator transmits outcome; participants confirm).

Communication / Message Complexity

• Phase 1: Coordinator contacts $n - 1$ participants, and $n - 1$ participants respond $\rightarrow 2(n - 1)$ messages.
• Phase 2: Coordinator broadcasts decision to $n - 1$ participants $\rightarrow n - 1$ messages (excluding optional acks).
• Total Message Complexity: $\mathcal{O}(n)$, specifically bounded by $2(n - 1) + (n - 1)$ without acks, or $4(n - 1)$ with end-to-end participant confirmations.

---

Failure Scenarios and Edge Cases

While conceptually straightforward, 2PC is vulnerable to network and process failures. Because nodes must block while awaiting missing state, 2PC is formally classified as a blocking protocol.

                     +--------------------------+
                     | 2PC Failure Scenarios    |
                     +-------------+------------+
                                   |
        +--------------------------+--------------------------+
        |                          |                          |
        v                          v                          v
+------------------+      +------------------+      +------------------+
| Case 1 & 2:      |      | Case 3 & 4:      |      | Case 5:          |
| Coordinator dies |      | Participant dies |      | Coordinator AND  |
| (Pre/Mid Phase 1)|      | (Phase 1 vs 2)   |      | Participant die  |
+------------------+      +------------------+      +------------------+

Case 1: Coordinator Fails Before Initiating Phase 1

• Symptom: The coordinator crashes before dispatching any Prepare messages.
• Impact: Low. No participant has prepared or locked state. Consensus never started.
• Resolution: The cluster detects the coordinator failure via heartbeats, elects a new coordinator, and the client retries the transaction.

Case 2: Coordinator Fails After Initiating Phase 1

• Symptom: The coordinator crashes after sending Prepare requests and receiving votes from some participants (e.g., $B$ and $C$), but before broadcasting a global decision.
• Impact: Severe blocking. Participants that responded YES have locked their resources and are waiting for the coordinator’s final verdict.
• Resolution: Without timeout mechanisms or a recovery protocol, participants remain blocked indefinitely. If participants simply abort on timeout, they risk inconsistency if the coordinator had already decided to commit and sent that decision to a subset of nodes.

Case 3: Participant Crashes Before Sending Its Vote in Phase 1

• Symptom: Coordinator requests votes from $B, C, D$. Nodes $B$ and $C$ reply, but $D$ crashes before responding.
• Impact: The coordinator is blocked waiting for $D$‘s vote.
• Resolution: The coordinator implements a timeout. Once the timeout expires, the coordinator treats the missing vote from $D$ as a NO, decides on GLOBAL_ABORT, and broadcasts the abort message to $B$ and $C$.

Case 4: Participant Crashes During Phase 2

• Symptom: The coordinator broadcasts GLOBAL_COMMIT, but participant $D$ crashes before or while applying the commit.
• Impact: The coordinator cannot determine whether $D$ crashed before or after applying the local commit.
• Resolution: Participants must use a persistent Write-Ahead Log (WAL) on disk. When $D$ recovers, it reads its WAL, queries the coordinator or peer nodes for the transaction outcome, and safely replays or discards the transaction.

Case 5: Coordinator and a Participant Crash Simultaneously in Phase 2

• Symptom: The coordinator begins Phase 2 by broadcasting the decision sequentially. It delivers GLOBAL_COMMIT to participant $B$. Before it can send the message to $C$ and $D$, both the coordinator and participant $B$ crash.
• Impact: Catastrophic system halt.
  • Surviving nodes ($C$ and $D$) voted YES in Phase 1, but never received the Phase 2 decision.
  • Neither $C$ nor $D$ knows whether the coordinator decided to commit or abort.
  • The only node that knew the decision ($B$) is dead.
• Resolution: Surviving participants cannot elect a new coordinator to proceed safely because doing so could cause an inconsistency (e.g., electing to abort while $B$ already committed locally). The remaining nodes are blocked until either the coordinator or participant $B$ recovers.

---

Why Two-Phase Commit is a “Blocking Protocol”

2PC guarantees Safety (no two nodes make conflicting decisions), but sacrifices Liveness in the presence of specific crash patterns.

When a coordinator crashes after participants have voted YES, participants cannot independently deduce the global state. They must hold transactional locks indefinitely until the coordinator recovers. This phenomenon can cause cascading resource starvation throughout a high-throughput distributed database.

To mitigate these blocking characteristics, non-blocking protocols such as Three-Phase Commit (3PC) and consensus protocols like Raft and Paxos decouple transaction progress from a single point of failure by relying on quorum-based state replication.

---

Summary of Trade-offs

Feature	Two-Phase Commit (2PC)
Rounds of Communication	2 Rounds (Prepare + Commit)
Message Complexity	$\mathcal{O}(n)$ (typically $3n - 3$ to $4n - 4$)
Consistency Guarantee	Strong Consistency (Atomic execution across all nodes)
Liveness Guarantee	Weak (Vulnerable to blocking during coordinator failures)
Primary Bottleneck	Resource locking during participant uncertainty window