FLP不可能性定理（非同期合意の限界）

FLP不可能性定理とは

FLP不可能性定理（Fischer・Lynch・Paterson, 1985）は、分散システム理論の出発点となる結果です。主張は鋭く、次の一言に尽きます。

完全非同期モデルでは、たった1つのプロセスがクラッシュする可能性があるだけで、必ず停止して合意に達する決定性アルゴリズムは存在しない。

ここで合意（コンセンサス）とは、複数のプロセスが各自の初期値を持ち寄り、全員が同じ1つの値に決める問題です。リーダー選出、トランザクションのコミット可否、レプリカ間の値の確定など、分散システム（/devops/microservices/）の根幹はほぼすべてこの形に帰着します。

合意問題の3条件

正しい合意アルゴリズムは、次の3つを同時に満たす必要があります。FLPはこのうち最後の1つが達成不能だと示します。

• 合意性（Agreement）：決定したプロセスは全員、同じ値を決める。
• 妥当性（Validity）：決まる値は、誰かの初期値である（勝手な値を作らない）。
• 停止性（Termination）：故障していないプロセスは、いずれ必ず何らかの値を決める。

合意性と妥当性は安全性（悪いことが起きない）、停止性は活性（良いことがいつか起きる）に対応します。FLPが突き崩すのは停止性です。

モデルの前提を正確に押さえる

定理の強さは「前提のきびしさ」にあります。次の条件下での話です。

注目すべきは、これが極めて弱い故障想定だという点です。故障は「1個」「クラッシュのみ」、ネットワークは値を失わない。それでも不可能なのですから、より過酷な現実（複数故障・ビザンチン故障・メッセージ消失）ではなおさら困難です。FLPは下限を与えているのです。

なぜ不可能なのか：直観

核心は、完全非同期では「故障したプロセス」と「単に遅いプロセス」を区別できないことです。

あるプロセスPからの応答が来ない。Pがクラッシュしたのか、メッセージが極端に遅れているだけなのか、受信側には判定する手段がありません。遅延に上限がない以上、「これだけ待っても来ないなら故障」というタイムアウトの正当化が原理的にできないのです。

ここから証明は次の構造をとります。

1. アルゴリズムの実行が向かう先を、最終的に決まる値で色分けする。まだ決まっていない構成を二価（bivalent） ＝「0にも1にもなりうる」状態と呼ぶ。
2. 初期構成の中に、必ず二価なものが存在することを示せる（もし全初期構成が一価なら妥当性に反する）。
3. 二価な構成からは、たった1つのメッセージ配送を選ぶだけで、再び二価な構成へ遷移させられることを示す。鍵となる1通のメッセージを「あと少し」遅らせ続ければよい。
4. これを繰り返すと、決して一価（決定）に到達しない無限の実行が構成できる。その間どのプロセスもクラッシュしていない。

つまり敵対的なスケジューラは、決定を引き起こす決定的な1通を永遠に先送りすることで、停止性を破れます。「故障を1個許す」とは、この1通をあたかも故障で失われたかのように遅らせてよい自由を敵に与えることに等しいのです。

だから実用アルゴリズムは前提を崩す

FLPは「合意を諦めよ」ではなく、「完全非同期・決定性・確実な停止のすべては同時に持てないので、どれかを緩めよ」という設計指針です。実際の合意アルゴリズムは、FLPの前提のどれかを意図的に外しています。

• 部分同期：「ずっと非同期ではなく、いつか（GST以降）は遅延に上限がある期間が来る」と仮定します。RaftやPaxosのタイムアウトは、この同期的な期間が訪れたときに前進（リーダー確定）するための仕掛けです。安全性は常に守りつつ、停止性は同期期間に賭けます。
• 故障検出器：「あるプロセスを故障と疑う」モジュールを別建てし、その正確さに最低限の保証（最終的には本当の故障を必ず疑い、正常なプロセスを疑わなくなる）を仮定します。Chandra-Touegは、合意を解くのに必要な検出器の最も弱い条件を特定しました。
• 乱択：コイン投げを入れ、停止性を確率1で（期待有限ステップで）達成します。FLPは決定性アルゴリズムの定理なので、乱数を使えば回避できます。

実務へのインパクト

この定理は抽象的に見えて、運用判断に直結します。

• タイムアウトは恣意的でよい、と割り切る：「正しいタイムアウト値」は理論上存在しません（遅延に上限がないため）。短すぎれば誤検知でリーダーが頻繁に交代し、長すぎれば障害復旧が遅れる。安全性は値に依存せず守られ、影響するのは活性（前進の速さ）だけだと理解しておくと、チューニングの判断が明確になります。
• 「落ちた」と「遅い」は本質的に見分けられない：ヘルスチェックや故障検出は近似であり、誤検知をゼロにはできません。カオスエンジニアリング（/devops/chaos-engineering/）で遅延注入を試すと、この区別不能性が実システムでどう顔を出すかを体感できます。
• CAP定理との関係：分断（P）時に一貫性（C）と可用性（A）を両立できないというCAPは、FLPと地続きの話です。どちらも「非同期な世界で安全性と活性は同時に保証しきれない」という同じ岩盤に立っています。サービスメッシュ（/devops/service-mesh/）のリトライやタイムアウト設定も、結局はこのトレードオフの調整に他なりません。

まとめ

• FLP不可能性定理：完全非同期・クラッシュ故障1個・決定性の下では、必ず停止して合意するアルゴリズムは存在しない。
• 真因は故障と遅延を区別できないこと。敵対者は決定を引き起こす1通を永遠に遅らせ、無限の二価状態を構成できる。
• 否定されるのは停止性（活性）だけで、合意性・妥当性（安全性）は守れる。
• だから実用合意は部分同期・故障検出器・乱択でFLPの前提を崩し、現実的に終了させている。Paxos/Raftは定理を破ったのではなく、前提の外で動いている。