二人の将軍の問題

コンピュータ科学において、二人の将軍の問題（または中国の将軍の問題^{[ 1 ]}）は、信頼性の低い通信回線を介して行動を調整しようとする際の落とし穴や設計上の課題を示すための思考実験である。この実験では、二人の将軍は敵地を経由して使者を送ることによってのみ互いに​​連絡を取ることができる。この実験は、送った使者が捕らえられる可能性があることを知りながら、彼らが攻撃を開始する時間についてどのように合意に達することができるかを問うものである。

2人の将軍の問題は、コンピュータ ネットワークの入門クラスで、より一般的なビザンチン将軍の問題の導入としてよく登場します(特に、TCP がエンドポイント間の状態の一貫性を保証できない理由を示す伝送制御プロトコルに関して)。ただし、通信障害が発生する可能性のあるあらゆる種類の 2 者間通信に適用されます。認識論の重要な概念であるこの問題は、共通知識の重要性を強調します。一部の著者は、これを2 人の将軍のパラドックス、2 つの軍隊の問題、または協調攻撃の問題とも呼んでいます。^{[ 2 ] [ 3 ]} 2 人の将軍の問題は、解決不可能であることが証明された最初のコンピュータ通信問題でした。^{[ 4 ]}この証明の重要な帰結は、ビザンチン将軍の問題のような一般化も任意の通信障害に直面して解決不可能であり、分散一貫性プロトコルに対する現実的な期待の基礎を提供するということです。

それぞれ異なる将軍に率いられた2つの軍隊が、要塞都市への攻撃を準備している。両軍は都市の近くの谷に陣を張っている。3つ目の谷が2つの丘を隔てており、2人の将軍が連絡を取り合う唯一の方法は、谷を通って使者を送ることである。しかし、谷は都市の守備隊に占領されており、谷を通って送られた使者は捕らえられる可能性がある。^{[ 5 ]}

両将軍は攻撃することには合意しているものの、攻撃の時期については合意していない。単独の攻撃軍が全滅するのを避けるため、両将軍の軍隊が同時に都市を攻撃する必要がある。そのため、両将軍は互いに連絡を取り合い、攻撃の時期を決定し、その時期に攻撃することに合意しなければならない。また、各将軍は、相手将軍が攻撃計画に同意したことを知っていることを知らなければならない。メッセージの受信確認は元のメッセージと同様に簡単に失われる可能性があるため、合意に達するには潜在的に無限のメッセージのやり取りが必要となる。^{[ 6 ]}

この思考実験は、彼らがどのように合意に達するかを検討するものです。最も単純な形では、一方の将軍がリーダーであることが分かっており、攻撃の時間を決定し、その時間をもう一方の将軍に伝えなければなりません。問題は、メッセージの送信や受信メッセージの処理など、将軍たちが使用できるアルゴリズムを考案し、それによって正しい結論を導き出すことです。

将軍たちが攻撃のタイミングについて合意に達することは非常に簡単であると仮定すると（つまり、成功したメッセージと成功した確認応答が1つあれば）、2人の将軍の問題の微妙な点は、将軍たちが上記の声明に安全に合意するために使用できるアルゴリズムを設計することが不可能である点にある。

第一将軍はまず「8月4日午前9時に攻撃せよ」というメッセージを送ることから始めるかもしれない。しかし、一度メッセージを送ったとしても、第一将軍は伝令が届いたかどうかを知る術がない。この不確実性から、第一将軍は単独攻撃のリスクを恐れて攻撃を躊躇する可能性がある。

確かに、第二将軍は第一将軍に「メッセージを受け取りました。8月4日午前9時に攻撃を開始します」という確認の返信を送るかもしれない。しかし、確認を伝える使者は捕らえられる可能性があり、第一将軍が確認なしでは攻撃を躊躇するかもしれないことを第二将軍は知っているため、躊躇するかもしれない。

さらなる確認は解決策のように思えるかもしれない。最初の将軍が2回目の確認を送ればよい。「8月4日午前9時に計画された攻撃の確認を受け取りました」。しかし、最初の将軍からのこの新たな使者もまた捕らえられる可能性がある。したがって、確認を何度繰り返しても、各将軍が相手が攻撃計画に同意したことを確信するという2つ目の要件を保証する方法はないことがすぐに明らかになる。両将軍は常に、最後の使者が無事に連絡を取ったかどうかを疑うことになるだろう。^{[ 7 ]}

このプロトコルは決定論的であるため、一定数のメッセージが連続して送信され、そのうち1つ以上が正常に配信され、1つ以上が配信されなかったと仮定します。両将軍が攻撃する確信を共有しているという前提があります。最後に正常に配信されたメッセージについて考えてみましょう。もしその最後のメッセージが正常に配信されていなかったとしたら、少なくとも1人の将軍（おそらく受信者）は攻撃しないことを決定するでしょう。しかし、その最後のメッセージの送信者の視点から見ると、送信および配信されたメッセージのシーケンスは、そのメッセージが配信された場合とまったく同じです。プロトコルは決定論的であるため、その最後のメッセージを送信した将軍はやはり攻撃することを決定します。これで、提案されたプロトコルによって一方の将軍は攻撃し、もう一方の将軍は攻撃しないという状況が生まれ、プロトコルが問題の解決策であるという前提に矛盾が生じました。

メッセージ数が変動する可能性のある非決定性プロトコルは、エッジラベル付き有限木と比較できます。この木では、木の各ノードが、指定された時点までの探索済み例を表します。メッセージを送信する前に終了するプロトコルは、ルートノードのみを含む木で表されます。ノードから各子ノードへのエッジには、子ノードの状態に到達するために送信されたメッセージがラベル付けされます。リーフノードは、プロトコルが終了するポイントを表します。非決定性プロトコルPが存在し、それが「二人の将軍の問題」を解決すると仮定します。すると、上記の固定長決定性プロトコルで使用したのと同様の議論により、P' も「二人の将軍の問題」を解決しなければなりません。ここで、 P'を表す木は、Pの木からすべてのリーフノードとそれらにつながるエッジを削除することによって得られます。Pは有限であるため、メッセージを送信する前に終了するプロトコルが問題を解決することになります。しかし、明らかにそうではありません。したがって、問題を解決する非決定性プロトコルは存在し得ません。

二人の将軍の問題に対処する現実的なアプローチは、通信チャネルの不確実性を受け入れ、それを完全に排除しようとせず、許容できる程度に軽減する方式を用いることです。たとえば、第一の将軍は、全員が捕まる確率は低いと想定して、100人の使者を送ることができます。このアプローチでは、第一の将軍はどんな場合でも攻撃し、第二の将軍はメッセージが受信されれば攻撃します。あるいは、第一の将軍がメッセージのストリームを送信し、第二の将軍がそれぞれに確認応答を送信することで、各将軍は受信するメッセージごとに安心感を増すことができます。しかし、証明で示されているように、どちらも攻撃が協調して行われることを確信することはできません。一方が他方なしで攻撃することを確実に防ぐアルゴリズム（たとえば、4つ以上のメッセージが受信された場合に攻撃する）は存在しません。また、第一の将軍は、各メッセージに、それがn番目のメッセージ1、2、3、...であることを示すマークを送信することができます。この方法により、第二の将軍は通信チャネルの信頼性を把握し、少なくとも1つのメッセージが確実に受信されるよう、適切な数のメッセージを返信することができる。通信チャネルの信頼性が確保できれば、1つのメッセージで十分であり、追加のメッセージは不要となる。最後のメッセージも最初のメッセージと同様に失われる可能性がある。

将軍たちは、伝令が送られて傍受されるたびに命を犠牲にしなければならないと仮定すると、攻撃が連携しているという確信度を最大化するために必要な伝令の数を最小限に抑えるアルゴリズムを設計することができる。連携の確信度を極めて高くするために何百もの命を犠牲にすることを避けるため、将軍たちは、伝令がいないことを、取引を開始した将軍が少なくとも1つの確認を受け取り、攻撃を約束したことを示す兆候として使用することに同意することができる。伝令が危険地帯を横断するのに1分かかると仮定すると、確認を受け取った後に200分間沈黙させることで、伝令の命を犠牲にすることなく極めて高い確信度を達成することができる。この場合、伝令は、攻撃時間が相手側に届いていない場合にのみ使用される。 200分経過した時点で、それぞれの将軍は次のように推論できる。「200分間、追加のメッセージを受け取っていない。これは、200人の伝令が危険地帯を越えられなかったか、あるいは相手の将軍が攻撃を確定し、実行を決意しており、私もそうすると確信しているかのどちらかだ」。

二人の将軍の問題とその不可能性の証明は、1975年にEA Akkoyunlu、K. Ekanadham、およびRV Huberによって「ネットワーク通信の設計におけるいくつかの制約とトレードオフ」^{[ 8 ]}で初めて発表され、73ページから2つのギャンググループ間の通信の文脈で説明されています。

この問題は、1978年にジム・グレイ^{[ 9 ]}が「Notes on Data Base Operating Systems」 ^{[ 10 ]}の465ページから始めて、「二人の将軍のパラドックス」と名付けました。この文献は、問題の定義と不可能性の証明の出典として広く引用されていますが、どちらも前述のように以前に発表されています。

• コンセンサスアルゴリズム