The Consensus Problem

The checkpoint ended with a monster in the doorway: a fleet of unreliable machines, on lying clocks, must sometimes produce one answer it will never take back. Everything so far either tolerated disagreement (keep both, concurrent, k-sorted) or funneled the decision through one door and hoped the door held. This section walks through the doorway.

And it's been coming since the very first lesson. Welcome to Hard Mode ended its opening argument with a sentence this course has been paying interest on ever since: no node can trust its own judgment, so truth must be agreed by a majority — that single fact forces consensus. Today the debt comes due. This lesson defines the problem precisely, lets you break every obvious solution with your own hands, and shows you the theorem that explains why your hands never had a chance. The machinery that actually works comes next; it will make far more sense once you've personally dug both of the graves it was built to avoid.

First, the recognition skill, because this problem almost never introduces itself by name.

• Who is the leader? A promotion after a failover is a decision that must not be made twice: you watched two kings crowned in Network Partitions & Split Brain, and now you can name what actually failed there: agreement.
• Did the transaction commit? Commit or abort — pick one, forever, on every machine.
• Who holds the lock? One holder at a time is a decision, renewed continuously.
• What is the current config? Which machines are even in the cluster. Change that twice, divergently, and both halves happily run different worlds.
• Did the irreversible thing happen? The email sent, the payment captured, the ticket sold: “exactly once” is a decision wearing delivery clothes.

One problem in five costumes: several machines, each with an opinion, must settle on one value — while any of them can die mid-sentence. If a system ever answers one of these questions twice, it never really answered it. And the sharpest version of the skill is spotting the disguise in your own architecture: every hand-rolled failover script, every “the cron job picks a winner”, every “we just use a database flag” is a consensus protocol — usually one of the three doomed ones you're about to break.

Consensus has a precise contract, and its teeth are in how little it asks:

1. Agreement. No two machines ever decide different values. Not “rarely” — never. This is the never-taken-back part.
2. Validity. The decision was actually proposed by someone. A protocol that always decides “nobody gets the ticket” satisfies agreement beautifully and is useless.
3. Termination. Every machine that keeps running eventually decides. An answer someday isn't optional; it's the whole point of asking.

Two promises are about being right; one is about ever finishing. Hold that split in view, because the entire drama of this section (the theorem, the timeouts, the machinery in the coming lessons) lives in the tension between them. Being safe means never producing two answers. Being live means producing one at all. On a network where dead is indistinguishable from slow, those two pull in opposite directions, and the figure's cracked pillar is exactly where the strain concentrates.

Before the theory, honor the instincts. Everyone who meets this problem invents the same three solutions in the same order, and each one deserves to be taken seriously — they all work, right up until the failure they can't survive.

Idea one: appoint a dictator. One node decides; everyone else asks it. Clean, fast, unambiguous: it's the single-writer rung from the ordering toolbox, and it really is a total order. Its grave: the dictator dies holding the pen. Now nobody may decide (you wait), or somebody stands in (you risk two answers when the dictator wakes with the old one still queued).

Idea two: first proposal wins. No boss: whoever shouts first, wins; flood the value everywhere. Its grave: “first” is exactly the word the last stretch spent five lessons burying. Cut the network and each half hears a different first; heal it and you hold two irreversible answers, each fully committed.

Idea three: majority vote, retry on timeout. Warmer: majorities can't split, as the tiebreak from the split-brain lesson already taught. But naive voting has a fatal habit: when a round stalls (a voter paused, a message slow), the natural move is “time out and vote again”. Votes get re-cast. And two overlapping attempts can each assemble a majority from different mixtures of old and new votes — two majorities, two answers, both “proven”.

Don't take my word for any of this. The lab below hands you all three, plus the faults.

One ticket. Two buyers — Ana and Raj. Three machines that must decide who gets it, once, forever. Two lamps to keep lit: SAFETY (one answer, ever) and LIVENESS (an answer, eventually).

Try this first: pick the dictator, let Ana buy, and watch it work perfectly. Reset, and this time kill the dictator mid-decision. The cluster hangs; the liveness lamp goes out. Press “ask a stand-in” to force progress, then wake the dictator — it finishes the decision it was holding, and the safety lamp shatters: ticket sold twice.

Then first wins: cut the cluster, let Ana buy on one side and Raj on the other, heal, then read the ledger. Two committed answers, no one at fault, nothing to merge: “decided” means never taken back, and both sides decided.

Finally the subtle one, vote + retry: pause a voter mid-round, let the timeout trigger a re-vote, wake the voter, and watch its stale ballot complete one majority while the fresh votes complete another. Count the votes yourself; both tallies are real. A majority means nothing if votes can be re-cast without round numbers.

Every path you can find ends in one of two graves: stuck forever or two answers. That's not the lab being rigged — that's the problem being the problem. The next section names it.

In 1985, Fischer, Lynch, and Paterson published Impossibility of Distributed Consensus with One Faulty Process — a paper short enough to read in an evening and heavy enough to win the Dijkstra Prize. Its result, in one honest paragraph:

In a fully asynchronous system — no bounds on message delay, which is to say no trustworthy timeouts — no deterministic protocol can guarantee agreement, validity, and termination if even one machine may crash. The root is the oldest fact in this course: dead is indistinguishable from slow. At some point every protocol's decision hangs on a message from a machine that has gone silent, and there are only two moves. Wait for it, and maybe wait forever, because it's dead: termination lost. Or decide without it, and maybe it was only slow, and its late vote completes a second, different majority: agreement lost. The lab didn't rig your defeats; it walked you down both tines of this fork.

Now the part that keeps FLP from being a counsel of despair. It bounds the fully asynchronous model with deterministic protocols and guaranteed termination. Real systems slip the noose by weakening exactly one word: they choose safety always, liveness usually. Never two answers, under any weather — but during a bad partition or a storm of false timeouts, decisions may stall. Timeouts (guesses, as the failure-detection lesson priced them) and a little randomness make stalls vanishingly rare in practice. That's the engineering posture every tool in the coming lessons adopts, and now you know it's not a hack. It's the only deal the mathematics offers.

One famous protocol deserves a paragraph now, because it looks like the answer and interviews love the distinction. Two-phase commit: a coordinator asks every participant to prepare (each locks up and promises it could commit), then announces the verdict. Clean — and not fault-tolerant consensus. Watch the chairman faint: the coordinator dies after everyone prepared, before anyone heard the verdict. Every participant is now locked, unable to commit (the verdict might have been abort) and unable to abort (the verdict might have been commit, and might already be on the coordinator's disk). They block, holding locks, until the chairman is revived. One machine's death froze the committee: exactly the dictator's grave, wearing a protocol's clothes.

Two-phase commit solves atomic commitment, everyone-or-no-one; the data systems course gives its mechanics their due. What it doesn't solve is surviving the decider. Mature systems keep 2PC for coordinating the work and put the verdict itself under real consensus, so the chairman's memory outlives the chairman.

• Consensus = one value, agreed, despite failures. Three promises: agreement (never two answers), validity (a proposed answer), termination (an answer at all). Never-taken-back is the whole game.
• You meet it in disguise: leader election, commit/abort, locks, membership, “exactly once”. If you answered twice, you never answered. Every hand-rolled failover script is a consensus protocol — usually a doomed one.
• The three obvious ideas dig two graves. Dictator: stuck, then double-sold. First wins: a partition makes two firsts. Vote + retry: re-cast votes assemble two majorities. Stuck forever, or two answers.
• FLP names the fork: fully async + one possible crash means no deterministic protocol guarantees all three promises, because dead is indistinguishable from slow. Real systems take the only deal on offer: safety always, liveness usually.
• 2PC is not the escape. Atomic commitment with a blocking chairman; the verdict itself needs consensus.

But notice what survived every wreck in the lab: the minority side never decided anything. The one ingredient that never betrayed you is the one this course has trusted twice already: in the split-brain tiebreak, and in the quorum reads and writes of the data course. Majorities cannot split. Why that's true, why it's almost enough, and exactly what's still missing — that's next: Quorum Intuition, Revisited.