Distributed Consensus: How Machines That Crash Agree on One Thing

A group of machines agreeing on “one thing” — who is the leader? who holds this lock? what’s the latest value? — sounds simple, yet it’s one of the hardest problems in distributed systems. Why? Because machines crash, networks partition, clocks can’t be trusted, and under all that you need everyone to reach consensus on one answer, and never diverge.

Why “rolling your own” goes wrong: split brain

The most intuitive homebrew solution: everyone sends heartbeats, whoever stops responding is treated as dead, and a new leader is elected. Fine on ordinary days, but the moment the network cuts, it breaks:

Split brain is the classic death of homebrew consensus: the network partitions, each side "reasonably" concludes "the other is dead, I'll take over", and both accept writes at once. The frightening part isn't that someone died; it's that both sides are alive and both believe they're right — when the network heals, two contradictory copies of the data refuse to yield to each other, and the damage may be irreparable

The root of the problem: “the other side didn’t respond” and “the other side is dead” are indistinguishable to you — maybe the network just cut, and the other side is perfectly alive. The homebrew algorithm treats “can’t hear you” as “dead”, so under a partition both sides conclude “I should be leader”. To cure it you need a mechanism that mathematically guarantees “never diverges”.

The core of consensus: majority (quorum)

Distributed consensus (Paxos, Raft and Zab are several implementations of it) rests on a principle you learned in primary school — majority vote: any decision must win the agreement of “more than half” the nodes to count. And “more than half” has one key property:

Why does a majority cure split brain? Because any two majority sets must share at least one node — and that node won't say yes to two conflicting proposals. So even under a partition, at most the side "holding the majority" can decide; the other side is automatically disabled, and two leaders can never coexist. It's also why consensus systems always use odd counts (3, 5): 2f+1 nodes tolerate f failures while keeping a majority

With majorities, a consensus system gives two key guarantees: safety — there will never be two contradictory decisions, and this holds under every circumstance; and liveness — as long as a majority of nodes are alive and can communicate, a conclusion will eventually be reached. Note that safety is unconditional: even if the network is so broken that only half can talk, the system would rather stop (be unavailable) than ever give a wrong answer — which is exactly CAP’s “choose consistency under partition”.

Three implementations of one problem: Paxos, Raft, Zab

“Majority” is the principle, but turning it into an algorithm that actually runs and doesn’t go wrong has a terrifying amount of detail. Consensus isn’t one algorithm but a family; the three names you hear most — Paxos, Raft, Zab — solve the same problem (use majority agreement to assemble an ordered log) but have very different personalities:

Three roads to the same place: all use majority agreement to assemble a log every replica accepts, in the same order. The real differences are the leader model (classic Paxos is symmetric; Raft and Zab both have a strong leader) and understandability — which sounds soft, yet is the key to Raft overtaking the others to become the modern default: an algorithm you implement correctly beats one that's theoretically prettier but riddled with traps

Paxos: the theoretical origin, correct but hard to handle

Proposed by Leslie Lamport in 1989, it’s the theoretical source of distributed consensus, mathematically proven correct. But it’s notoriously hard to understand: the original paper only covers “reaching consensus on a single value” (basic Paxos), while real systems need consensus on “a sequence of values” (a log) — Multi-Paxos — and the paper is vague on that part, so every implementation looks different and the details are full of traps. Google’s paper “Paxos Made Live” is entirely about “how much unwritten blood and tears lie between the paper and a shippable product”. It’s used by heavyweights like Google’s Chubby and Spanner.

Raft: born to be “understandable”

Proposed by Stanford in 2014, its motivation is right in the paper’s title: “In Search of an Understandable Consensus Algorithm” — it had had enough of Paxos being too hard, and was deliberately designed to be understandable. The approach is a strong leader model: all changes flow only from leader to followers (one way), and the problem is split into three digestible sub-problems — leader election, log replication, safety. It has one very elegant small trick too: randomised election timeouts, which naturally avoid the split-vote deadlock of everyone running for leader at once. Raft gives the same guarantees as Multi-Paxos, but you can actually implement it and not easily get it wrong, so it became the modern default — etcd, Consul, TiKV, CockroachDB, and Kafka’s KRaft all use it.

Zab: ZooKeeper’s dedicated engine

Zab (ZooKeeper Atomic Broadcast) is the protocol behind Apache ZooKeeper, older than Raft and similar in style (also strong leader). It’s tailored to the specific scenario of a “coordination service”, centred on atomic broadcast — guaranteeing that all state changes are applied on every machine in exactly the same order; the leader numbers each change with a monotonically increasing zxid, and the design revolves around “how to recover cleanly after the primary crashes”. You may never have used it directly, but you’ve almost certainly depended on it indirectly — ZooKeeper underpinned old Kafka, HBase, Hadoop and a whole crowd of systems.

What consensus is for: a log everyone agrees on

The most common use of consensus is producing an operation log that all replicas agree on, in the same order (a replicated log). Every replica applies the same operations in the same order, and their states naturally match — that’s a replicated state machine. On top of that you can build a stack of critical facilities:

Leader election: there’s always exactly one leader, never split brain.
Distributed locks: the whole cluster agrees on who truly holds the lock.
Configuration / metadata storage: the whole system’s “source of truth”.

And SRE’s most important piece of advice is: don’t build your own consensus. The correctness of consensus algorithms is extremely subtle, and a homebrew version almost certainly has hidden bugs. In practice, use a proven off-the-shelf system — the infrastructure you use every day is built on them: K8s entrusts its entire cluster state to etcd, which runs Raft; Kafka’s new KRaft is Raft by name; inside Google it’s Chubby.

Reflections

”Don’t build your own consensus” is a belief I paid tuition for

When I was younger I really did “elect a leader with a flag column in the database plus a periodic heartbeat”, and at the time it felt clever and cheap. The result was that during one network hiccup, two instances both grabbed “I’m the leader” and each ran a round of tasks that were supposed to be mutually exclusive; the clean-up took a long time. Consensus is the kind of thing that’s right ten thousand times in a row and wrong on the ten-thousand-and-first edge case — and in distributed systems, rare edge cases happen every day. Since then I hold to one rule: any requirement involving “a group of machines agreeing on something”, I reach for etcd / ZooKeeper instead of assembling my own. That’s not laziness; it’s admitting one thing — this problem is an order of magnitude harder than it looks, and someone else has already solved it correctly.

What split brain taught me: the most dangerous failure is “everyone believing they’re right”

Split brain gave my picture of “failure” a new dimension. I used to think failure meant “the thing died, no response”, which is actually the easy case — at least you know it’s broken. What’s truly frightening is split brain: nobody died, every node is alive and well and working normally, each making a “reasonable” judgment from the partial information it can see, and the whole collapses. It’s the same shadow as the “partial failure” DDIA describes — the difficulty of distributed systems is often not a single point breaking, but the absence of a god’s-eye view: every node sees only its part, yet has to make a globally consistent decision. The elegance of the majority is precisely that it uses the geometric property of “overlap” to impose a single truth on this crowd of independent nodes.

Consensus isn’t free, so use it where it cuts

Majority voting sounds beautiful, but it has a price: every decision waits for a round trip of confirmation from a majority of nodes, a very real latency and throughput bottleneck. So good architecture doesn’t shove everything through consensus; it routes only the most critical, least-allowed-to-fail sliver of state through it (who is the leader, locks, key configuration), and the large bulk of data through cheaper replication. It echoes what I keep coming back to: reliability was never “crank everything to maximum”, but knowing which places are worth paying the expensive price and which aren’t — and reserving the strongest guarantee for the line you truly can’t afford to lose.