友人に「明日の午後3時に駅前で会おう」とメッセージを送ったのに返信が来ないと、相手が読んだかどうかわからず、なんとなく不安になります。「了解」と返事が来ても、今度はその返事を自分が受け取ったことを相手が知っているのかが気になるかもしれません。コンピュータ科学には、この終わりのない確認の連鎖を二人の将軍の物語で説明した有名な問題があります。それが「二人の将軍問題（Two Generals’ Problem）」です。
二人の将軍問題とは、簡単に言えば「メッセージが途中で消えるおそれのある通信路では、双方が同じ行動に合意したという事実を決して完全には確信できない」ことを示す思考実験を意味します。ネットワークや分散システムを初めて学ぶときに必ずと言っていいほど登場し、コンピュータ通信の問題のなかで、解決できないことが初めて証明された問題とされています。
本記事では、二人の将軍問題がどのような状況を描いているのかから、なぜ解けないのか、この問題がどこから始まったのか、そして実際の技術がこの限界をどう扱っているのかまでを順に見ていきます。
確認の確認が終わらない二人の将軍問題
二人の将軍問題とはどんな状況か
この問題は、城を挟んだ二つの軍隊の物語から始まります。
（1）別々に陣を張る二つの軍隊
二人の将軍が率いる軍隊が、一つの城を攻めるためにそれぞれ別の丘に陣を張っています。二つの軍隊が同時に攻撃すれば城を落とせますが、片方だけが攻撃すると、その軍隊は大敗してしまいます。
（2）危険な谷を越える伝令
二人の将軍が連絡を取る方法は、城の軍隊が守る谷を通って伝令を送ることだけです。伝令はいつ捕まってもおかしくなく、送った側には伝令が到着したかどうかを知るすべがありません。
（3）将軍たちが求める確信
将軍たちは攻撃の時刻を決めるだけでなく、「私たち二人ともその時刻に攻撃する」という事実を互いに確実に知りたいと考えています。この確信があってこそ、安心して軍を動かせるからです。
このように二人の将軍問題は、信頼できない通信路の上で双方が行動を合わせようとするときに生じる難しさを、シンプルな場面に凝縮して示しています。
なぜ最後まで確信できないのか
伝令を何度もやり取りすれば解決しそうに思えますが、確認を増やすほど同じ悩みが繰り返されるだけです。
（1）最初のメッセージの不安
最初の将軍が「明朝6時に攻撃する」という伝令を送っても、伝令が着いたかどうかわからないため、自分だけが攻撃することになるのではとためらってしまいます。
（2）延々と続く返信
二人目の将軍が「受け取った、6時に攻撃する」という返信を送ると、今度は二人目の将軍がその返信が届いたかどうかを心配します。最初の将軍が返信を受け取ったという確認をまた送っても、その最後の伝令もやはり捕まるおそれがあります。
（3）最後の伝令のパラドックス
何度やり取りしても、最後に送った伝令が到着したかどうかを送った側は知ることができません。最後の伝令が捕まっても送った側から見れば状況はまったく同じなので、その伝令一人に攻撃するかどうかがかかっている方式なら、片方だけが攻撃する事態が起こりえます。そのため、決まった回数だけ確認をやり取りするどんな方法でも、二人の将軍を完全に足並みをそろえさせることはできないという結論になります。
要点は、確認のメッセージも元のメッセージと同じくらい簡単に失われうるということです。確認をどれだけ重ねても、最後の一枚の不確実性はそのまま残ります。
二人の将軍問題はどこから始まったのか
この問題は、コンピュータネットワークが発展し始めた1970年代に整理されました。
- 最初に掲載された論文（First Publication）：1975年、E. A. アッコユンル（E. A. Akkoyunlu）、K. エカナダム（K. Ekanadham）、R. V. ヒューバー（R. V. Huber）が、ネットワーク通信の設計上の制約を扱った論文で、この問題と解決できないことの証明を初めて発表しました。この論文では、将軍の代わりに互いに連絡を取り合う二つのギャング団で状況を説明していました。
- 名前を付けた人（Naming）：データベース研究者のジム・グレイ（Jim Gray）が1978年、データベースのオペレーティングシステムに関する文章でこの問題を「二人の将軍のパラドックス（Two Generals Paradox）」と呼んだことで、現在の将軍の物語として広く知られるようになりました。
- より大きな問題への拡張（Byzantine Generals Problem）：1982年、レスリー・ランポート（Leslie Lamport）、ロバート・ショスタク（Robert Shostak）、マーシャル・ピーズ（Marshall Pease）は、複数の将軍のなかに裏切り者が混じっている状況を扱った「ビザンチン将軍問題」を発表しました。二人の将軍問題は、この問題を学ぶ前の入門としてよく紹介されます。
実際の技術はこの限界をどう扱っているのか
完全な確信が不可能なら、現実の技術は不確実性をなくすよりも、許容できる水準まで減らす道を選びます。
（1）何度も送る
最初の将軍が伝令を何人も送れば、全員が捕まる確率は大きく下がります。確信とまではいかなくても、成功の可能性を十分に高めることができます。
（2）確認と再送
インターネットの基本的な通信規約であるTCP（Transmission Control Protocol）は、接続を確立するときに3回のメッセージをやり取りし、データを送ったあと受信の確認が決められた時間内に来なければ再送します。この方式も双方の状態が常に同じであるとは保証できませんが、実用に十分な信頼性を生み出します。
（3）沈黙も合図として使う
一定時間何の連絡もなければ相手が計画を受け入れたものとみなす、とあらかじめ約束しておく方法もあります。伝令を送る回数を減らしながらも、高い確信を得ることができます。
これらの方式にはどれも、完璧さの代わりに「十分に信頼できること」を目標にしているという共通点があります。
二人の将軍問題は、どれほど精巧な技術でも、信頼できない通信路の限界を完全には越えられないという事実に気づかせてくれます。今日私たちが使うメッセンジャーや決済システム、クラウドサービスも、この限界を認めたうえで設計されています。
完全な確信は不可能だという事実を受け入れ、そのうえに安全装置を積み重ねること。それが信頼できるシステム設計の第一歩です。
