The FLP Impossibility Result
You'll learn: Why achieving deterministic consensus in asynchronous distributed systems is fundamentally impossible when even a single process might fail.
The Shocking Impossibility
The FLP theorem (named after Fischer, Lynch, and Paterson, 1985) is one of the most important impossibility results in distributed computing. It proves mathematically that no deterministic algorithm can guarantee consensus in an asynchronous system if even one process might crash.
This might seem strange—surely we can just wait for all correct processes to agree? The problem lies in asynchrony: you cannot distinguish between a slow process and a crashed one. If you wait forever for a potentially-crashed process, you violate liveness (making progress). If you proceed without it, you risk violating safety (agreement on the correct value).
Why This Matters
Think of three friends trying to decide on a restaurant via text messages that arrive at unpredictable times. If one friend's phone dies (crashes), the other two can't tell if they're just slow to respond or truly offline. Do they wait indefinitely? Or decide without them and risk choosing somewhere the crashed friend already vetoed?
FLP proves that no algorithm can always satisfy both requirements:
- Safety: All working processes agree on the same value
- Liveness: The system eventually decides something
In practice, systems work around FLP by relaxing one constraint—often using randomization, timeouts (making the system partially synchronous), or accepting that consensus might occasionally stall.
Key Takeaway: The FLP theorem proves deterministic consensus is impossible in purely asynchronous systems with even one potential crash failure, forcing real systems to make practical compromises between safety and liveness.