The theorem
The FLP result, named for Fischer Lynch and Paterson, proves that in a fully asynchronous system where even one node may crash, no deterministic protocol can guarantee consensus in bounded time. It is one of the deepest results in distributed computing.
Why it holds
In an asynchronous network you cannot tell a crashed node from a slow one, because there is no bound on message delay. The proof shows there is always an execution where the protocol stays stuck deciding, unable to make progress without risking inconsistency.
What it does not say
FLP forbids guaranteed termination, not consensus in practice. It does not say consensus is usually impossible, only that no algorithm can always decide in bounded steps under worst case timing.
How real systems escape it
- Timeouts add a partial synchrony assumption so progress happens when the network behaves.
- Randomization lets protocols decide with probability one, sidestepping the deterministic limit.
This is why Raft and Paxos use timeouts, accepting they may stall during pathological delays but stay safe.
Key idea
FLP proves no deterministic protocol can always reach consensus in an asynchronous network with a crash, so real systems rely on timeouts or randomization.