Paxos, the Intuition

The last lesson closed with a debt: "why it's legendary, why the mathematics earned twenty years of awe, and why it still lost the popularity war — that story is next." Here is that story, and it's a strange one. It involves a fictional Greek island, a computer scientist lecturing in an Indiana Jones costume, a paper rejected for being too funny, and an algorithm that ran the world's most critical infrastructure for two decades while most of the engineers operating it couldn't explain how it worked.

The algorithm is Paxos, and you're meeting it last for a reason. Every lesson in this section has quietly been building its vocabulary: one answer never taken back, majorities that cannot avoid overlapping, numbered rounds, an owner per round. Raft arranged those parts into a machine designed to be understood. Paxos is where the parts were discovered, in 1989, before any of them had names.

So this lesson runs the course's usual direction in reverse. You already own the modern machine. Now you get to appreciate the original: smaller than Raft, stranger than Raft, harder to operate than Raft, and in one specific way more general than anything that came after it. By the end you'll know the two round trips, the one rule that makes them safe, the failure mode that makes them frustrating, and the honest answer to the question every interviewer eventually asks: if Raft and Paxos solve the same problem, why do both exist?

Strip consensus down to its smallest possible form. Not a log of commands, not a stream of decisions — just this: some machines propose values, and the group must choose exactly one, forever. Once chosen, never changed, never taken back. Computer scientists call this single-decree consensus: one slot, one decision. It's the atom everything else is built from; a replicated log is just this atom repeated slot after slot.

Two kinds of participants play. Proposers push candidate values: think of the machines that each want their configuration, their winner, their answer. Acceptors are the memory of the group: five of them, say, each keeping a little ledger. A value is chosen the moment a majority of acceptors have accepted it. Majority, for exactly the reason you proved two lessons ago: any two majorities of the same five must share a member.

Now try to design the acceptor's rule yourself, because the two obvious answers both fail, and the way they fail is the whole lesson.

Attempt one: accept the first value you hear, refuse everything after. Safe — nothing chosen can ever be unchosen, because nothing changes. But run three proposers at once and the five ledgers split two, two, one. No majority, no choice, and every acceptor's ears are now permanently closed. The parliament deadlocks on its first morning. So acceptors must be allowed to accept newer proposals.

Attempt two: accept whatever's newest. Live, certainly. But now watch the sin happen: three of five accept pizza (chosen, a majority, dinner is decided) and then a slow proposer wanders in with sushi, and three ledgers flip. The group just took back an answer. That's not a bug to patch; that's the one thing the whole section forbids.

Hold both failures in your head at once, because Paxos lives exactly in the squeeze between them: acceptors must keep saying yes to new proposals and a chosen value must never change. The escape is one of the loveliest moves in computer science: make the new proposal carry the old value. Don't block the latecomer. Recruit it.

Here's the machinery that pulls it off. Every proposal gets a ballot number — unique, totally ordered, ever-rising. The classic trick for uniqueness: proposers draw from disjoint pools, one takes odd numbers, another takes even, so nobody ever reuses a number. You've seen this species of number twice now — the fencing token, the term — and here is its ancestor, nine years older than both.

A proposal then takes two round trips.

Trip one — prepare. The proposer picks a fresh ballot number n and asks every acceptor: may I? An acceptor that hasn't seen anything higher answers with a promise, and the promise does two jobs at once:

• A gag order on the past: I will ignore every ballot smaller than n from now on.
• A confession about the past: and here is the newest value I have already accepted, if I ever accepted one.

Trip two — accept. Once a majority has promised, the proposer sends its value with accept(n, v). But it is not free to choose v, and this is the entire algorithm. If any promise confessed an accepted value, the proposer must adopt the newest one confessed, abandoning its own. Only if every promise came back empty may it propose what it actually wanted. Acceptors then accept, unless they've since promised someone higher. When a majority has accepted the same ballot, the value is chosen.

One subtlety worth savoring: at the instant the third acceptor writes pizza into its ledger, the value is chosen — and nobody knows it yet. Not the proposer, not the acceptors, not anyone. Choice is a fact about five ledgers, not a message anyone received. Finding out — learning, in the papers' vocabulary — takes more communication, and that little gap between decided and known is exactly why Raft's leader carries an explicit commit frontier.

Two trips, one adoption rule. That's single-decree Paxos. The pseudo-code fits on a page. What deserves the awe is why the adoption rule is enough.

Run the disaster from attempt two again, but through the machinery this time. Three of five acceptors accepted pizza at ballot 3. Chosen. Now the slow proposer arrives, wanting sushi, and does everything right: picks ballot 4, prepares, gathers promises from a majority.

Count with the pigeonhole. Pizza lives on a majority of ledgers. The sushi proposer heard from a majority of acceptors. Two majorities of five must share at least one member — you cannot put more pigeons into fewer holes. So at least one of the promises came from an acceptor holding (ballot 3, pizza), and a promise is a confession: that acceptor told the proposer what it held. The adoption rule does the rest. The proposer's sushi goes back in its bag, and accept(4, pizza) goes out the door.

Ballot 4 wins — and pizza wins with it. The rival didn't get blocked, didn't get refused, didn't even get slowed down. It got recruited. Every proposer that shows up after a choice becomes a courier for the chosen value, pushing it onto even more ledgers under ever-higher ballot numbers. The value doesn't survive the challengers; it survives through them.

And why the gag order? Because a confession is only trustworthy if it can't go stale. Between the promise and the accept, some ancient ballot could try to slip a different value onto the very acceptors the proposer heard from — and then the confession would have been incomplete, and the adoption rule would carry the wrong cargo. The promise slams that window: once an acceptor has promised n, every smaller ballot bounces. The past you were shown is the past that stays true.

That's the whole safety story, and notice whose tools it used: a majority overlap from Quorum Intuition, Revisited, a rising number from Leader Election, and one new move — adopt what the overlap confesses. When Raft's voters refuse a candidate with a stale diary, that is this same move wearing different clothes: Raft filters who may lead by the past; Paxos filters what may be proposed by the past. Same overlap, same confession, same survival.

You now know enough to be dangerous, which is the right frame of mind: the fastest way to trust Paxos is to attack it and lose.

Attack it like this:

1. Run one clean decree. Give the amber proposer a value, prepare, read the five empty promises, accept. Watch the CHOSEN banner light when the third ledger fills.
2. Now try to overwrite it. Give the violet proposer a different value and a higher ballot. Prepare — and read the promises carefully this time: at least one confesses the accepted value. Your accept button will betray you, in the best way: the cargo swaps, and your rival ballot ships the winner.
3. Crash two acceptors and repeat. Three ledgers is still a majority of five. The confession still surfaces. The value still rides.
4. Race them before anything is chosen. Prepare with one, then out-prepare with the other before the first can accept. The first accept bounces off the fresher promise — harmless, honest, and nothing was lost, because nothing was chosen yet.
5. Stage the duel. Let both proposers race politely forever: prepare, out-prepare, bounce, retry. The ballot numbers climb like a score nobody's winning by. That spiral is the next section's story.

The banner at the bottom is recomputed from the ledgers on every step, and it will state the same fact every time: from the moment a value is chosen, no sequence of prepares, accepts, crashes, or rival ballots changes it. You are not being protected by the interface. You are losing to the algorithm.

Now the honest wart, and it's the same wart it always is: liveness.

Two proposers, both eager, neither chosen yet. The amber one prepares ballot 1 and gathers promises. Before its accept lands, the violet one prepares ballot 2 — and the acceptors, honoring the gag order, now bounce ballot 1's accept. So amber retries with ballot 3, which dooms violet's accept at 2. Violet answers with 4. The ballot numbers climb, the ledgers churn with promises, and nothing is ever chosen. Perfect safety, zero progress — the machine politely duels forever.

You've seen this silhouette before. The consensus lesson told you no protocol can promise both safety and liveness under every schedule, and every real system signs the same deal: safety always, liveness usually. The duel is where Paxos pays its liveness premium. Raft pays the very same premium at the same counter — split votes — and settles it with randomized patience. Paxos needs the same medicine: let one proposer act as the distinguished proposer for a while, have the others hold their ballots, and progress returns. Elect an owner, in other words. You have been here.

Which brings us to the version of Paxos that actually runs in production. Nobody deploys one decree; systems need a sequence of decisions — and single-decree Paxos repeats beautifully: run one instance per slot, slot 1, slot 2, slot 3, an infinite bookshelf of tiny parliaments. Then the famous optimization: if one distinguished proposer stays stable, it can run trip one once — a single prepare covering every future slot at its ballot, and then stream trip twos, one per value. Squint at what's left standing: a stable owner with a rising number, a numbered sequence of accepted values, followers acknowledging appends. Multi-Paxos with a stable leader is Raft's silhouette, drawn eleven years earlier with the labels missing. Raft didn't defeat that machine; it specified it, gave its parts one coherent design, and wrote down all the answers multi-Paxos left as folklore.

Now you can appreciate the strange story, because you know what's inside the box.

Around 1989, Leslie Lamport — the same Lamport whose clocks you carry from the ordering lessons — worked out this algorithm and decided to present it as found archaeology: the parliament of a fictional Greek island called Paxos, where part-time legislators wander in and out of the chamber, messages travel by unreliable courier, and yet the parliament passes exactly one law per decree. The legislators bore the names of computer scientists transliterated into mock Greek. To sell the bit, Lamport gave lectures on the paper in character — an Indiana-Jones-style archaeologist, Stetson and hip flask included.

It did not land. By his own account the humor was a dismal failure: audiences remembered the costume and not the algorithm. He submitted the paper to a major journal in 1990; the referees found it mildly interesting and asked him to strip out all the Greek business. He declined, and the paper sat in a drawer for eight years while, in the meantime, the industry started needing exactly what was in it. The Part-Time Parliament was finally published, parable intact, in 1998. Three years later, tired of being told the paper was impenetrable, Lamport wrote a plain-prose version whose abstract is a single, magnificently passive-aggressive sentence: "The Paxos algorithm, when presented in plain English, is very simple."

Meanwhile the algorithm went to work. Google built Chubby, the lock service at the base of its stack, on Paxos — and the team's war-story paper became a classic of its own for documenting the distance between a proof and a product: "There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system," they wrote, and, more bluntly: "While Paxos can be described with a page of pseudo-code, our complete implementation contains several thousand lines of C++ code." Spanner runs a Paxos group under every split of every table — Google's planet-spanning database is, underneath, millions of little parliaments. Cassandra and ScyllaDB run Paxos per partition for their lightweight transactions. The consensus layers of that era largely treated Paxos as the trunk of the family tree — and for twenty years, learning consensus meant surviving this one strange paper and its folklore.

So: two algorithms, same problem, same majorities, same rising numbers, equivalent guarantees. Why did the industry's center of gravity move?

Because Raft was designed for the reader, and Paxos was designed for the proof. The Raft authors made understandability an explicit engineering requirement — they decomposed the problem the way a teacher would (elections, then replication, then safety) and cut the state space wherever two designs were equally correct but one was easier to hold in a head. Then they tested the claim like scientists: 43 students at two universities learned both algorithms and took quizzes; 33 of the 43 scored better on Raft. It remains one of the few times a distributed algorithm won an argument with a user study.

Just as decisive: Raft is a complete specification, and multi-Paxos never was. Elections, log repair, membership changes, commit rules — Raft wrote every answer down in one place. Multi-Paxos left those as exercises, and every team solved them differently; that is exactly the gap the Chubby engineers documented. When you pick Raft, you pick a blueprint. When you pick Paxos, you pick a theorem and a to-do list.

What did Paxos keep? Generality. Single-decree Paxos doesn't need a leader for safety — any proposer, any time, no election, and the value still survives. Its roles decouple cleanly (the machines that propose, store, and learn can be entirely different fleets). And its quorums hide a flexibility Raft's design doesn't chase: the two trips' majorities only need to overlap each other, a loosening (published as Flexible Paxos, 2016) that lets operators shrink the common-case quorum and pay on the rare path. When researchers want to bend consensus into a new shape, they usually start from Paxos, because there's less machine welded to the theorem.

The verdict to carry: operate Raft, understand Paxos. One is the machine you'll run and debug; the other is the load-bearing idea inside every machine of this kind — including Raft.

• Single decree: choose one value, forever. The atom of consensus; a replicated log is this atom repeated per slot.
• Two round trips. Prepare earns promises; a promise is a gag order on older ballots plus a confession of what's already accepted. Accept ships a value to a majority.
• The courier rule is the whole algorithm. A proposer must adopt the newest confessed value. Later ballots don't threaten a chosen value; they deliver it. Raft's stale-diary refusal is the same move pointed at leaders instead of values.
• Chosen ≠ known. A value can be decided while nobody yet knows — learning is separate, which is why practical systems carry an explicit commit frontier.
• The duel is the price. Rival proposers can out-prepare each other forever: safety always, liveness usually, same deal as ever. The fix is an owner with patience — an election, by any name.
• Multi-Paxos ≈ Raft's silhouette. Slots plus a stable distinguished proposer plus an amortized trip one. Raft won by specifying that machine end to end and proving, with 43 students, that humans could hold it.
• Paxos still matters: leaderless safety, decoupled roles, flexible quorums — and it's running under Chubby, Spanner, and Cassandra's transactions right now.

Step back and look at the section so far: everything you've built — quorums, terms, logs, ballots — buys certainty, and pays for it in round trips and majorities. The next lesson asks the opposite question: what if you don't need certainty at all? No quorums, no ballots, no owner — every node just whispers what it knows to a few random neighbors, and information spreads through the cluster the way a rumor crosses a school. It's how clusters learn who's alive, and it is gloriously, deliberately imprecise: Gossip Protocols.