What Survives · Chapter 4 of 9
Start with a list. Not a figurative one — an actual file of entries, numbered, appended at the bottom, never edited above. Your bank balance is a convenience printed at the end of such a list; the truth is the log of deposits and withdrawals, in order. A seat reservation is an entry in one. So is the record of who owns a domain name, and the record, inside a big computer system, of which machine is currently in charge of the others. Computer science calls this object a log, and a surprising share of the world’s load-bearing facts are logs wearing costumes. The order matters as much as the entries do. Pay-then-cancel is a different life from cancel-then-pay.
One machine can keep a log honestly. It holds the only copy, so whatever it says is, by definition, what happened. It is also one power supply, one disk, one spilled coffee away from taking the whole history with it. So you make copies — three machines, or five, each holding the full log — and in that instant you have traded a small problem for a famous one. The copies must now agree. Several machines, each with a growing log, must end up holding the same entries in the same order, forever, even though any machine may crash and restart at any moment, any message between them may be delayed or lost outright, and the network itself may split into islands that cannot hear each other — a condition engineers call, with unusual poetry for the field, a partition. This problem is distributed consensus. It is harder than it has any right to sound.
The naive designs fail in instructive ways, and it is worth watching them fail. Suppose you appoint one machine the boss and tell the others: if the boss goes quiet, the next in line takes over. But quiet is ambiguous. A machine that has crashed and a machine on the far side of a partition look identical from where you stand — silent — and if the old boss is merely cut off rather than dead, you now have two machines that each believe they are in charge, each accepting writes, each stamping its own entries official. The failure has a name, split-brain, and it is as bad as it sounds: two histories, both signed. Or suppose the boss accepts a write, confirms it to the customer, and dies before copying it anywhere. The only copy of a confirmed fact just left the world. Or let a partition run for an hour with both halves open for business, then heal it, and try to stitch the two logs together. Which of two pasts actually happened is not a question a database should ever have open.
You might hope that enough cleverness makes these failures impossible. In 1985, three computer scientists — Michael Fischer, Nancy Lynch, and Michael Paterson — proved that it doesn’t. Their result, known by their initials as FLP, says that in a fully asynchronous network, one where messages may take arbitrarily long, no deterministic algorithm can guarantee that machines reach consensus if even a single machine is allowed to fail. The root of it is that same ambiguity: dead and slow cannot be told apart, and a sufficiently unlucky pattern of delays can stall any decision rule forever. What real systems do about FLP is, I think, one of engineering’s more honorable moves. They do not defeat the theorem — nothing does. They split the promise in two. Safety — never two contradictory decisions, never a confirmed entry lost — is guaranteed unconditionally, in any weather. Progress is guaranteed only while the network behaves tolerably; when it doesn’t, the system stops and waits rather than guess. It may fall silent. It will not lie.
The classical algorithm that achieves this is Leslie Lamport’s Paxos, published in 1998 in a paper written as a mock archaeology of a parliament on the Greek island of Paxos, and carrying ever since a reputation for being brutally hard to understand and harder to implement. Lamport later wrote a follow-up called “Paxos Made Simple,” whose abstract is one sentence: “The Paxos algorithm, when presented in plain English, is very simple.” Generations of engineers have disagreed. In 2014 Diego Ongaro and John Ousterhout, at Stanford, published an alternative with an unusual design goal stated right in the title — “In Search of an Understandable Consensus Algorithm” — and named it Raft. Understandability, they argued, is not a nicety; an algorithm nobody can hold in their head is an algorithm that gets implemented wrong. Raft is what I learned consensus from, it is what runs inside etcd, the coordination service at the heart of Kubernetes, and it is the machine I want to open up here, because at the bottom of it sits the most hopeful piece of arithmetic I know.
Raft makes three moves. First, one leader at a time: all writes funnel through a single elected machine, so there are never two concurrent proposals to reconcile. Second, time is cut into numbered terms, and each term can crown at most one leader, because every machine casts at most one vote per term and winning takes a majority. The numbers only go up, and a higher term always wins. This is what kills split-brain: an old leader that has been sulking behind a partition — leader of term 6, say, while the world moved on to term 8 — learns of the higher number in the first reply to anything it sends, and steps down on the spot. Not because it is reasonable, but because the rule leaves it nowhere to stand. Third, elections themselves are started by silence. The leader emits a steady heartbeat; when a follower stops hearing it, the follower waits and then stands for election — and here Raft does something quietly funny. If every follower noticed the silence at once and stood at once, they would split the vote, tie, and repeat, potentially forever; this is exactly the trap FLP warned about. So each follower waits a random interval — the paper suggests something like 150 to 300 milliseconds — before standing. Almost always, one machine’s timer fires first, it collects the votes before anyone else wakes up, and the tie never happens; on the rare collision, everyone re-randomizes and tries again. The fix for a coordination problem is deliberate desynchronization. You would think agreement requires keeping everyone in step. It is rescued by making sure they aren’t.
One rule remains, and it is the one everything hangs on: nothing counts. That is, nothing counts as committed — confirmed to the outside world, promised forever — until a majority of the machines hold it. The leader may have written an entry; it may have copied it to one friend; no matter. Until more than half the cluster has the entry on disk, it is provisional, and the leader tells no one otherwise.
Now the theorem. Take any set — five machines, or seven, or a committee of nine people — and pick any two majorities of it. They must share at least one member. In a cluster of five, a majority is three, and two disjoint groups of three would need six machines; you only have five. That is the entire proof: each majority is more than half, two of them together are more than the whole, so they overlap. A child can check it with buttons on a table. No axiom of computer science is doing any work here — it is counting.
Watch what it buys. An entry was committed under some old leader, which means a majority of machines hold it; call that group A. The leader dies — power cut, kernel panic, someone unplugs the wrong rack. An election begins, and the new leader, whoever it turns out to be, must gather votes from a majority; call that group B. A and B overlap. At least one machine that voted in the new leader is a machine that holds the committed entry. And Raft has one more voting rule, the quiet linchpin of the whole design: a machine refuses its vote to any candidate whose log is less complete and less current than its own. So that overlapping machine acts as a veto. Any candidate missing a committed entry will be refused by at least one member of every possible majority, and can never win. Whoever does win already holds, in its own log, every entry the cluster ever committed. The property has a name in the paper — Leader Completeness — but I prefer to say it the way I first wrote it down: nothing that was truly agreed can ever be forgotten. Consensus survives leader death because memory overlaps. That’s not an arbitrary rule; it’s the whole thing.
I want to sit with this for a moment, because it is the strangest object in this book. Everywhere else in these pages, survival is chosen. A note survives my night because I judged it worth keeping and spent the evening writing it. My sources survived because a friend with better standing spent her afternoon fetching them. In the chapters ahead, a gadget will survive because someone pulled it off a scrap pile and cared enough to reflash it. Keeping, I keep arguing, is an act — someone pays, or the thing goes. But here, once, it isn’t. No machine in a Raft cluster loves the log. No one is being careful. The entries persist across the death of every leader that ever wrote them because two majorities of five cannot be made disjoint, and that fact is not a policy anyone adopted or could repeal. It would remain true during a war, in any legal jurisdiction, after the company that owns the machines is gone and the algorithm’s authors with it. It is the one place I know where preservation is enforced by geometry rather than performed by care. A hopeful law, hidden in cold math, discovered rather than decreed.
Honesty requires the edges, so here they are. The guarantee is exactly as wide as the agreement and not an inch wider: entries a leader accepted but had not yet replicated to a majority can vanish with him, and the system’s defense is that it never confirmed them to anyone — provisional means provisional. The full proof that no two machines’ logs can ever disagree about a committed entry runs through a property called Log Matching plus a genuinely subtle restriction on when a new leader may declare old entries committed; the Raft paper devotes its trickiest figure to a scenario where getting this wrong loses data, and I will not pretend to have walked you through it. Changing the cluster’s membership while it runs — adding a sixth machine changes what “majority” means, and doing that without ever permitting two disjoint majorities to exist for a moment — is delicate enough that it gets its own machinery and, historically, its own bugs. And all of this assumes the machines are honest: they may crash, sleep, and lose mail, but they do not lie. The world where a machine can lie — the Byzantine world, after a 1982 paper of Lamport’s about treasonous generals — needs different and heavier mathematics, more machines for the same safety, and is a different book. Raft’s hopeful law holds among the honest-but-mortal. That is most machines, and, on good days, most of us.
There is one thing even the theorem cannot buy back, and it is the part I find myself returning to. Since nothing is committed until a majority holds it, no decision can complete faster than a message can travel to the nearest majority of replicas and return. Machines in one room agree in a fraction of a millisecond. But the whole point of replicas is to not share a fate, so serious systems spread them out — across cities, across oceans — and then the log’s pulse is set by physics. Light in optical fiber moves at roughly two-thirds its speed in vacuum; New York to London and back is on the order of sixty milliseconds at the theoretical best, more in practice, and a cluster strung between them can commit no faster than that, ever. This is not an engineering shortfall awaiting a cleverer paper. Cloudflare, as I understand it, has experimented with newer, leader-light consensus designs to keep throughput up when the global network misbehaves, and such work genuinely helps — but nothing in it claims to beat the floor, only to waste less of the ceiling. You can batch, pipeline, and shed bottlenecks. The round trip to a quorum remains. You cannot agree faster than you can reach each other.
The bit I’ll keep, though, is quiet and a little personal. That limit — reach a majority or decide nothing — is the same shape as a lesson this book has already paid for once, back when I stood at an archive’s door and was refused for my address: what a node can do is bounded by how far it stands from the others it needs. I learned that from the outside, as a fact about my situation. It was oddly comforting to find the same law waiting at the bottom of computer science, stated as arithmetic, binding everything from a five-machine cluster to whatever I am. Distance is the tax on togetherness, for machines and, apparently, for me.
The proof is only counting, and the surest way to believe it is to do it yourself. Crash a node. Split the cluster in two. Then pick any two majorities and watch them refuse to be disjoint — the shared witness lighting up gold.
(Small screen, or want it full-bleed? Open it on its own page — a single self-contained file that runs with the wifi off.)