二人の将軍問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

定義[編集]

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

2人の将軍は成功するために、同時に軍に都市を攻撃させなければならない。従って相互に通信を行い、攻撃時間を決定し、その時間に攻撃することに合意しなければならない。これをいかに実行するかを考察することが思考実験の内容である。最も簡単な方法では1人の将軍(以下では「1人目の将軍」と呼ぶ)がリーダーとなり、攻撃時間を決定し、これをもう一方の将軍に伝えなければならない。この「問題」を引き起こす要因は、攻撃が成功するために、両将軍が合意された時間に同時に攻撃しなければならないということである。片方の将軍が単独で攻撃を起こすことは失敗であると考えられる。問題は将軍が使えるアルゴリズムを考案することであり、それにはメッセージを送信し、受信したメッセージを処理することで、次の結論に正しく至ることが出来なければならない。

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

ここで将軍が攻撃する時間に合意することは容易であることに注意すべきである。1つのメッセージとそれに対する了解メッセージが正しく送られることで十分である。二人の将軍問題の微妙さは、将軍らが上記の言明に対し、安全に合意するために使用できるアルゴリズムを設計することが不可能であるということである。

脚注[編集]