ビザンチン将軍問題

問題の内容

敵の都市を包囲するビザンチン帝国の複数の軍を想定する。各軍を率いる将軍たちは伝令を介してしか連絡が取れず、攻撃か撤退かについて全員が同じ計画で一致しなければならない（半数だけが攻撃すれば全滅する）。ところが将軍の中には裏切り者がいて、ある将軍には「攻撃」、別の将軍には「撤退」と、相手ごとに食い違う内容を伝えてくる。このとき、忠実な将軍全員が同じ計画に合意し、かつ少数の裏切り者に合意内容を歪められないようにできるか、というのがこの問題である。

比喩は軍隊だが、想定されているのは計算機のノードやプロセス²である。故障したノードは、単に応答を止めるだけでなく、壊れたデータを送る、宛先ごとに異なる値を返す、正常に振る舞っているふりをする、といったあらゆる挙動を取りうる。こうした故障を「ビザンチン障害」と呼ぶ。

主要な結果

論文が示した中心的な結果は2つある。ひとつは、伝令が口頭で伝える（＝メッセージ²の偽造や改竄を防ぐ手段がない）場合、裏切り者がm人いるとき、参加者全体がn ≥ 3m+1 を満たさなければ合意は不可能だという定理である。裏切り者が全体の3分の1以上を占めると解けなくなるということで、将軍3人・裏切り者1人という最小の例ですら合意できない。

もうひとつは、偽造できない署名付きのメッセージを使えるなら、裏切り者が何人いても合意が可能になるという結果である。「誰が何を言ったか」を第三者に転送可能な形で証明できるようになると、問題の難しさが質的に変わる。この対比は、暗号技術が分散合意において果たす役割を端的に示している。

名前の由来

この寓話は当初アルバニア軍の将軍たちの話として語られていたが、実在する国を裏切り者の集団として描くことになりかねないため、ジャック・ゴールドバーグの提案で、すでに滅んだビザンチン帝国に置き換えられたという経緯がある。結果として「ビザンチン」は分散システムの用語として定着し、ビザンチン障害、ビザンチン耐性（Byzantine fault tolerance, BFT）といった派生語を生んだ。

応用と広がり

航空機や宇宙機の制御系では、複数の冗長な計算機やセンサのうち一部が異常値を出しても系全体が正しく動くことが求められるため、この問題設定が実際の設計要件として扱われてきた。1999年にミゲル・カストロとバーバラ・リスコフが発表した PBFT（Practical Byzantine Fault Tolerance）は、n ≥ 3f+1 という条件のもとで実用的な性能を達成し、ビザンチン耐性を理論上の話から実装可能なものにした。

2009年以降はブロックチェーンの文脈で再び広く参照されるようになった。参加者が誰でも出入りでき、その中に悪意ある者が混じることを前提に台帳の内容を一致させるという課題は、ビザンチン将軍問題と同じ構造を持つためである^※1。