Commentary: two-phase-commit

Kill the coordinator at every step of the protocol and count. The transaction that succeeds blocks the cluster on 10 of 25 crash timings; the one that gets vetoed blocks on 0 of 23. The dangerous path is the happy path. A study guide for tpc.py.

cd two-phase-commit
python3 demo.py                    # the crash sweep and the boundary (§6)
python3 -m unittest test_tpc -v    # 27 tests, pinning every number here

1. Orientation

This is two-phase commit: a coordinator asks every participant to prepare, collects a unanimous vote, and broadcasts commit or abort. The toy runs it as an explicit, numbered message schedule with no threads, no sockets and no clock, which is what makes the central experiment possible — killing the coordinator at every single step of the protocol and counting what the survivors can work out.

No dependencies, no installation, no network.

By the end you should be able to:

• say precisely which window of the protocol is dangerous, and why it opens earlier than almost everyone guesses;
• explain why a timeout cannot rescue a blocked participant — not "is hard to tune", cannot;
• predict which of the two transactions in the demo is the risky one, and be right for the right reason;
• name the one line of code that decides it.

2. The problem this mechanism exists to solve

You have one transaction spanning two databases. You need both to commit or neither. The obvious approach — commit the first, then the second — fails at the obvious place: the second one refuses, and the first is already durable.

2PC's move is to split committing into two steps and buy a point of no return. In the first phase every participant is asked to prepare: force undo/redo to disk, take the locks, and guarantee it can commit later. The participant answers YES, and in doing so gives away its right to abort unilaterally. That surrender is the entire protocol. Everything 2PC gets and everything it costs comes from that one exchange.

The competing goals that make more than one design defensible:

• Atomicity — all or nothing, across nodes that fail independently.
• Liveness — the system keeps making progress through failures.
• Latency and lock hold time — participants sit prepared, holding locks, for at least one round trip while nobody else can touch those rows.

You cannot have all three. 2PC picks atomicity and lock-holding, and gives up liveness: it is a blocking protocol. It is never wrong, and it can stop forever. That trade is not a bug or an oversight in the design; this page measures its exact size, and then measures what the famous alternatives actually buy.

3. Background you need

The three flagged ⚑ carry the result. The rest is plumbing.

4. The mental model

The window does not open when the coordinator decides. It opens as soon as the last participant has entered PREPARED, which happens well before any vote comes back — and that is the part almost everyone gets wrong. §6 measures where it actually opens.

5. Reading the source

5.1 step — why a crash can land anywhere

def step(self):
    """Execute exactly one event, and return its one-line description."""
    kind, m = self.q.popleft()
    tag = f"{m['src']}->{m['dst']} {m['kind']:8}{self._payload(m)}"
    if kind == "SEND":
        if self.alive[m["src"]]:
            self.q.append(("DELIVER", m))
            desc = f"SEND    {tag}"
        else:
            desc = f"SEND    {tag} NEVER SENT (sender dead)"
    elif self.alive[m["dst"]]:
        for out in getattr(self.nodes[m["dst"]], "on_" + m["kind"])(m):
            self.q.append(("SEND", out))
        desc = f"DELIVER {tag}"
    else:
        desc = f"DELIVER {tag} DROPPED (receiver dead)"
    self.trace.append(desc.rstrip())
    return desc.rstrip()

The decision to split SEND from DELIVER is the one that makes this toy work at all. A message moves in two events: the sender hands it to the network, and later the receiver's handler runs. If instead a handler atomically emitted all of its outbound messages — the obvious design — then "the coordinator decided, forced commit to its log, and died before transmitting a single copy" would be unreachable, because the decision and all three broadcasts would happen in one indivisible step. That is exactly the state the entire protocol's reputation rests on. The model has to be able to express the bug you are studying.

The asymmetry in the two dead-node branches matters too. A SEND by a dead node never happens; a DELIVER to a dead node is dropped. But a message the coordinator already sent before dying stays in the queue and is delivered — which is why the blocked window closes at step 13 rather than 16.

5.2 on_prepare — where the right to abort is surrendered

def on_prepare(self, m):
    if self.vote == "no":
        # THE line the one-NO result lives on. A NO voter never enters the
        # uncertainty period at all: it knows the outcome by itself, so it
        # aborts here and stays a live oracle for everybody else.
        self.state = ABORTED
        self.log.append("abort")
        return [dict(src=self.id, dst=C, kind="vote", vote="no")]
    self.state = PREPARED
    self.locks = 1
    self.log.append("prepare")  # forced BEFORE the reply goes out
    return [dict(src=self.id, dst=C, kind="vote", vote="yes")]

Two branches that look symmetrical and are not, in the way that decides the whole page.

The NO voter skips the uncertainty period entirely. It does not need anyone's permission to abort — a single NO makes the outcome abort no matter what anybody else says, so it can write its log record and release its locks immediately. It ends up ABORTED, alive, and certain. That makes it a live oracle: any peer that asks it gets a real answer.

The YES voter does the opposite. It takes locks, forces prepare, and enters a state from which it can neither advance nor retreat without being told. The ordering on that line is load-bearing in the ordinary durability sense — force the record then reply, because a crash between the two must not leave a promise the participant has forgotten making.

The on_prepare NO branch is the single line this toy's headline result turns on. §6 measures what happens when you change it.

5.3 on_vote — one node, one moment

def on_vote(self, m):
    if self.state != "collecting":
        return []
    self.votes[m["src"]] = m["vote"]
    if len(self.votes) < len(self.pids):
        return []               # unanimity required, so one NO is enough
    d = "commit" if all(v == "yes" for v in self.votes.values()) else "abort"
    self.state = COMMITTED if d == "commit" else ABORTED
    self.log.append(d)          # the decision record, forced to stable store
    return [dict(src=C, dst=p, kind="decision", decision=d) for p in self.pids]

The coordinator waits for every vote, then decides once. Note what this makes true: between self.log.append(d) and the delivery of the first decision message, the outcome of the transaction exists in exactly one place on Earth. Every participant is prepared and knows nothing. That is not an unlucky interleaving — it is a mandatory phase that every 2PC transaction passes through, every time.

5.4 terminate — the best the survivors can do

def terminate(self):
    """The cooperative termination protocol (Bernstein, Hadzilacos and
    Goodman s7.4): an uncertain participant asks every live peer what it
    knows, and the group resolves if ANY peer is outside the uncertainty
    period.

    Returns "commit", "abort", or "BLOCKED" -- the last meaning every live
    participant is uncertain, so the group's uncertainty set is still
    {commit, abort} and no rule can pick between them.
    """
    live = [p for p in self.parts.values() if self.alive[p.id]]
    known = None
    for p in live:
        if p.state == COMMITTED:
            known = "commit"
        elif p.state == ABORTED and known != "commit":
            known = "abort"
        elif p.state == INIT and known is None:
            known = "abort"     # it never voted, so commit was impossible
    if known is None:
        return "BLOCKED"
    for p in live:
        p.on_decision(dict(decision=known))
    return known

This is the smartest thing the survivors can legally do, and it is worth being clear that it is genuinely smart — it is not a strawman. It rescues every situation where any live participant sits outside the uncertainty period, in either direction:

• a peer that already committed proves the decision was commit;
• a peer that already aborted proves it was abort;
• a peer still in INIT never voted, and the coordinator requires unanimity, so commit was impossible. Abort is safe. This clause is worth three crash timings on its own (§6).

return "BLOCKED" is the honest branch. When every live participant is uncertain, the group's uncertainty set is still {commit, abort}, and the function does not guess. A protocol that guesses here is a different protocol with different guarantees, which §6 also measures.

5.5 run_crash_at — the experiment harness

def run_crash_at(votes, k, recovery="terminate", heuristic="abort"):
    """Run the schedule, crash the coordinator immediately after step `k`,
    drain whatever is still in flight, then recover. `k=0` means it died
    before doing anything at all. `recovery="none"` freezes the cluster
    exactly as the crash left it, for inspection."""
    s = Sim(votes)
    for _ in range(k):
        if not s.q:
            break
        s.step()
    s.crash(C)
    s.run()
    if recovery == "terminate":
        return s, s.terminate()
    if recovery == "unilateral":
        s.unilateral(heuristic)
        return s, None
    if recovery == "none":
        return s, None
    raise ValueError(recovery)

Because the schedule is deterministic, k is a complete description of a failure scenario. There is no "run it a thousand times and see" here and no RNG to seed: the sweep in §6 is exhaustive over crash timings, so "40% of crash timings block" is a count, not an estimate.

6. The demo, and what it proves

6.1 A clean run

24 steps, so 25 distinct crash timings: k=0 (died before sending anything) through k=24.

6.2 The sweep

Kill the coordinator after each step in turn. The all-YES table, k=0 through k=14 (the remaining rows are all commit):

And the headline:

The transaction that succeeds is the one that can hang the cluster. The transaction that gets vetoed cannot, ever.

6.3 The arithmetic

Never leave a headline number underived, so:

• k=0,1,2 — not every prepare has been handed to the network, so at least one participant is still INIT. It never voted; the coordinator requires unanimity; commit was therefore impossible and abort is provably safe. 3 timings, resolved.
• k=3..12 — every participant is PREPARED and none has heard a decision. 10 timings, blocked.
• k=13..24 — at least one decision message was already handed to the network before the crash, so it still gets delivered; the peer query finds that participant and the group resolves. 12 timings, resolved.

3 + 10 + 12 = 25. ✓ 10/25 = 40.0%.

Look at where the window opens: step 3, the moment the last prepare is handed to the network — before a single vote has come back, and nine steps before the coordinator decides anything. The intuition that the danger is a narrow race around the decision broadcast is wrong by most of the protocol. The dangerous window is essentially the entire voting phase.

6.4 Why waiting cannot help

The reflex is that a timeout fixes this. It cannot, and the demo shows why by finding two runs a participant cannot tell apart. Both are searched for, not assumed — and both land at k=12:

Byte-identical local state; opposite correct answers. A timer carries no information about which world you are in, so it cannot separate them. However long P1 waits, whichever way it eventually jumps, there is a world with exactly its state where that jump is wrong. demo.py asserts the equality so the claim cannot rot.

And the peers add nothing:

All three are in the identical position. Asking every peer returns your own uncertainty back, once per peer. The deciding bit is not in the cluster.

6.5 What the locks are protecting: nothing, nine times out of ten

Three locks are held in all ten blocked timings. But in nine of the ten the coordinator had not decided anything at all — nothing was committed, and abort was legal the entire time. The cluster freezes all ten times regardless, because from the inside those nine are indistinguishable from the one. This is the sharpest thing the sweep shows: the cost is paid on every crash in the window, and the outcome being protected exists in one case out of ten.

6.6 The counterfactual: refuse to block

Rip out the peer query and let each uncertain participant guess when its timer fires.

("SPLIT" = participants disagree with each other. "STALE" = they agree, but opposite to the decision the coordinator forced and will hand out on restart.)

The split-brain, step by step:

Two adjacent steps decide whether the database is consistent. At k=13 the coordinator got one commit onto the wire before dying: P1 commits, P2 and P3 time out and roll back. Half the transaction is durable and half is gone, and nothing anywhere reports an error.

So presumed-abort is not a fix. It is a decision to be wrong 3/25 of the time instead of stuck 10/25 of the time. That is the real trade, and it is the one every production transaction manager has to make.

6.7 Which lines are load-bearing

Each variant was applied to the shipped module and re-run against the identical sweep.

CF1 is the one. Move a NO voter into the uncertainty period like everyone else — three lines, no change to any message — and the vetoed transaction goes from never blocking to blocking exactly as often as the successful one. The immunity was never about the abort outcome. It was about there being one participant left alive who never gave up its certainty.

6.8 Roads not taken, measured: does 3PC fix it?

Three-phase commit adds a pre-commit round precisely to destroy the state that blocks 2PC. It works, on the failure this page has been studying:

Then partition the participants and run the identical sweep:

3PC's four violations all occur where one participant reached precommitted and the others are still merely prepared: the minority side sees "everyone uncertain, so abort", the majority side sees a pre-commit and commits.

3PC is not a fix. It moves the failure out of the liveness column and into the safety column — and a silent atomicity violation is a considerably worse outcome than a stuck transaction you can page someone about. This is why 3PC is famous and essentially unused, and why the modern answer is to replicate the coordinator with a consensus protocol instead (see raft-toy). Gray and Lamport put it best: two-phase commit is the trivial version of Paxos Commit that tolerates zero faults.

6.9 The boundary: where the effect vanishes

Not with cluster size. The closed form is exact and demo.py asserts it for every N:

steps = 8N, blocked = 3N+1, so the fraction is (3N+1)/(8N+1), which falls to 3/8 = 37.5% and stays. Adding participants makes it very slightly better and never fixes it. You cannot size your way out.

It is the vote, and it is a cliff. At N=5, varying how many participants veto:

Zero vetoes blocks 16 of 41 timings. One veto blocks zero. So does two, three, four, five. There is no gradient — one veto is the entire boundary, because one veto is enough to leave a certain participant alive.

So: place your own system by asking not "how many nodes do I have" but "is there any live participant that never entered the uncertainty period?" If yes, you are fine. If no, you are one coordinator crash from a stuck transaction, and no amount of hardware helps.

7. Design decisions and roads not taken

Coordinator crashes only. Participant crashes are the other half of the real failure space and they are deliberately absent. Coordinator-only failure already produces the result, and adding participant failures turns one sweep into a combinatorial one that the LOC budget cannot pay for. The cost of this choice is honest to name: with participant failures, cooperative termination gets worse, because the one live certain peer that rescues the one-NO case can itself be the node that died. The 0% floor in the boundary table is the best case, not the general one.

No coordinator restart. A recovering coordinator with an intact log resolves every blocked timing. Leaving it out is the point: it converts "blocked forever" into "blocked for the duration of the outage", which is a real mitigation and not a solution, and the transaction is stuck holding locks either way. Making recovery visible would also have needed a persistence layer the toy does not otherwise want.

No RNG, no clock, no threads. Other designs would have used a random message scheduler and sampled. Determinism buys the thing that actually matters here: k is a complete description of a scenario, so the sweep is exhaustive and the headline is a count rather than an estimate. Nothing needs seeding because nothing is random.

Unanimity checked with all(), not a quorum. 2PC is not a voting protocol in the quorum sense and it is worth not blurring: any single NO decides the outcome. Quorums appear when the coordinator is replicated, which is Paxos/Raft Commit and a different toy.

terminate() returns a string rather than raising. "BLOCKED" is a legitimate protocol outcome, not an error condition, and the sweep needs to count it. Making it an exception would have implied that being stuck is a malfunction, when it is the specified behaviour.

8. What's simplified vs. the real thing

• Locks are an integer. self.locks = 1 stands in for a real lock manager holding row and index locks. The production consequence is what the Postgres docs warn about directly: a dangling prepared transaction "continues to hold whatever locks it held", blocks VACUUM from reclaiming storage, and in the extreme can force a shutdown to prevent transaction ID wraparound. Postgres ships max_prepared_transactions = 0 by default for this reason.
• The log is a Python list. No fsync, no log sequence numbers, no recovery pass. The ordering it demonstrates (force, then reply) is the part that transfers; see wal-kv for what durability actually costs.
• No timeouts anywhere. Real participants time out and then run exactly the decision this toy makes explicit in terminate() versus unilateral(). Removing the timer makes the choice visible rather than tuning-dependent — and the §6 result is precisely that the timer's duration is irrelevant.
• One transaction, no concurrency. Real transaction managers run thousands concurrently, which is where the second-order cost lands: a blocked transaction's locks stall unrelated transactions that touch the same rows, so one stuck coordinator degrades throughput far beyond the one transaction involved. Abadi calls this the cloggage problem.
• The network only drops, never reorders or duplicates. Reordering would not change the result — on_decision is already idempotent, which is a real requirement, not a convenience.
• Participants are trusted. No Byzantine behaviour, no authentication, no heuristic-resolution audit trail. Real XA implementations log heuristic decisions specifically so a human can find the split-brain afterwards, which tells you how routinely it happens.

9. Check yourself

10. Further reading

• Bernstein, Hadzilacos & Goodman, Concurrency Control and Recovery in Database Systems — the standard treatment, free from Microsoft Research (a .zip of per-chapter PDFs). Chapter 7 is the one: the uncertainty period, cooperative termination and the 3PC analysis all come from here, and §7.4 is what Sim.terminate() implements.
• Gray & Lamport, Consensus on Transaction Commit — the paper that reframes the whole problem: two-phase commit is the trivial version of Paxos Commit that tolerates zero faults. Read this immediately after the 3PC table in §6.8; it explains why replicating the coordinator, not adding rounds, is the answer.
• Abadi, It's Time to Move on from Two Phase Commit — states the blocking window in one sentence ("every worker has voted 'yes', but the coordinator fails before sending a message with the final decision to at least one worker") and then makes the argument this toy does not: that the cloggage cost on unrelated transactions is the bigger problem.
• PostgreSQL, PREPARE TRANSACTION — 2PC as a real feature you can type. The Caution section is this entire page in one paragraph, including why max_prepared_transactions defaults to zero.
• Jepsen, Consistency Models — for placing atomic commit next to the consistency properties it is often confused with. Useful background; it does not cover commit protocols directly.

Next in this repo: raft-toy — replicating the coordinator so that losing it is survivable, which is the real answer to everything above.