二人の将軍問題

ウィキペディア

二人の将軍問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/19 15:53 UTC 版)

二将軍の問題（英: Two Generals' Problem）は計算機科学における思考実験であり、不確実なリンクでの通信により行動を同期する際の落とし穴や、設計課題を明示するためのものである。より一般的なビザンチン将軍問題と関連しており（ただし発表時期はこちらがはるかに早い）、コンピュータネットワークに関する入門的授業に（特にTCPに関連して）しばしば登場するが、他の通信手法にも応用可能である。二つの軍隊問題や、調整攻撃の問題と呼ばれることもある。

定義

2つの軍がそれぞれ将軍に率いられ、要塞化した都市の攻撃準備をしている。軍はそれぞれ、都市の近くの丘に宿営を張っている。2つの丘は谷により分断され、2人の将軍が通信をする唯一の方法は、谷を経由して使者を送ることである。不幸なことに、谷は都市の防衛者が占拠しており、谷を通過する使者が捕獲される可能性がある。

2人の将軍はそれぞれの丘の位置につく前に、攻撃することは合意しているが、攻撃時間については合意していない。成功するためには、同時に都市を攻撃しなければならず、さもなくば単独で攻撃した軍は敗北する。従って相互に通信を行い、攻撃時間を合意し、かつ合意を相手が知っていることを確認しなければならない。了解メッセージも本来のメッセージと同じぐらい簡単に無くなる可能性があるため、潜在的には、合意に至るには無限のメッセージが必要になる。

これをいかに実行するかを考察することが思考実験の内容である。最も単純な形式化では、1人の将軍（以下では「1人目の将軍」と呼ぶ）がリーダーとなり、攻撃時間を決定し、これをもう一方の将軍に伝えなければならない。問題は将軍らが使えるアルゴリズムを考案することであり、それにはメッセージを送信し、受信したメッセージを処理することで、次の結論に正しく至ることが出来なければならない:

はい、私達は同時に合意された時間に攻撃を行います。

問題の仮定として、将軍らに攻撃時間のこだわりはない (つまり、1つのメッセージとそれに対する了解メッセージが正しく送られることで合意にいたれる) とされる。その上で二人の将軍問題の本質は、将軍らが上記の条件のもと、安全に合意できるアルゴリズムを設計することが不可能であるということである。