## 定義 2人の将軍の問題(Two Generals Problem)とは、分散システムにおける同意の説明でもっとも著名な思考実験の1つである。2つの軍隊が2人の将軍に率いられて要塞化された都市の両側に布陣しており、同時に攻撃した場合のみ包囲を成功できる。両将軍は伝令を送ることで通信でき、残された課題は攻撃を実行に移すかどうかについての同意だけである。将軍Aがメッセージ`MSG(N)`を送り、将軍Bがそれを受け取れば確認応答`ACK(MSG(N))`を返すが、この確認応答を運ぶ伝令もまた敵に捕らえられ伝達に失敗する可能性がある。それを確かめるにはBは二次的な確認応答`ACK(ACK(MSG(N)))`を待たねばならず、両将軍がどれだけ確認の返事を送り合っても、安全に攻撃に移れると確信するには常に次のACKが必要という状況が無限に続く。この思考実験は、リンクの障害が存在し通信が完全に非同期である場合、2つの集団間で同意を実現するのは原理的に不可能であることを示す。ここでタイミングの仮定は一切置かれておらず、両将軍が応答にかけられる時間の長さに上限は設定されていない。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 8 基本事項の紹介と概要]] §8.4) たとえTCPのようなパーフェクトリンク(信頼できる配信・重複なし・生成なしを保証するリンクの抽象化)を使ったとしても、パーフェクトリンクはその名前にもかかわらず完璧な配信を保証するものではなく、参加ノードが常時有効で転送のみに関心があることを保証することもできない。この問題の亜種として一方の将軍の位が高い場合や、正確な時刻について合意する必要がある場合があるが、これらの詳細によって問題の本質(両将軍は同意しなければならない)は変わらない。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 8 基本事項の紹介と概要]] §8.4) ## 横断的知見 - 現時点では『詳説 データベース』第8章が唯一のソースであり、横断的知見はまだ蓄積されていない。[[FLPの不可能性]]・[[分散コンセンサス]]と突き合わせることで、2者間の具体的な思考実験(本概念)とN者・一般形式の不可能性証明(FLP)、実用的な合意アルゴリズム(Raft・Paxos)がどう連続しているかを整理できる可能性がある。 ## 未解決の問い - 2人の将軍の問題(2者間・非同期・リンク障害のみを前提とする不可能性)と[[FLPの不可能性]](N者・非同期・プロセスクラッシュを前提とする不可能性)は、どちらがどちらを一般化した関係にあるか、あるいは独立した証明なのか。本章はこの関係を明示していない。 - 実用システムは2人の将軍の問題が示す不可能性にもかかわらず、タイムアウト・再送・べき等性を組み合わせることで実務上「十分に安全な」合意を達成している。この「理論上不可能だが実務上十分」というギャップは、どのような前提の緩和(部分同期モデルの採用など)によって埋められているか。 - 位の高い将軍がいる亜種(一方が意思決定権を持つ)は、リーダーベースの合意アルゴリズム(Raft等)の考え方に近い。この亜種と実際のリーダー選出プロトコルの関係を、[[分散コンセンサス]]の知見と突き合わせて整理する価値はあるか。 ## 関連 - ソース: [[@2021__OReillyJapan__詳説 データベース - Chapter 8 基本事項の紹介と概要]] - 概念: [[FLPの不可能性]] / [[ビザンチン障害]] / [[分散コンセンサス]] ## 出典 - Alex Petrov, *詳説 データベース*, オライリー・ジャパン, 2021, 8章, §8.4.