ビザンチン将軍問題

ビザンチン将軍問題の最新ニュースをまとめて検索！

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

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

[編集] 問題

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

問題を複雑にさせるのは、一部の将軍が反逆者であって、時折最適でない戦略に票を投じたりして混乱させるのである。例えば、9人の将軍が投票して4人が攻撃で4人が撤退に票を投じたとすると、9人目の（反逆者でもある）将軍は一部の将軍達には撤退票を送り、他の将軍達には攻撃票を送るかもしれない。9人目から撤退票を受けた将軍達は撤退するだろうし、残りの将軍達は攻撃を開始して敗走することになるだろう。

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

[編集] ビザンチン故障

ビザンチン故障は、分散コンピューティングにおいて、コンピュータとネットワークがハードウェア故障やネットワーク輻輳・切断やソフトウェアのバグや悪意ある攻撃によって予期しない動作をすることである。ネットワーク上で分散した何らかのオブジェクトがアルゴリズムを実行すべく協調動作している。これらオブジェクトを便宜上プロセスと呼ぶ。

アルゴリズムの各ステップはプロセスが実行する。故障したプロセスは予期しない動作をする。故障していないプロセスの動作は正しいとする。故障したプロセスがとりうる動作にはいくつかの種類がある。

• 本来返すべき応答を返さなくなる。アルゴリズムの実行を停止する。これをクラッシュ障害とか沈黙型障害と呼ぶ。
• 何らかの応答を返すが、その応答が正しいかどうか不明な場合。これをビザンチン故障またはビザンチン障害と呼ぶ。このときプロセスはアルゴリズムの次のステップを正しく実行したり、全く関係ないステップを実行したりする。

ビザンチン故障に耐性のあるアルゴリズムはそれらの障害に対処し解決する。そのようなアルゴリズムは一般に、ビザンチン故障の状態にあるプロセスを何個まで許容し対処できるかで特徴付けられる。これを回復力（resilience） t で表す。

プロセスは信頼できるがプロセス間の通信が信頼できないとする特殊ケースが二人の将軍問題である。

[編集] ビザンチン・フォールトトレラント性

ビザンチン・フォールトトレラント性の目的は、ビザンチン故障に対して防御できることである。最初の解決策は 1982年、ACM Transactions on Programming Languages and Systems誌上で Lamport、Shostak、Peaseによって示された（参考文献参照）。

Lamport、Shostak、Pease らはビザンチン将軍問題を「司令官と副官」問題に帰結することができると指摘することから始めた。「司令官と副官」問題とは、誠実な副官は司令官が誠実である場合にその命令を忠実に守らなければならないというものである。おおまかに言えば、将軍達の投票では、その票を司令官の命令と考えることができる。

• メッセージに嘘があったとしても、反逆的な将軍が全将軍の人数の3分の1未満であれば「ビザンチン・フォールトトレラント性」は達成される。一人の司令官と二人の副官を想定したとき、司令官が反逆者ならば「司令官と副官」問題を解決できないことを証明することで、3分の1以上の反逆者がいる場合の解決策がないことを証明したのである。A、B、C の三人がいて、A が反逆者だったとする。A が B には攻撃すると言い、C には撤退すると言い、B と C が相互にやりとりして A からどう指示されたかを教えあった場合、B も C も誰が反逆者であるかを判断できない（例えば、B か C が反逆者だった場合でも指示が食い違う）。将軍の人数を n、反逆者の人数を t としたとき、解決策が存在するのは n が (3 × t + 1) 以上の場合のみである。

• 2番目の解決策は、偽造不可能なサイン(現代のコンピュータシステムでは、これは公開鍵暗号で達成されるだろう)を必要とするが、任意の数の反逆的な将軍がいても「ビザンチン・フォールトトレラント性」を維持可能である。

• また、すべての将軍が直接互いと通信できるわけではないいくつかの状況におけるバリエーションも提示されている。

[編集] 参考文献

• 論文 "The Byzantine Generals Problem" (PDF形式) Lamport, Shostak, Pease: ACM Transactions on Programming Languages and Systems, Vol.4, No.3 (1982年7月、382～401頁)

[編集] 関連項目

• フォールトトレラント設計
• フォールトトレラントシステム
• ピア・ツー・ピア
• 二人の将軍問題