Distributed consensus
A Socratic walk-through of distributed consensus — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why can a group of perfectly healthy machines fail to agree on which of them is in charge?
Five servers, all powered, all running, none of them buggy. Between them they must maintain one fact: which server is the leader. They can exchange as many messages as they like. And yet they can end up with two servers each certain it is in charge.
The instinct is to blame a fault — a crash, a bug, bad hardware. But suppose there is none. Then the failure is not mechanical, and if it is not mechanical it must be about what each machine can know. That is the thread worth pulling.
Reasoning it through
REASONING #Put yourself inside one node. You sent a message to a peer and no reply came. The peer crashed; or the peer is alive but paused, in a long garbage collection or on a stalled disk; or your message was dropped; or the reply was; or the reply is still in flight.
Now the question that decides everything: can you distinguish these? Only by waiting longer. And how long is long enough? If the network guarantees no upper bound on delivery time — and no real network does — then no amount of waiting is conclusive. A timeout is a guess, and one that is sometimes wrong by construction rather than by carelessness.
That is the whole failure in miniature. A follower's timeout fires, it concludes the leader is gone, and it stands for election. But the leader was merely slow. Two nodes now hold beliefs that were reasonable on the evidence each had, and the beliefs are incompatible. No machine misbehaved.
This is not a folk observation. Fischer, Lynch and Paterson proved in 1985 that in a fully asynchronous system where even one process may crash, no deterministic protocol can guarantee both that all nodes decide and that they decide the same thing. The obstacle is exactly the indistinguishability above: any protocol that always terminates can be forced into a wrong decision, and any protocol that never decides wrongly can be forced to hang. Real systems therefore give up something specific — they keep safety absolutely, never two conflicting decisions, and surrender liveness, making no progress until the network cooperates.
The instrument for keeping safety is arithmetic, worth deriving because it is the one part with no hand-waving. Require any decision to be endorsed by a majority. Take two majorities of an N-node cluster: each has more than N/2 members, so together they have more than N. But there are only N nodes, so they must share at least one, and that node will not endorse two conflicting things. Two majorities cannot independently commit. The reason a partitioned cluster has at most one effective leader is not that the protocol detected the partition — it did not — but that the minority side cannot assemble the votes. The counting rules follow: to survive f crash failures and still hold a majority you need 2f+1 nodes, and if nodes may lie rather than merely stop, the Byzantine requirement rises to 3f+1.
But notice what majorities do not fix. The stale leader is still running, still believes it leads, and will discover otherwise only when it next talks to someone. Between the election and that discovery, two leaders genuinely exist. Protocols handle this by numbering leadership — terms, epochs, ballot numbers — so anything the old leader tries arrives stamped with an obsolete number and is refused. Its writes fail, but at the receiver, after the fact.
The analogy
THE ANALOGY #Two people are trying to agree on a meeting place using only postcards, with no guarantee about delivery time and no way to tell a lost card from a slow one. Each writes "meet at the station" and waits for confirmation — but confirming receipt needs its own confirmation, and so on. What they can do is agree in advance that the plan is whatever a majority of a committee of five has stamped, because two different plans cannot each collect three stamps from the same five people.
postcards arrive in the order posted often enough to feel reliable, whereas networks reorder and duplicate freely — and the correspondents can eventually pick up a telephone, while a partitioned cluster has no channel outside the one that failed.
Clarifying the model
THE MODEL #The most common wrong framing is that consensus protocols make agreement always achievable. They do not. They make disagreement never durable: a split brain can exist for a while, and what the protocol guarantees is that only one side's decisions ever take effect.
The second is the popular reading of CAP as "pick two of three". The actual result is narrower — during a network partition you cannot have both linearizable consistency and availability at every node — and it says nothing useful about the times when the network is fine, which is most of the time. Treating it as a menu of three interchangeable properties supports design conclusions the theorem does not.
Worth reconciling with a neighbouring puzzle: the reason two machines can never fully agree on the order of two events is clock skew and the absence of a shared instantaneous now. That is the same underlying limit — no node has a current global view — surfacing at a different point. Clock skew makes ordering unknowable; message-delay uncertainty makes liveness unattainable. Consensus protocols dodge the first entirely by ordering events with their own logical term numbers rather than trusting any clock, which is why a machine with a badly wrong clock can still participate correctly.
And "healthy machines" was doing real work in the question. The scenario needs no fault at all — a two-second pause on a node about to renew its lease is enough. That is why better hardware does not help: the limit is informational, not mechanical.
A picture of it
THE PICTURE #How to readTime runs downward and each vertical line is one participant, with the network drawn as a party in its own right because its behaviour causes everything here. The crossed arrow is the message that never lands — nothing broke, it was only late. The first note is the crux: B's next action is reasonable on the evidence B has. Read the last four exchanges as the repair rather than the failure — A's stale write is not prevented, it is rejected on arrival, which is what "safety without liveness" looks like in practice.
What became clearer
WHAT CLEARED #The machines fail to agree because none can tell silence from slowness, and no amount of health in the hardware supplies that distinction. Agreement is therefore not something a protocol can guarantee outright — it is something it guarantees never to get wrong, by refusing to let any decision stand without a majority, and by leaning on the fact that two majorities of the same set must overlap.
Everything else — terms, leases, fencing tokens — is machinery for surviving the interval in which two nodes hold incompatible but individually reasonable beliefs. The system is not built to prevent that interval. It is built so the interval cannot leave a mark.
Where to go next
ONWARD #- How Paxos and Raft differ in structure while making the same safety guarantee.
- Why leases are time-based and what assumption about clock drift they smuggle in.
Key terms
TERMS #| Term | What it means |
|---|---|
| Quorum | a subset large enough that any two such subsets must overlap, usually a strict majority. |
| Split brain | a state in which two nodes each believe they hold leadership, typically after a partition. |
| Term / epoch | a monotonically increasing number identifying a leadership period, used to reject stale commands. |
| Fencing token | a number handed out with a lock so a downstream service can refuse a superseded holder's request. |
Every term the collection defines is gathered in the glossary.