Distributed Consensus

Picture five servers that must agree on a single fact — say, "order #42 was charged." If they all stayed up and messages arrived instantly, this would be trivial. But real machines crash, networks delay and drop messages, and a server can freeze for a second and wake up thinking no time has passed.

The challenge is to make the whole cluster behave like one reliable machine: every surviving server reports the same value, in the same order, no matter which ones died along the way. This is the distributed consensus problem, and it is the quiet foundation under databases, lock services and cloud control planes.

The trick used in practice is almost human: the cluster elects a leader, the leader writes down decisions in a log, and it copies that log to everyone else. Lose the leader and the survivors simply elect a new one — and the agreed-upon history is never lost.

Below is a tiny cluster of five nodes. Click Elect leader and the nodes vote: whoever gets a majority becomes the leader. Then Append entry to write a value — the leader copies it to the followers, and an entry is committed once a majority hold it.

<p class="hint">{{hint}}</p>
<div id="cluster" class="cluster"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="elect" type="button">{{btn_elect}}</button>
  <button id="append" type="button">{{btn_append}}</button>
  <button id="crash" type="button" class="danger">{{btn_crash}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.cluster { display: grid; grid-template-columns: repeat(5, 1fr); gap: 8px; margin: .4rem 0; }
.node { border: 1px solid #cdd9e3; border-radius: 10px; padding: .5rem .35rem; text-align: center;
        background: #f4f7fa; transition: all .15s; }
.node .name { font-weight: 700; font-size: .85rem; color: #1d3557; }
.node .role { font-size: .7rem; text-transform: uppercase; letter-spacing: .04em; color: #5a7088; margin: .15rem 0; min-height: 1em; }
.node .log { display: flex; flex-direction: column; gap: 2px; margin-top: .35rem; min-height: 14px; }
.node .ent { font: 600 11px ui-monospace, monospace; background: #d7e3ee; color: #1d3557; border-radius: 4px; padding: 1px 0; }
.node .ent.committed { background: #0a7d33; color: #fff; }
.node.leader { background: #1d3557; border-color: #11233c; }
.node.leader .name { color: #fff; } .node.leader .role { color: #9fc0e0; }
.node.leader .ent { background: #355378; color: #e8eef3; }
.node.leader .ent.committed { background: #2fae5a; color: #fff; }
.node.dead { background: #efe2e2; border-color: #e0b9b9; opacity: .6; }
.node.dead .name { color: #c92f3c; text-decoration: line-through; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.danger { background: #c92f3c; border-color: #a8242f; }
button:disabled { opacity: .45; cursor: not-allowed; }

// Code not found

Now press Crash leader. The leader goes dark, the followers notice the silence, and a new election picks a fresh leader from the survivors — with the committed log intact. The key idea is the majority (quorum): because any two majorities of five nodes must share at least one node, no two leaders can ever commit conflicting histories. Agreement survives as long as more than half the cluster is alive.

How hard is consensus, really? Hard enough to be provably impossible in the worst case.

• FLP impossibility (Fischer, Lynch, Paterson, 1985). In a fully asynchronous network — no bound on message delay — no deterministic algorithm can guarantee consensus if even a single process may crash. You can never tell a dead node from a slow one, so any protocol can be forced to wait forever.
• The escape hatch is timing. Real systems assume that messages eventually arrive and that nodes have rough clocks (the "partially synchronous" model). Under that mild assumption, consensus becomes solvable.
• Paxos (Leslie Lamport, 1998) was the first widely used solution: a majority quorum ensures that any committed value is seen by every future leader, so decisions are never lost or contradicted.
• Raft (Ongaro & Ousterhout, 2014) repackages the same guarantees around an explicit leader, terms and a replicated log, trading nothing in safety for a lot in understandability.

The punchline: consensus is safe always, live only when the network behaves. You cannot beat FLP — you can only arrange for the bad case to be temporary. The deep tension between staying consistent and staying available is the same one named by the CAP theorem.

"Make these machines agree on one ordered history" turns out to be the backbone of modern infrastructure:

• Replicated databases: systems like Google Spanner and CockroachDB use Paxos/Raft groups so a write survives any single machine failure.
• Coordination services: etcd (the brain of Kubernetes), ZooKeeper and Consul store cluster configuration and elect leaders using consensus.
• Distributed locks and leases: only one worker should hold a lock at a time — that "only one" is a consensus decision.
• Blockchains: public ledgers solve a Byzantine cousin of the problem, where nodes may not just crash but actively lie.

The shared pattern is the replicated state machine: feed every node the same log of commands in the same order, and they all end up in the same state. Get consensus right and a pile of flaky servers behaves like one machine that never forgets.

Distributed consensus hides a paradox: theory says guaranteed agreement under crashes is impossible (FLP, 1985), yet every cloud you use depends on it working flawlessly. The resolution is humble — assume the network eventually behaves, demand a majority before committing, and let a crashed leader be replaced by a fresh election.

So the next time a server dies and your app keeps running as if nothing happened, that is consensus quietly at work: a quorum of machines agreeing on one story, refusing to lose it, and standing in for the one perfect computer we can never actually build. The same trade between agreeing and staying online is what the CAP theorem puts into words.