The FLP Theorem
10 hours ago
- #consensus
- #distributed systems
- #FLP theorem
- The FLP theorem is an impossibility result about distributed consensus, stating that a system cannot guarantee consensus within finite time if one node is faulty.
- The model assumes deterministic computers with no global clock or randomness; messages can be reordered or delayed arbitrarily.
- State transitions occur when a computer receives a message, changing its local state and possibly sending new messages.
- The theorem shows that in a fault-tolerant consensus protocol, there's always an infinite path where consensus is never reached.
- Two cases are considered: messages delivered to different computers (non-overlapping effects) or the same computer (recovery scenario).
- Both cases lead to contradictions, proving that consensus cannot be guaranteed in an asynchronous system with one faulty process.
- Practical systems often rely on clocks or probabilistic methods to achieve liveness, despite the theoretical impossibility.
- The FLP theorem highlights the challenges of livelock in consensus systems, such as repeated leader elections.