The FLP Impossibility Result
What you'll learn: Why achieving consensus in a fully asynchronous distributed system is mathematically impossible when even one node might fail.
The Theoretical Foundation
The FLP Impossibility Result (named after Fischer, Lynch, and Paterson, 1985) is a foundational theorem in distributed systems. It proves that no deterministic consensus algorithm can guarantee agreement in an asynchronous system if even one process might fail — even if that failure is just a crash (not malicious behavior).
What "Asynchronous" Means Here
In a fully asynchronous system, there are no timing assumptions:
- Messages can be delayed arbitrarily (but eventually arrive)
- Processes can run at any speed
- There's no way to distinguish a slow process from a crashed one
The Core Problem
Imagine three friends trying to decide where to eat dinner via text message, but:
- Messages can arrive in any order
- You can't tell if someone's phone died or they just haven't replied yet
- No one can call a "timeout" because there's no shared clock
FLP proves that under these conditions, if one person's phone might have died, you cannot design a protocol that guarantees everyone will eventually agree on a restaurant while also guaranteeing the system won't get stuck waiting forever (making progress).
The Real-World Impact
This doesn't mean consensus is impossible in practice — it means we must make assumptions to work around it:
- Add timeouts (partial synchrony)
- Use randomization (non-deterministic)
- Accept that consensus might occasionally stall
Key Takeaway: The FLP result proves deterministic consensus is impossible in purely asynchronous systems with failures, forcing real systems to add timing assumptions or randomization to achieve practical consensus.