裏切り者を見破る「ビザンチン将軍問題」
ある国に9人の将軍がいます。将軍同士はあまり仲が良くないので、決め事をするときはいつも伝言で直接会おうとしません。
今まさに敵の国が攻めてこようとしても、将軍たちは集まって作戦会議をしません。
敵に勝つために2つの作戦があります。
作戦①:攻めてくる真っ向から敵に立ち向かう
作戦②:自分の国で鉄砲で返り討ちにする
(作戦の内容な適当ですw)
敵に勝つには多数決で多かった方の作戦を9人の将軍全員で実行する必要があります。
最初の伝言で各将軍の意見は以下のようになりました。
各将軍が知ることができるのは、「どの将軍がどちらの作戦に賛成したか」だけです。
作戦①:A、B、C、D、X
作戦②:E、F、G、H、X
おや。将軍Xが両方の作戦に賛成しているようです。おかしいですね。
実は将軍Xは敵の国のスパイで裏切り者だったのです。
このままだと、将軍A、B、C、Dは自分たちの作戦①がで決まったと勘違いし
将軍E、F、G、Hは作戦②が多数決で決まったと勘違いしていまいます。
その結果、2つの作戦を中途半端な勢力で実行してしまい、敵に負けてしまいます。
裏切り者の存在に気づくには、伝言の中に以下の2つを加えることで解決できます。
ⅰ :他の武将から、各武将がどっちの作戦に賛成したか聞く
ⅱ :ⅰで聞いた情報を他の武将と共有する
この解決策を実行すると、武将Aが知ってる情報は以下の通りになります。
B→A の情報:
作戦①→A(自分)、B、C、D、X
作戦②→E、F、G、H
C→A の情報:
作戦①→A(自分)、B、C、D
作戦②→E、F、G、H、X
将軍Aは裏切り者Xが相手によってデタラメな情報を流してることが分かります。
各武将が他の武将から情報を聞けば聞くほど、Xの言ってることがデタラメであることが明確になります。
そうなったら、裏切り者Xのことは無視して8人だけで作戦を決めればよいことになります。