二人の将軍問題
2つの軍がそれぞれ将軍に率いられ、要塞化した都市の攻撃準備をしている。軍はそれぞれ、都市の近くの丘に宿営を張っている。2つの丘は谷により分断され、2人の将軍が通信をする唯一の方法は、谷を経由して使者を送ることである。不幸なことに、谷は都市の防衛者が占拠しており、谷を通過する使者が捕獲される可能性がある。
2人の将軍はそれぞれの丘の位置につく前に、攻撃することは合意しているが、攻撃時間については合意していない。成功するためには、同時に都市を攻撃しなければならず、さもなくば単独で攻撃した軍は敗北する。従って相互に通信を行い、攻撃時間を合意し、かつ合意を相手が知っていることを確認しなければならない。了解メッセージも本来のメッセージと同じぐらい簡単に無くなる可能性があるため、潜在的には、合意に至るには無限のメッセージが必要になる。
これをいかに実行するかを考察することが思考実験の内容である。最も単純な形式化では、1人の将軍(以下では「1人目の将軍」と呼ぶ)がリーダーとなり、攻撃時間を決定し、これをもう一方の将軍に伝えなければならない。問題は将軍らが使えるアルゴリズムを考案することであり、それにはメッセージを送信し、受信したメッセージを処理することで、次の結論に正しく至ることが出来なければならない:
はい、私達は同時に合意された時間に攻撃を行います。
問題の仮定として、将軍らに攻撃時間のこだわりはない (つまり、1つのメッセージとそれに対する了解メッセージが正しく送られることで合意にいたれる) とされる。その上で二人の将軍問題の本質は、将軍らが上記の条件のもと、安全に合意できるアルゴリズムを設計することが不可能であるということである。