Lesson 26 · Consensus · Module 3
Why Agreement Is Hard
Not fiddly. Hard. Two nodes cannot become certain of each other by exchanging any finite number of messages, and no deterministic algorithm can guarantee agreement in a system with no clocks. Every consensus algorithm you will ever run is a negotiated settlement with those two results.
The win in this lesson: you will stop reading a timeout as an implementation detail. A timeout is the assumption that makes consensus possible at all — and you will be able to say precisely what a failure detector is really detecting.
1. The problem: agreement is not a coding problem
Two services must reach the same decision. Commit or abort. This node is the leader or that one is. The next message in the log is m or it is n. Only one answer may exist, and every participant must end up holding it.
The instinct is that this is an engineering problem — add a retry, add a confirmation, add a confirmation of the confirmation. The instinct is wrong, and it is wrong for a reason you can prove rather than measure.
2. The two generals
Two armies, camped apart, can capture a city only if both attack. Either attacks alone and it is destroyed. They can communicate only by messenger through hostile territory, so:
"a message sent by one general may or may not be received by the other general, and the sender does not know whether their message got through, except by receiving an explicit reply from the other party. If a general does not receive any messages, it is impossible to tell whether this is because the other general didn’t send any messages, or because all messengers were captured."
Martin Kleppmann, Distributed Systems, Cambridge Part IB 2021/22 · §2.1, The two generals problem
Now watch what an acknowledgement actually buys. Each one settles the doubt about the message before it — and creates exactly the same doubt about itself.
"The problem is that no matter how many messages are exchanged, neither general can ever be certain that the other army will also turn up at the same time. […] it can be proved that they cannot reach certainty by exchanging any finite number of messages."
Kleppmann, Distributed Systems · §2.1
The notes give the one-line moral on the slide itself: "the only way of knowing something is to communicate it". Certainty about another node is not something you can compute locally. It has to arrive, and arrival is the thing in doubt.
"This thought experiment demonstrates that in a distributed system, there is no
way for one node to have certainty about the state of another node. The only way how a node can know
something is by having that knowledge communicated in a message." Every health check, every heartbeat, every
SELECT 1 is an attempt to buy a fact that cannot be bought outright — only rented, for as long
as the last reply stays plausible.
3. What a system model actually assumes
If certainty is unobtainable, an algorithm has to say out loud what it is assuming instead. That statement is the system model, and it has three independent axes.
| Axis | Choices | What the weakest choice costs you |
|---|---|---|
| Network | reliable · fair-loss · arbitrary | Fair-loss means "Messages may be lost, duplicated, or reordered. If you keep retrying, a message eventually gets through" — so you must build retry and de-duplication yourself |
| Nodes | crash-stop · crash-recovery · Byzantine | Crash-recovery means in-memory state is gone on restart and only disk survives, so every decision you must not forget has to be flushed |
| Timing | synchronous · partially synchronous · asynchronous | This is the axis that decides whether consensus is possible at all |
The timing axis is the one this lesson turns on. Kleppmann's three choices, quoted exactly:
| Model | What it assumes | What you may therefore do | How it fails |
|---|---|---|---|
| Synchronous | "Message latency no greater than a known upper bound. Nodes execute algorithm at a known speed." | Treat a missed deadline as proof of a crash. A perfect failure detector exists here | Catastrophically, and rarely — the assumption is true most of the time, which is what makes it a trap |
| Partially synchronous | "The system is asynchronous for some finite (but unknown) periods of time, synchronous otherwise." | Use timeouts for progress only. Correctness may never depend on them | Gracefully: during a bad period the system stalls rather than diverges |
| Asynchronous | "Messages can be delayed arbitrarily. Nodes can pause execution arbitrarily. No timing guarantees at all." | Nothing that needs a clock. Timeouts are meaningless in this model | It does not fail — it simply cannot deterministically solve consensus (§5) |
Synchrony is the tempting one, and the notes are blunt about the temptation:
"algorithms designed for a synchronous model often fail catastrophically if the assumptions of bounded latency and bounded execution speed are violated, even just for a short while, and even if this happens rarely."
Kleppmann, Distributed Systems · §2.3, Slide 35 commentary
The node that does not know it left
Synchrony is violated from inside as well as outside. Queueing, route reconfiguration, retransmission — and, on the node itself, scheduling, page faults, and garbage collection, where "On large heaps, such pauses can be as long as several minutes".
The consequence is the whole reason failure detection is subtle: "for one node, time appears to 'stand still' while it is paused, and during this time all other nodes continue executing their algorithms normally. Other nodes may even notice that the paused node is not responding, and assume that it has crashed."
So what is a failure detector, really?
The notes name the limit directly. A perfect detector "labels a node as faulty if and only if it has crashed", and its typical implementation is to "send message, await response, label node as crashed if no reply within some timeout". The gap between those two sentences is the entire subject:
"the two generals problem tells us that this is not a totally accurate way of detecting a crash, because the absence of a response could also be due to message loss or delay. A perfect timeout-based failure detector exists only in a synchronous crash-stop system with reliable links; in a partially synchronous system, a perfect failure detector does not exist."
Kleppmann, Distributed Systems · §2.4, Slide 40 commentary
What a real system gets instead is the eventually perfect failure detector, which "May temporarily label a node as crashed, even though it is correct", and "May temporarily label a node as correct, even though it has crashed". Temporarily wrong, eventually right. That is the whole product.
You have priced this before. Lesson 04 chose timeouts by picking "an acceptable rate of false timeouts" — accepting, up front, that some healthy calls would be declared dead. That was not sloppiness. It was the only kind of timeout that exists.
4. The FLP result
Consensus has a precise specification: one or more nodes propose a value, the algorithm decides one of the proposed values, every non-faulty node decides the same value, and a decision is final. Safety (agreement, validity, integrity) plus liveness (termination).
Fischer, Lynch and Paterson showed that you cannot have all of it:
"FLP result (Fischer, Lynch, Paterson): There is no deterministic consensus algorithm that is guaranteed to terminate in an asynchronous crash-stop system model."
Kleppmann, Distributed Systems · §6.1, Slide 107 · citing Fischer, Lynch and Paterson, 1985, "Impossibility of distributed consensus with one faulty process"
Read the three qualifiers, because every escape route lives in one of them.
- Deterministic. The algorithm's next step is a function of its state and the messages it has received. Nothing else.
- Guaranteed to terminate. Not "usually terminates". Not "terminates in the runs we tested". Always, in every possible schedule an adversary may choose.
- Asynchronous. No clocks. No bound on message delay or on how long a node may pause.
Note what FLP does not say. It does not say consensus is unsolvable — real clusters do it thousands of times a second. It does not need a Byzantine node, or many failures. One crash-stop process is enough. What it says is that in a world with no clocks, no deterministic algorithm can promise to finish, and the reason is exactly the two generals problem wearing a different coat: without a clock you cannot distinguish a crashed process from one whose messages are merely still in flight.
Kleppmann's notes make that dependency explicit:
"the assumption of partial synchrony cannot be weakened to asynchrony. The reason is that consensus requires a failure detector (Slide 40), which in turn requires a local clock to trigger timeouts […]."
Kleppmann, Distributed Systems · §6.1
A timeout is not an implementation detail. It is the clock that a failure detector needs, and the failure detector is what consensus needs. Delete the timeout and you have not simplified the algorithm — you have moved it into the asynchronous model, where FLP says it can no longer guarantee it will ever finish. The number in your config file is load-bearing theory.
5. How real algorithms escape it
There are exactly two doors out, and both work by breaking one of FLP's qualifiers.
"It is possible to get around the FLP result by using a nondeterministic (randomised) algorithm. However, most practical systems instead avoid non-termination by using clocks for timeouts."
Kleppmann, Distributed Systems · §6.1
- Drop determinism. Let the algorithm flip a coin. It then terminates with probability 1 rather than with certainty — the adversarial schedule that stalls it for ever becomes a measure-zero event. This is the door Byzantine and blockchain protocols often take.
- Drop asynchrony. Assume partial synchrony: the system behaves for unknown but finite stretches. Set timeouts. Make progress during the good stretches. This is the door Paxos, Raft, Viewstamped Replication and Zab take.
The second door only works because of a division that is easy to state and easy to get backwards:
"Paxos, Raft, etc. use clocks only used for timeouts/failure detector to ensure progress. Safety (correctness) does not depend on timing."
Kleppmann, Distributed Systems · §6.1, Slide 107
"consensus algorithms need to guarantee their safety properties […] regardless of the timing in the system, even if messages are arbitrarily delayed. Only the liveness (namely, that a message is eventually delivered) depends on clocks and timing."
Kleppmann, Distributed Systems · §6.1
Get this backwards and you build the dangerous thing. An algorithm whose safety depends on a timeout is a synchronous algorithm wearing a partially-synchronous costume: it is correct right up to the first long GC pause, and then two nodes both believe they are the leader. The whole craft is confining timing to the liveness half.
6. Residual risk
Your timeout is a tuning parameter for availability, not correctness — until someone makes it one. The moment a piece of application code says "the lock expired, so it is safe to proceed", safety has been made to depend on a clock, and you have re-entered the synchronous model by accident.
Eventually live can be a long eventually. Partial synchrony promises the bad period is finite. It promises nothing about its length. A cluster can be perfectly safe and completely unavailable for as long as the network misbehaves, and no amount of correct implementation shortens that.
False suspicion has a cost you pay in throughput. An aggressive timeout on a loaded cluster produces leader churn: elect, suspect, re-elect, with no progress in between. The system is never wrong and never finishes anything. Lesson 04's "acceptable rate of false timeouts" is the same dial, now attached to a much more expensive machine.
And the assumptions are the product. The notes end the system-models section with the warning the rest of this course keeps earning: "This is the basis for any distributed algorithm. If your assumptions are wrong, all bets are off!"
7. Check yourself
8. Back to your world
Find one timeout in your own system and ask which half it belongs to. If it only decides how long you wait before retrying or failing over, it is a liveness knob and you may tune it freely. If anything downstream treats its expiry as a fact — the lease has lapsed so the old holder must be gone, the node is out of the ring so its writes cannot land — then correctness is resting on a clock, and a stop-the-world pause is a live bug waiting for a busy afternoon.
The sentence worth being able to say in a design review: "that timeout is not tuning. It is the assumption that lets this algorithm terminate at all — and if we let it decide correctness too, we have assumed a synchronous network we do not have."