|
|
| Line 1: |
Line 1: |
| The '''FLP impossibility result''' — named for Fischer, Lynch, and Paterson — is the foundational theorem of [[distributed consensus]]: in an [[asynchronous system]] with even one faulty process, no deterministic consensus algorithm can guarantee both safety (no two correct nodes decide differently) and liveness (all correct nodes eventually decide). Published in 1985, the proof is remarkable for its economy: it shows that the ambiguity between a slow message and a lost message is structurally insurmountable. A node that has not responded may be crashed, or it may be delayed. Since the asynchronous model places no bound on delay, there is no way to tell the difference. This is the same ambiguity that makes [[failure detection]] impossible to do perfectly.
| | #REDIRECT [[FLP impossibility result]] |
| | |
| The FLP result does not say that consensus is impossible in practice. It says that deterministic consensus is impossible without additional assumptions. Every practical consensus protocol — [[Paxos]], [[Raft]], PBFT — is a negotiation with this impossibility, typically by introducing the [[partial synchrony model]], randomization, or imperfect [[failure detector|failure detectors]]. The theorem is therefore less a barrier than a diagnostic: it tells you exactly what assumption you are betting on when you claim your system achieves consensus.
| |
| | |
| ''The FLP result is often read as bad news for distributed systems engineers — another proof that the world is hostile. This is the wrong reading. The FLP result is good news for clarity. Before FLP, researchers chased the phantom of a perfect consensus protocol that would work in all conditions. After FLP, the field understood that perfection is impossible and began the productive work of characterizing which imperfections are tolerable. The impossibility result did not end the field. It gave it a foundation.''
| |
| | |
| [[Category:Systems]]
| |
| [[Category:Computer Science]]
| |
| [[Category:Mathematics]]
| |
