computer science//distributed systems//FLP impossibility

2026-02-20

The FLP impossibility result states that in a fully asynchronous network, where every message is eventually delivered but with no bound on its delay, no deterministic algorithm can guarantee that a set of processes reaches agreement if even one of them may crash. Fischer, Lynch and Paterson proved it in 1985, and it explains why every practical consensus algorithm leans on timeouts.

The intuition is the slow node. A process waiting for a peer's vote cannot tell a peer that crashed from one whose message is merely delayed. If it waits, a crash leaves it waiting forever; if it decides without that vote, the late message may arrive and show that the decision split the group. The proof turns this into a strategy for an adversarial scheduler of message delays, which can keep any deterministic protocol moving from one undecided configuration to another forever.

Safety can always be kept; progress cannot be guaranteed.

Paxos and Raft never commit two different values under any timing, and they make progress only while the network behaves well enough for their timeouts to mean something. When it does not, they stall rather than lie.

Each escape route weakens one assumption. Partial synchrony assumes delays are bounded most of the time, which is what Raft's election timeouts rely on; randomization makes termination probable instead of certain; failure detectors give each process a hint about who has crashed.

It concerns guarantees in the worst case. Real networks are rarely adversarial, and Raft clusters commit writes all day in production; the theorem tells the engineer what has to be traded (progress during bad periods) and why a timeout value is part of the correctness argument.

It is often confused with the CAP theorem. FLP is about agreement under unbounded delay with a single crash; CAP is about consistency against availability once the network actually splits. Both are limits that distributed consensus is designed around.