付け焼き刃でビザンチン将軍問題

ちょっと前に噂になったビットコインに関する記事でたまに見かけるビザンチン将軍問題について。

この問題の面倒くさいところは、反逆者(故障箇所)が返事をしないという訳ではなく、適当な返事をするところらしい…

ビザンチン将軍問題 - Wikipedia

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

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

 

Lamportの方法

この問題の解法としてLamportさんが提唱した方法があるそう(以下)

  1. 各将軍は, 他将軍に自部隊の情報を伝える
  2. 各将軍は, 受け取った情報をベクトル化する
  3. 作ったベクトルを他の将軍に送る
  4. ベクトルを比較, 過半数が同じならば正しいとみなす

ということです。

 

実際に試してみる

各将軍は, 他将軍に自部隊の情報を伝える

正常だとこんな感じ

f:id:Etclsc:20160825165129p:plain

異常状態だと適当なお返事をする(イメージ)

f:id:Etclsc:20160825170322p:plain

 

情報をベクトル化する

f:id:Etclsc:20160825165807p:plain

 

ベクトルを他の将軍に送る

またまた正常と異常のイメージ

f:id:Etclsc:20160825170336p:plain

f:id:Etclsc:20160825170344p:plain

 

ベクトルを比較する

過半数が同じであれば正解とみなすので[1, 2, ?, 4]となる

他の将軍でも(多分)同じ答えになる → 正常な将軍間で合意が取れる

f:id:Etclsc:20160825171044p:plain

 

ということでした。

 

合ってるかどうかもわからない上、大部分があやふや

すごく雑にプログラムを書きましたが、なんとも 

GitHub - Etclsc/ByzantineGenerals: ビザンチン将軍問題に関する簡単なプログラム

 

参考

http://research.nii.ac.jp/~f-ishikawa/work/enpit15/CloudBasic-3-quorum.pdf

http://www-higashi.ist.osaka-u.ac.jp/~nakata/mobile-cp/chap-07j.pdf