Notesdistributed🌱 seedling
FLP Impossibility
Also: FLP · FLP Result · Fischer Lynch Paterson
In a fully asynchronous system, no deterministic algorithm can guarantee that consensus terminates if even one process may crash. Practical algorithms keep safety unconditionally and get liveness from timeouts or randomness.
Why it exists
It explains why every real consensus system can stall, and why they all lean on timing assumptions for progress.
How it works
- Asynchronous model: no bound on message delay or processing time, no clocks.
- A crashed process is indistinguishable from a slow one. Waiting for it may wait forever; not waiting may decide without information that mattered.
- The proof shows an adversarial schedule can keep the system undecided indefinitely.
- Ways around it: partial synchrony (the network is eventually timely; use timeouts), randomization (terminate with probability 1), failure detectors.
- Raft and Paxos: safety holds even if every timing assumption fails; leader election uses timeouts and randomness, so liveness returns when the network behaves.
Trade-offs
| Design response | Cost |
|---|---|
| timeouts (partial synchrony) | false suspicions trigger needless elections |
| randomized timeouts | probabilistic, not guaranteed, progress |
| stop rather than diverge | unavailability during partitions or storms |
In practice
- Split votes in Raft are the FLP shape in miniature: they could repeat forever; randomized election timeouts make that vanishingly unlikely.
Pitfalls
- Reading it as "consensus is impossible". It's impossible to guarantee termination deterministically in a purely asynchronous model; real networks are usually timely.
- Confusing it with CAP Theorem: FLP concerns termination with crashes, CAP concerns availability versus linearizability under partitions.
Connections
- Part of
- Consensus
- Learn first
- Partial Failure
Recall
These cards are also in your review deck, scheduled with spaced repetition.