二人の将軍問題とは?——「了解しました」の返信を何往復重ねても、合意が確実にならない理由を問う思考実験

二人の将軍問題とは、通信が途中で失われうる状況で、離れた二人が同時攻撃の約束を確実に成立させられるかを問う思考実験。確認の返信を重ねても最後の1通の到着は保証できず、完全な合意には届かない。分散システムの設計から、事業の「了解です」までを通して、確実さの限界との付き合い方を考える。

#二人の将軍問題 #合意 #分散システム #共有知識 #コミュニケーション

夜、谷をはさんで二つの軍が布陣している。谷の底には敵の城がある。どちらの軍も単独では城を落とせず、二つの軍が同じ時刻に攻めたときだけ勝てる。片方だけが攻めれば、全滅する。

二人の将軍は、伝令を谷に走らせて連絡を取るしかない。ところが、伝令は敵の領内を通るため、途中で捕まることがある。将軍Aは「明朝6時に攻める」と書いて送った。さて、Aは安心して準備に入れるだろうか。

一通では足りない

伝令が着いたかどうか、Aには分からない。届いていなければ、Bは動かず、Aだけが突撃して全滅する。だからAは、Bからの返事を待つ。

Bは手紙を受け取った。「了解、6時に攻める」と返信を出す。ところが今度は、Bが同じ心配をする。返信がAに届かなかったなら、Aは約束が成立したと思えず、攻めないかもしれない。だからBも、Aからの確認の確認を待ちたくなる。

Aが「返信を受け取った」と送れば、今度はAがその到着を気にする。返信を重ねるたびに、最後の1通を送った側だけが、相手に届いたかどうか分からない。どれだけ往復しても、この構造は変わらない。

不可能性は、往復の数ではなく構造にある

この思考実験は「二人の将軍問題」と呼ばれる。1970年代にコンピュータ科学の分野で、通信の確実さを論じる例として知られるようになった。データベースの取引を扱ったジム・グレイの1978年の論文でも、この名前で紹介されている。

結論は、通信が失われうる限り、どれだけメッセージを重ねても、双方が確実に同時攻撃を約束できるプロトコルは存在しないというものだ。

理由は、背理法で示せる。仮に、ある有限回のやり取りで確実に合意できる手順があったとする。その中で最短のものを考える。最後の1通を取り除いても、手順が成り立つなら、より短い手順があることになり、最短という前提に反する。逆に、最後の1通がなければ成り立たないなら、合意はその1通の到着に懸かっていることになり、届く保証がないので確実とは言えない。どちらに転んでも、確実な合意は作れない。

ここで大事なのは、伝令がたまたま捕まる確率の話ではない、という点だ。成功する確率は、往復を重ねれば高くできる。しかし「確実に」成立するという保証は、確率がどれほど高くても得られない。

「確実」を諦めて、設計するということ

では現実のシステムは、どうやって動いているのか。答えは、確実な合意を諦めて、次のどれかを選んでいることにある。

確率を受け入れる。 何度か往復して、十分に高い確率で成功すればよしとする。インターネットの通信が、再送と確認応答を組み合わせて信頼性を作っているのは、この考え方だ。

やり直せるようにする。 同じ操作が二回届いても結果が変わらないように設計しておけば、届いたかどうか分からないときは、もう一度送ればよい。確認の確認を無限に続ける代わりに、再実行が安全な形に作り替える。

時間で切る。 返事がなければ、一定時間後に失敗として扱う。「届いたかもしれないが、届いていないものとして動く」と決めておけば、判断が止まらない。

もう一つ、関連する問題がある。1982年にレスリー・ランポートらが論文で示した「ビザンチン将軍問題」は、将軍の中に嘘をつく裏切り者が混ざる場合に、忠実な将軍たちが合意できるかを問う。こちらは、裏切り者が全体の3分の1未満なら合意できる手順があることが知られている。二人の将軍問題が「連絡が失われる」ことの限界を示すのに対し、ビザンチン将軍問題は「相手が信用できない」ことの限界を示す。似た名前だが、問うているものは違う。

事業の「了解です」に持ち込む

この構造は、サーバーの中だけの話ではない。

「確認しました」の最後の1通。 日程調整のメールで「では、その日でお願いします」と送ったあと、相手がそれを読んだかどうかは、返事が来るまで分からない。返事を受け取った側は「ありがとうございます」と返すか迷う。ここで返信が止まるのは、私たちがどこかで確認の連鎖を打ち切っているからだ。

打ち切りの位置を、事前に決めているか。 打ち切りが暗黙のままだと、重要な約束で「届いていない」ことに後から気づく。大事な約束ほど、確認の仕方を先に決めておく価値がある。たとえば「前日の正午までに一言ください」「返事がなければ予定どおり進める」と、期限と既定の動作を添える。

やり直せる形にしておく。 会議の日時を一度送って終わりにせず、当日朝に再度知らせる。同じ内容を二度受け取っても困らない作りにしておけば、届いたかどうかの不安は小さくなる。

本当に取り返しがつかない約束は、同時に動かさない。 二つの組織が、同じ瞬間に何かを実行しなければならない設計は、通信の確実さに全面的に依存する。可能なら、片方が先に動いても被害が小さい手順に組み替える。将軍たちが全滅するのは、「同時でなければならない」という条件があるからだ。

問いを残す

  • いま進めている約束のうち、最後の1通が届いたかどうか、誰も確かめていないものはどれか
  • 確認のやり取りを、どこで打ち切ると決めているか。その位置は、全員が同じ認識を持っているか
  • 「同時でなければ成立しない」と思い込んでいる手順は、片方が先に動いても壊れない形に組み替えられないか
Share

🧪 同じカテゴリの記事

🔀 他のカテゴリの記事