FLP不可能性
1985年に証明された定理。非同期環境では、ノードが一つでもクラッシュしうる限り、停止性と安全性を両立する決定的な合意アルゴリズムは存在しない。
名前はフィッシャー、リンチ、パターソンの頭文字から。ここでの「非同期」とは、メッセージの到達時間に何の保証もないことを指す。実用上の帰結は、Paxos、Raft、PBFT といった現実の合意アルゴリズムがいずれも FLP を何らかの形で回避していることだ。方法は三つあり、(a) 部分同期のようにタイミングに関する仮定を置く、(b) 乱択を使う、(c) 障害検出器を使う、である。CAP定理と並んで、分散システム設計を支える理論的な大黒柱の一つといえる。