FLP不可能性とビザンチン耐性合意(PBFT)

合意には2種類の「無理」がある

分散合意（複数ノードが1つの値・同じ順序に同意すること）を理解する上で、避けて通れない2つの限界があります。1つはタイミングの限界＝FLP不可能性、もう1つは悪意の限界＝ビザンチン障害への耐性です。前者は「いつ決まるかを保証できない」、後者は「嘘をつくノードが混じると正直者の多数派だけでは足りない」という話で、性質がまったく異なります。

前提として合意アルゴリズムが満たすべき性質を3つに整理します。

• 合意性 (agreement): 正常ノードは皆同じ値を決める。
• 妥当性 (validity): 決まる値は誰かが提案した値である（でたらめな値を決めない）。
• 停止性／活性 (termination / liveness): いつかは必ず決まる。

合意性と妥当性をまとめて安全性 (safety)、停止性を活性 (liveness) と呼びます。FLPもPBFTも、この「安全性と活性をどこまで両立できるか」という一点を巡る議論です。

FLP不可能性：非同期では決定的合意ができない

FLP不可能性 (Fischer-Lynch-Paterson, 1985) は次を主張します。「完全非同期 (fully asynchronous) なメッセージ通信モデルで、1台でもノードが停止しうるなら、安全性と活性を常に満たす決定的合意アルゴリズムは存在しない」。たった1台の停止故障すら確実には扱えない、という強い結果です。

なぜか。完全非同期とは「メッセージ遅延に上限がなく、ノードの処理速度にも下限がない」モデルです。この世界では、あるノードからの応答が来ないとき、それが本当に停止したのか、ただ極端に遅いだけなのか、原理的に区別できません。

ノードBから応答が来ない…さて、どちらか？
  ケース1: B はクラッシュした  → B を待たず先へ進むべき
  ケース2: B は生きていて遅いだけ → B を待つべき（先へ進むと矛盾の恐れ）
完全非同期では両者を見分ける手段（時計・タイムアウト）が無い
→ 「待つ」も「進む」も間違いうる

FLPの証明は、どんなアルゴリズムにも**どちらにも転びうる中間状態（bivalent configuration、二価状態）**が必ず存在し、メッセージ遅延を巧妙に操作すれば、その状態から決して抜け出せない実行（合意に到達しない無限実行）を作れることを示します。決定が「あと1通のメッセージ」に懸かる瞬間を作り、そのメッセージを遅延させ続ければ、永遠に決まらない、というわけです。

FLPの回避：前提を少しだけ強める

FLPは「完全非同期」という最悪の前提に依存します。現実の合意は、この前提をわずかに緩めることで活性を取り戻します。主な手段は3つです。

実用上もっとも普及しているのが部分同期です。「普段はネットワークがいつ安定するか分からないが、ある未知の時刻 GST (Global Stabilization Time) 以降は遅延に上限が効く」と仮定します。するとタイムアウトが意味を持ちます。タイムアウトは「停止」と「遅延」を区別する近似手段で、GST以降は正しく機能するため、最終的に合意へ到達できます。

Paxos も Raft も、この発想です。両者ともリーダーの心拍が一定時間途絶えたらタイムアウトして再選挙しますが、これはまさに部分同期の仮定を使って活性を確保する動きです。安全性（過半数の交わりによる無矛盾性）はタイミングに依存せず常に成立し、タイムアウトはあくまで「いつか進む」ための活性側の道具にすぎません。詳細は 分散合意アルゴリズム（Paxos / Raft） を参照してください。

ビザンチン障害：停止より厄介な「嘘をつく」故障

Paxos/Raft が想定するのは停止故障 (crash-stop)、つまりノードは黙って止まるだけで嘘はつかない、という穏やかな故障モデルです。これに対しビザンチン障害 (Byzantine fault) は、ノードが任意の異常な振る舞いをするモデルです。バグ・改ざん・乗っ取り・矛盾したメッセージの送り分けまで含み、悪意ある攻撃者を想定します。語源は「ビザンチン将軍問題」で、裏切り者の将軍がいても忠実な将軍だけで作戦を一致させられるか、という問いに由来します。

停止故障なら「応答が無いノード＝故障」と単純化できますが、ビザンチンノードは正常に応答しつつ内容が偽だったり、相手ごとに違う値を送りつけたりします。だから過半数 (floor(N/2)+1) では足りません。多数派の中に嘘つきが紛れ込めるからです。

PBFTと3f+1の必要性

PBFT (Practical Byzantine Fault Tolerance, Castro-Liskov 1999) は、部分同期下でビザンチン障害に耐える実用的な合意プロトコルです。最大 f 台のビザンチンノードに耐えるには、全体で N >= 3f + 1 台が必要——これがPBFTの核心的な下限です。なぜ「3」なのかを論理から導きます。

合意を進めるには**クォーラム（応答を待つ定足数）**を設定しますが、ビザンチン環境では2つの制約を同時に満たす必要があります。

全 N 台、うち最大 f 台がビザンチン（悪意）。クォーラムサイズを Q とする。

制約1（活性）: 故障 f 台が応答しなくても Q 台は集まる必要がある
        →  Q <= N - f

制約2（安全性）: 任意の2つのクォーラムの交わりに、
        正直なノードが最低1台は含まれる必要がある
        2つの Q が重なる台数 = 2Q - N、そのうち悪意は最大 f
        → (2Q - N) - f >= 1

制約2から 2Q >= N + f + 1、制約1から Q <= N - f。この2式を両立させると 2(N - f) >= N + f + 1、整理して N >= 3f + 1 が出ます。クォーラムサイズは Q = 2f + 1 に取ります。

つまり、故障で f 台落としても、残りから安全な多数派を取り出し、しかもその重なりに正直者を必ず1台残す——この三重の要求を満たすのに、停止故障なら2倍強で足りた台数が、ビザンチンでは3倍強に膨らむのです。停止故障合意が N >= 2f+1（過半数）で済むのと対比すると、嘘への耐性のコストが一目で分かります。

PBFTの1回の合意は、リーダー（primary）からの pre-prepare → prepare → commit の3フェーズで進みます。prepare/commit の各段で 2f+1 の一致を確認することで、たとえリーダーが裏切っても、正直ノード同士が同じ順序にしか確定しないことを保証します。リーダーが不正と疑われれば view-change で交代します。停止故障版の2フェーズ（2相コミット や Raft のログ複製）に対し、ビザンチンではもう1フェーズ多いのも、嘘の送り分けを潰すための代償です。

まとめ