Impossibility of Distributed Consensus with One Faulty Process
Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson1985Journal of the ACM 1985
Read it on doi.org(opens in a new tab)Why this one
Read this before Paxos Made Simple. FLP is the paper that turns consensus from a programming problem into a physics problem: in a fully asynchronous system, one crashed process is enough to make guaranteed termination impossible. The trap is to read it as saying consensus cannot be built, which is false. Real systems use timeouts, leaders, failure detectors, leases, quorums, and operational assumptions to escape the model. The point is that every escape has a price, and this paper teaches you to look for it. When a design doc says a coordinator is dead, ask how it knows. When a database claims consistency during partitions, ask which timing assumption it smuggled in. This is worth your evening because it gives you the mental checksum for Paxos, Raft, ZooKeeper, Spanner, and every service that says "exactly once" with a straight face.
What to take away
- A crashed process and unbounded message delay are indistinguishable to the rest of the system.
- The proof hinges on bivalent states, where both decision outcomes are still possible.
- Consensus protocols work by adding assumptions FLP forbids, usually timing, randomness, or failure detectors.
Reads with
- Paxos Made Simple
paxos is the practical escape hatch from flp's asynchronous impossibility model
- In Search of an Understandable Consensus Algorithm
raft makes the same timing and leader assumptions easier to see in an implementation
- ZooKeeper: Wait-free Coordination for Internet-scale Systems
zookeeper shows consensus assumptions packaged as a coordination service engineers actually use