Leader Election

Two debts come due today. The data course, watching a standby get promoted, said the quiet part out loud: promote too eagerly and you'll promote a leader that was never dead, now you have two — and then promised that promotion is a genuinely deep topic that gets its own treatment later in the course. This is that treatment. And the last lesson ended on a riddle: every working protocol needs an owner per round, but picking an owner is itself a one-answer decision. Consensus before consensus. Who elects the electors?

The escape is clean, and it's the heart of this lesson: you don't need a chairman if everyone carries the same rulebook. No referee starts the election; the rules themselves make it safe for anyone to start one, safe for two to start one at once, and safe for the old king to wake up confused. By the end you'll have the recipe's two missing ingredients installed (rounds with numbers, and an owner) and you'll have run the machinery with your own hands: killed kings, woken zombies, split votes, and watched the cluster heal itself every time.

State the riddle honestly, because hand-rolled systems die on it: to run a round of consensus we wanted an owner; to pick an owner we need a round of consensus. If elections needed an elected official to run them, nothing could ever start.

The escape has two parts, and neither is a referee.

Symmetry. Every node runs the identical protocol and any node may call an election. There is no special first mover, no bootstrap node, no admin who goes first. The safety rules (next section) are written so that concurrent calls, the thing a referee would have prevented, simply cannot produce two winners.

Randomness. What a referee would have serialized, chance staggers. Each node waits a slightly different, randomly drawn time before calling an election, so in the common case exactly one node moves first and wins cleanly. When luck fails and two move together, nothing breaks — the round just fails and everyone redraws. Randomness here buys liveness, never safety; safety never rests on luck.

That division of labor (rules guarantee one-answer, randomness makes an answer likely soon) is the consensus problem's “safe always, live usually” deal, signed in machinery.

The rounds get numbers, and the numbers get a name: terms. A term is a monotonically climbing integer: the cluster lives in term 3 until somebody calls an election, and that call is the increment. Three rules run everything:

1. Calling an election means bumping the term. The candidate moves to term+1, votes for itself, and asks everyone else.
2. One vote per node per term — remembered. A node that granted its term-4 vote writes that fact down before answering, so not even a crash-and-reboot lets it vote twice in term 4. This is the rule that makes ballots legible: every vote is labeled with its round, which is precisely what the witness lacked in the last lesson's wreckage.
3. A majority of the full membership wins. Not a majority of whoever's awake — a majority of N, dead nodes included. The pigeonhole only protects you if N is the real N.

Put the three together and the last lesson's proof finishes the job: two leaders in one term would need two majorities in that term, two majorities must share a voter, and the shared voter would have had to vote twice in one term: forbidden and remembered. At most one leader per term. Not “rarely two”. One, by arithmetic.

The crowned leader then holds the room the same way it was found: heartbeats, streamed to every follower, each one saying the throne is occupied, reset your timer.

Look closely at the follower's election timer and you'll recognize it: it's the failure detector from the heartbeats lesson, wearing election clothes. A follower whose timer expires hasn't learned the leader is dead (dead is indistinguishable from slow, still, forever); it has merely bet that waiting longer isn't worth it, and the bet's two loser sides come straight from that lesson's dial:

• Too tight, and ordinary jitter crowns needless candidates: elections fire during GC pauses and network hiccups, terms churn, and the cluster spends its time campaigning instead of working. The split-brain factory, rebuilt as an election storm.
• Too loose, and every real death buys seconds of leaderless silence (no writes, no progress, clients stacking up) before anyone dares to run.

Suspect fast, convict slow, act reversibly — and notice how well the election machinery obeys the old rule. Calling an election is the reversible act: if the old leader was alive all along, the worst outcome is a new term it can't argue with. The irreversible thing, two crowns in one term, is guarded by arithmetic, not by the timer. The bet only ever risks efficiency; the rules protect truth.

Five nodes, one crown, everything live: heartbeat pulses streaming from the leader, timer rings draining and refilling on every follower, terms on every chest.

Try this first: kill the leader and just watch. Some follower's ring empties first (randomness picked it) and the machinery runs on its own: term bumps, self-vote, grants come back, majority, crown. Read the vote ledger afterward; every grant is labeled with its term, and no node appears twice in one.

Then run the zombie. Pause the leader instead of killing it, let a successor get elected, and wake the old king: it comes back still wearing the old term, meets a bigger number on the first exchange, and steps down without a fight. No fencing gate needed at the door — the door check is built into the protocol itself.

Then get mean. Cut the lone node off and watch it rage — calling elections nobody hears, term climbing 7, 8, 9, and never winning, because three of five means three, and it has one. Heal it and watch the honest wart: its inflated number forces the healthy leader to step down for one needless re-election. Real systems sand this off with a pre-vote check; that story is next lesson's.

Finally, stage the classic with the split vote button: two rings fire together, the vote splits with no majority, the term ends crownless — and the retry, with fresh random timers, resolves it. That tiny anticlimax is FLP's shadow passing overhead: a stall is always possible, and randomness makes it never matter.

Now step back, because you've met this number twice before.

In the split-brain lesson it was the fencing token: authority as a number that only goes up, checked at the storage gate, so the stale king's writes bounce. In the logical clocks lesson it was the epoch, the Lamport species, a counter carried on messages that orders without testifying. The term is the same number, third costume, now running the whole show: every request a leader sends carries its term, every node compares terms before believing anything, and any node holding a bigger number simply outranks the past.

That's why the zombie king is harmless here without any extra machinery. Yes — for a moment, two nodes each believe they are a leader. But they are leaders of different terms, and the term travels with every word they say. Followers already in term 3 refuse term 2's orders; the store, if you kept the fencing gate, refuses them too; and the first reply the old king receives teaches it the truth, at which point rule three does the rest: higher term wins the argument, step down. Two believers, never two authorities. The impossible thing — two leaders in the same term — stays impossible, and everything else is a brief costume party that the number ends.

Two honest warts, both visible in the sim, both worth naming in a design review.

Split votes. Two timers fire together, the vote splits, the term produces no leader, and the cluster waits out another random draw. Safety never flinched (no majority, no crown) but time was lost, and in principle bad luck could repeat. This is FLP made concrete: a deterministic protocol can't guarantee the election ever ends, so the machinery buys its liveness with randomized timeouts that make repeated collisions geometrically unlikely. Safe always; live with probability that rounds to always.

The disruptor. An isolated node can't win, but it can inflate. Every futile election bumps its term, and when the partition heals, its swollen number forces a perfectly healthy leader to step down for one unnecessary election. Nothing breaks; something hiccups. Mature implementations add a pre-vote: before really bumping the term, a would-be candidate asks “would you vote for me?” and only proceeds if a majority says yes — the isolated node keeps polling, keeps hearing no, and stops wrecking terms. The full mechanism, along with everything the leader is actually for, is the next lesson's story.

• The circularity has a clean escape: symmetry plus randomness. No chairman runs the election; the shared rulebook makes concurrent candidacies safe, and random timers make them rare. Rules buy safety; randomness buys liveness.
• Terms are the numbered rounds the recipe demanded. Call an election, bump the term; one remembered vote per node per term; a majority of the full membership wins.
• At most one leader per term, by arithmetic. Two would need a shared voter voting twice in one term: forbidden, and written down.
• The election timer is the failure detector with a crown on it. Tight buys election storms, loose buys leaderless seconds; calling an election is the reversible act, so the bet only risks efficiency, never truth.
• The term is the token, third costume. Fencing number, epoch, term: one rising integer, carried on every message, ending every argument. The zombie king steps down because it must lose the comparison.
• Two honest warts: split votes (randomness heals), the inflated-term disruptor (pre-vote heals — next lesson).

So the cluster can now crown an owner, keep exactly one per round, and survive the old one's return. One question was carefully dodged: crown it to do what? A leader is only worth electing if everyone then follows the same story it tells: a replicated log, identical on every machine, with rules for who is even allowed to stand for election after a crash. That's the whole machine, assembled and running, and you can drive it: Raft, Visually.