ビザンチン将軍問題

ビザンチン将軍問題（ビザンチンしょうぐんもんだい、英語: Byzantine Generals Problem）とは、相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題である1。フォールトトレラントシステムでの多数決の妥当性や分散コンピューティングの処理の妥当性に関わる問題と言え、二人の将軍問題を一般化したものと言える。

ビザンチン将軍問題に帰結される故障や障害をビザンチン故障（Byzantine Failure、あるいはビザンチン障害）と呼ぶ。また、ビザンチン将軍問題が発生しても全体として正しく動作するシステムをビザンチン・フォールトトレラント性（Byzantine Fault Tolerance）があるという。

問題

ビザンチン将軍問題は、東ローマ帝国（ビザンチン帝国）の首都コンスタンティノープルを攻略するオスマン帝国の将軍たちがそれぞれ軍団を率いて、ひとつの都市（コンスタンティノープル）を包囲している状況で発生する。将軍たちは、都市攻撃計画について合意したいと考えている。最も単純な形では、将軍たちは、攻撃するか撤退するかだけを合意決定する。一部の将軍たちは攻撃したいと言うだろうし、他は撤退を望むかもしれない。重要な点は、将軍たちはひとつの結論で合意しなければならないということである。つまり、一部の将軍だけで攻撃を仕掛けても敗北することは明らかで、全員一致で攻撃か撤退かを決めなければならないのである。また、将軍たちは、それぞれ離れた場所に各軍団を配置しており、メッセンジャーを相互に送ることで合意を目指す。

問題を複雑にさせているのは、一部の将軍たちが反逆者であって、時折最適でない戦略に票を投じたりして混乱させることである。例えば、9人の将軍が投票するとして、その内の4人が攻撃に投票し、別の4人は撤退に投票した場合、9人目の（反逆者でもある）将軍は、撤退に投票した将軍たちには撤退票を送り、攻撃に投票した将軍たちには攻撃票を送ることができる。すると、この9人目の将軍から撤退票を受けた将軍たちは(撤退が過半数であると判断して)撤退するだろうし、残りの将軍たちは(攻撃が過半数であると判断して)攻撃を開始するだろう（しかし攻撃はうまくいかないだろう）。更に問題を複雑にするのは、将軍たちは物理的に離れた場所にいるため、使者に投票の信書を運ばせねばならないが、票を届けるのに失敗する場合もあるし、偽の票に改竄される可能性もあることである。

誠実な将軍たち（反逆者でない将軍たち）が全員一致で攻撃（あるいは撤退）に同意している場合、ビザンチン・フォールトトレラント性は達成可能である。ある将軍が正しい判断をする場合、他の誠実な将軍たちは必ずその判断に合意する。さもなくば、合意された戦略を選択することは、見当違いの方法ということになる。

この問題を合意問題として定式化したのは、マーシャル・ピーズ、ロバート・ショスタク、レスリー・ランポートの1980年の論文である