合意問題とFLP不可能性｜分散システム

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：障害モデル（クラッシュ・オミッション・ビザンチン）　|　関連：Paxos・Raft

要点（BLUF）

合意問題：複数ノードがそれぞれ値を提案し、全員が同じ1つの値に決める。満たすべきは3条件——合意性（全員同じ）・妥当性（決めた値は誰かの提案）・停止性（いつか決まる）。
FLP不可能性（1985）：完全非同期かつ1ノードでもクラッシュしうる環境では、合意性と停止性を常に両立する決定的アルゴリズムは存在しない。
実用はこれを回避する：①部分同期＋タイムアウト（活性を「ほぼ確実」に緩める）、②ランダム化（確率1で停止）。Paxos/Raftは①の道。安全性は常に守り、活性だけ条件付きにするのが定石。

問題設定 ── 合意の3条件

\text{合意性: 全プロセスが同じ値を決定} \quad\wedge\quad \text{妥当性: その値は提案された値}

\text{停止性(活性): すべての正しいプロセスはいつか決定する}

合意性と妥当性は安全性（悪いことが起きない）、停止性は活性（良いことがいつか起きる）。リーダー選出（リーダー選出（Bully・Ring））もアトミックコミット（2相コミット・3相コミット）も、この形に帰着します。

FLP ── なぜ非同期だと不可能か

非同期＝メッセージ遅延や処理速度に上限が無いモデル（障害モデル（クラッシュ・オミッション・ビザンチン））。ここでの核心的困難：

「遅い」と「死んだ」が原理的に区別できない。

flowchart LR
    A["ノードからの応答が来ない"] --> Q{"どっち?"}
    Q -->|"待ち続ける"| L["活性を失う（永久待ち）"]
    Q -->|"死んだとみなし進む"| S["後で復活し別決定→安全性を失う"]

FLPの証明は「どんなアルゴリズムにも、決定が永遠に先延ばしされる実行（スケジュール）が必ず存在する」ことを、二価（bivalent）状態（まだ0にも1にも転びうる状態）が必ず残せることから示します。たった1つの遅いメッセージで、決定を無限に遅らせられる——だから「常に停止」は保証できません。

正しさの観点 ── 安全性は犠牲にしない

FLPが言うのは「停止性（活性）が保証できない」であって、「合意性（安全性）が破れる」ではありません。だから実用システムは：

安全性（2つの値を確定しない）は無条件で守る。
活性（いつか決まる）だけを「ネットワークがいずれ十分安定すれば決まる」と条件付きにする。

この分離が分散合意の設計哲学です。Paxos（Paxos）もRaft（Raft）も、ネットワークが荒れている間は決まらないかもしれないが、間違った決定は絶対にしない。

回避策の比較

回避	やり方	代表
部分同期	普段は同期的と仮定し、タイムアウトで故障検出。荒れたら一時的に進まない	Paxos・Raft・2相コミット・3相コミット
ランダム化	コイン投げで対称性を破り、確率1で停止	Ben-Or・一部のBFT
故障検出器	「最終的に正確」な故障検出器Ωを仮定	Chandra-Toueg

なぜ分散だと難しいか（直観）

単一マシンの「合意」は自明（変数に代入するだけ）。分散では、全員が同時に同じ事実を知ることができない（共通知識の不可能性）。誰かが落ちたかも分からないまま「全員一致」を作るのが本質的に難しい。FLPはその難しさの数学的な底を示した結果です。

⚠️ よくある誤解・落とし穴

「FLPがあるから合意は実装できない」→ 実装できる。FLPは「常に停止する保証は無い」だけ。実際はほぼ常に速やかに停止する。
「タイムアウトを使えばFLPを破った」→ 破っていない。タイムアウト＝部分同期の仮定を追加しただけ。仮定が崩れる間は停止しない。
「FLPは安全性も否定する」→ 否定するのは活性のみ。安全性は守れる。
「ビザンチンの話」→ FLPはクラッシュ故障1個でも成立する、より強い不可能性。

対応ラボ

なし（不可能性の定理）。FLPを回避した実際の合意の挙動は Raft・リーダー選出（Bully・Ring）のラボで観察します。