分散処理を勉強した記録～その26～

この記事は、
「分散処理システム」著：真鍋義文　森北出版株式会社
を参考にしています。

今回は、「ビザンチン将軍問題」についてです。

ビザンチン帝国が、とある敵国の街を包囲しています。

将軍と部隊1～3からなる軍勢で、
「攻撃」か「和解」を選んで行動します。
部隊が一気に攻撃すれば成功率が上がるので、
全員で畳みかければ済む話なのですが、
「将軍」と「部隊」はそれぞれ敵国と内通している可能性があります。

「将軍」と「部隊」が裏切った場合、
攻撃指令を出していても、
内通している部隊は攻撃せず、
敵と内通していない部隊は攻撃し、
ビザンチン帝国の戦力が削られてしまいます。

「部隊」が裏切った場合、
「将軍」が攻撃指令を出しても、
内通している部隊は攻撃しません。

敵国の街を陥落させるにはどうしたらいいでしょうか。
ここで、以下のような条件を満たすようにしてみましょう。
1.内通していない部隊同士が合意する。
2.将軍が内通していない場合、将軍の出した指令で合意する。

ただし、この条件は部隊が2つしかない場合は成り立ちません。

将軍から「和解」せよ、と指令が来たとしても、
もう片方の部隊には「攻撃」せよ、と言っているかもしれません。
この場合、もう片方の部隊に指令がどっちなのかを教えてもらうとします。

ここで、もう片方の部隊が「攻撃」指令だった、
と言ってきた場合、裏切っているのは「将軍」でしょうか？
それとも「部隊」でしょうか？
判断がつきません。なので、この場合は合意が成り立ちません。

今回はここまでです。ありがとうございました。