FLP Impossibility Result Explained
On this page
What consensus requires
Several nodes must agree on one value: who's the leader, whether a transaction commits, which command comes next in a replicated log. A correct consensus algorithm must satisfy:
- Agreement: no two correct nodes decide different values.
- Validity: the decided value was proposed by some node.
- Termination: every correct node eventually decides.
It sounds simple. In 1985, Fischer, Lynch and Paterson proved a surprising limit.
The FLP impossibility result
The intuition: a node can't tell a crashed peer from a very slow one (Day 1). An algorithm waiting for that peer might wait forever; an algorithm that stops waiting might decide while the "slow" peer, which was alive all along, decides differently. The proof shows that for any algorithm, there's always some unlucky schedule of message delays that keeps it undecided indefinitely, while still respecting agreement.
The proof's key word is bivalent: a state from which either decision is still possible, depending on what happens next. FLP shows two things. Some starting state is bivalent. And from any bivalent state, whatever step the algorithm takes next, a schedule exists that leads to another bivalent state, while every message still gets delivered eventually. Each step looks like progress, but the system can be kept forever in a state where both outcomes remain open. Delaying one critical message, which no node can tell apart from a crash, is always enough.
What FLP doesn't say: the escape routes
It doesn't say consensus is impossible in practice. It says no algorithm can guarantee termination under all possible timings in a purely asynchronous model. The escape routes come from relaxing assumptions:
| Relaxation | How it helps | Used by |
|---|---|---|
| Partial synchrony: delays are eventually bounded, even if we don't know when | Algorithms make progress once the network behaves for long enough | Paxos, Raft, PBFT |
| Failure detectors and timeouts | Suspect slow nodes and move on, accepting occasional wrong suspicions | Leader election in Raft and ZooKeeper |
| Randomization | Random choices break the unlucky schedules with probability 1 | Ben-Or's algorithm, randomized election timeouts |
How Paxos and Raft live with FLP
Paxos and Raft (Days 15 and 16) make a precise choice: they never violate safety (agreement), whatever the timing, but they may fail to make progress while the network is badly behaved, for example during repeated failed elections or a partition with no majority. Once things calm down, they decide.
That's the right trade for real systems: a coordination service that stalls briefly is far better than one that lets two nodes believe they hold the same lock. When you see an etcd or ZooKeeper cluster unable to elect a leader under severe network trouble, you're watching FLP's boundary in practice.
Why this matters to application engineers
- Timeouts are guesses. Every failure detector can be wrong (Day 20), so designs must stay safe when it is.
- Prefer safety over liveness for data that must be correct: refuse to act without a majority rather than risk two decisions.
- Don't build your own consensus. Use etcd, ZooKeeper, a consensus-based database, or a managed service; the subtle cases FLP points to are where homemade protocols break.
Check yourself
A deterministic algorithm that guarantees consensus terminates under every possible message timing in a fully asynchronous system where one node may crash.
They assume partial synchrony and use timeouts. Safety, never deciding two different values, holds no matter how bad the network is; liveness, eventually deciding, is only guaranteed once the network is stable long enough for a leader to stay in place.
In an asynchronous system they look identical, so an algorithm can't safely decide whether to keep waiting or proceed without the node.
No. It means no algorithm can guarantee termination in every possible timing. In practice networks are usually well-behaved, so consensus systems decide quickly almost all the time.
It explains why consensus-backed systems can stall during network trouble, and why timeouts, retries and clear handling of unknown outcomes are unavoidable.