ビザンチン将軍問題？

質問

ビザンチン将軍問題って何でしょうか？Byzantine Generals Problem（BGP）と言われているらしいですが。検索しても解説や説明がうまく引っかかりませんでした。できれば分かりやすく（難しい数式無しで）説明いただけるとありがたいです。

回答No.3

punchan_jp · ベストアンサー

ビザンチンの由来ですが、ちょっとわかりませんね。

下の補足で挙げられているページ（ゼミか何かの資料みたいですね）
にあるランポートの論文が最初の文献だと思うんですが、彼が名付
けた可能性が高いです。

簡単に問題の部分だけ訳すと、

指揮将軍は以下の条件のもとでn-1人の中将に命令を送らなければならない。
1. 全ての忠実な中将は同じ命令に従う。
2. 指揮将軍が忠実であれば、全ての忠実な中将は彼の送った命令に従う。

一般に、m人裏切り者がいるときに 3m+1 より少ない将軍という場合には、
解はない。

論文そのものではないので、もとの表現を見るには、1982年の雑誌
を探してこないといけないですけど。

で、Byzantine の意味を辞書で見ると、ビザンチンのという意味も
もちろんありますが、他に、複雑なとか、ごちゃごちゃした、とか
陰険なとかの普通の単語としての用法があります。これにひっかけ
たのかもしれません。

お礼

いろいろお答えいただきまして、ありがとうございました。
ビザンチン帝国というのがあったのですねぇ。

回答No.2

punchan_jp

まず、敵を複数の軍隊で包囲している状況を考えます。それぞれに
将軍がいますので、攻撃するかしないかを判断するには N 人の
（それぞれ平等の権限をもつ）将軍間で合意しないことには危険で
す。ここで、将軍のなかに M 人の裏切り者がいてそれが誰かわか
らないとき、残りの将軍が正しい判断をするにはどのような通信方
式をとればいいか、というのがビザンチン将軍問題です。

この問題はフォールトトレランス（耐故障）技術における基本問題
です。N個の要素のうちM個が壊れて誤った情報を出しても、システ
ム全体としては正しく動作することを保証する方法を考えるために、
よく引き合いに出されます。

もちろん、要素が壊れたからといって、誤るばかりでなく、停止す
るとか、どこかに壊れない（にくい）要素があるとか、平等ではな
くてどこかに権限が集中してるとか、いろいろなモデルが考えられ
ます。

悪意をもって組織的に嘘をつく可能性があるというビザンチン将軍
問題はかなり厳しいモデルの一つですが、これだけでは条件があい
まいすぎるので、実際にはもっと条件を厳密にして、精密なモデル
で議論します。

補足

むむぅ。なるほど。メールでじゃんけんするのはどうしたらいいのか、
ってのと似てる気が（違うか）。ありがとうございました。ちなみに
ビザンチンでの史実から名付けられたのでしょうか？そんな事件が
あったんでしょうか？

回答No.1

noname#24736

下記のページに詳細が書いてあります。
私には専門外で判りませんので、URLの紹介だけにします。

参考URL：

http://nicosia.is.s.u-tokyo.ac.jp/pub/staff/hagiya/gakujutsu98/gakushin.txt

補足

上記サイトは私も検索でヒットしました。読んでみたのですが、イマイチピンとこなかったのです。その他、
http://www.cs.cornell.edu/cs614-sp98/notes/byzantine.html
にも英語で書いてあったのですが、私の理解力不足か分かりませんでした。ビザンチンに由来した？歴史上の事件から取られた？という由来まで分かると非常にありがたいのですが……。