The Theoretical Ceiling
Before diving into how consensus algorithms work, it is worth understanding a fundamental theoretical constraint: the FLP Impossibility Result, named after Fischer, Lynch, and Paterson who proved it in 1985.
The FLP result states that in a purely asynchronous distributed system — one where there are no bounds on message delivery time — it is impossible to guarantee that a consensus algorithm will always terminate, even if only a single node can fail.
This sounds alarming, but it is important to understand what it does and does not mean. It does not mean consensus is impossible in practice. It means you cannot simultaneously guarantee all three of these properties:
- Safety: The system never returns an incorrect result (no two nodes decide on different values).
- Liveness: The system always eventually returns a result (it does not hang forever).
- Fault Tolerance: The system continues to work despite node failures.
Real-world algorithms like Raft and Paxos handle this by making practical assumptions about timing. They use randomized timeouts and heartbeats to ensure liveness in practice, accepting that in pathological network conditions (extreme message delays), they may temporarily stall rather than produce an incorrect result. They always prioritize safety over liveness — a Raft cluster that cannot reach quorum will refuse to commit writes rather than risk inconsistency.
This trade-off is the core design philosophy: it is better to be unavailable than to be wrong.