|
ビザンチン将軍問題（ビザンチンしょうぐんもんだい、）とは、相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題である。フォールトトレラントシステムでの多数決の妥当性や分散コンピューティングの処理の妥当性に関わる問題と言え、二人の将軍問題を一般化したものと言える。 ビザンチン将軍問題に帰結される故障や障害をビザンチン故障（、あるいはビザンチン障害）と呼ぶ。また、ビザンチン将軍問題が発生しても全体として正しく動作するシステムをビザンチン・フォールトトレラント性（）があるという。 == 問題 == ビザンチン将軍問題は、東ローマ帝国（ビザンチン帝国）の将軍達がそれぞれ軍団を率いてひとつの都市を包囲している状況で発生する。将軍達は都市攻撃計画について合意したいと考えている。最も単純な形では、将軍達は攻撃するか撤退するかだけを合意決定する。一部の将軍達は攻撃したいと言うだろうし、他は撤退を望むかもしれない。重要な点は将軍達はひとつの結論に合意しなければならないということで、一部の将軍だけで攻撃を仕掛けても敗北することは明らかで、全員一致で攻撃か撤退かを決めなければならないのである。また、彼らはそれぞれ離れた場所に各軍団を配置しており、メッセンジャーを相互に送ることで合意を目指す。 問題を複雑にさせるのは、一部の将軍が反逆者であって、時折最適でない戦略に票を投じたりして混乱させるのである。例えば、9人の将軍が投票して4人が攻撃で4人が撤退に票を投じたとすると、9人目の（反逆者でもある）将軍は一部の将軍達には撤退票を送り、他の将軍達には攻撃票を送るかもしれない。9人目から撤退票を受けた将軍達は撤退するだろうし、残りの将軍達は攻撃を開始して敗走することになるだろう。 誠実な将軍達（反逆者でない）が全員一致で攻撃（あるいは撤退）に同意している場合、ビザンチン・フォールトトレラント性は達成可能である。ある将軍が正しい判断をする場合、他の誠実な将軍達は必ずその判断に合意する。さもなくば、合意された戦略を選択することは見当違いの方法ということになる。 この問題を合意問題として定式化したのは、マーシャル・ピーズ、ロバート・ショスタク、レスリー・ランポートの1980年の論文である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ビザンチン将軍問題」の詳細全文を読む スポンサード リンク
|