兩軍問題

兩軍問題（英語：Two Generals' Problem）是電腦領域的假想實驗，顯示以不可靠的通訊渠道交換訊息並達成共識難以實現。問題中，兩支軍隊的將軍只能派信使穿越敵方領土互相通訊，以此約定進攻時間。該問題希望求解如何在兩名將軍派出的任何信使都可能被俘虜的情況下，就進攻時間達成共識。

軍隊位置示意圖：軍隊甲（A1）與乙（A2）派遣信使互相通訊，但信使可能被敵軍（Ｂ）俘虜。

兩軍問題是拜占庭將軍問題的特例，常被編入與電腦網絡相關的入門課程中。在傳輸控制協議（TCP）相關的課程中，問題可用作解釋TCP協議無法保證通訊雙方狀態一致，也適用於其他有訊息丟失風險的通訊。作為認識邏輯的重要概念，問題突出了共識的重要性。一些學者也將問題稱作兩軍悖論（英語：Two Generals Paradox）或協同進攻問題（英語：Coordinated Attack Problem）。兩軍問題是第一個證實無解的電腦通訊問題。證明的重要意義在於，其顯示了對於有通訊出錯風險的更廣泛問題（如拜占庭將軍問題），同樣無解。這也為實現所有分布式一致性協議提供了符合現實的預期。

定義

兩支軍隊由不同將軍領導，準備進攻一座堅固的城市。軍隊在城市附近的兩個山谷紮營。由於有另一個山谷將兩山隔開，兩名將軍只能透過派信使穿越山谷通訊，但這山谷由城市護衛占領，有可能俘虜途徑山谷傳遞訊息的任何信使。

雖然兩軍已約定要同時進攻，但尚未約定進攻時間。要順利攻擊，兩軍必須同時進攻。如果同一時間僅一支軍隊進攻就會戰敗，因此兩名將軍須約定攻擊時間，並確保對方知道自己同意了進攻計劃。但由於傳遞確認訊息的信使與傳遞原始訊息的信使一樣，都可能被俘虜而丟失訊息，即使雙方不斷確認已收到對方的上一條訊息，也無法確保已與對方達成共識。

問題演示

將軍甲首先派信使向將軍乙傳遞訊息「在8月4日9時進攻」。然而，派遣信使後，將軍甲不知道信使是否成功穿過敵方領土。由於擔心自己成為唯一的進攻軍隊，將軍甲可能會猶豫要否按計劃進攻。

為了消除不確定性，將軍乙可以向將軍甲發送確認訊息「我收到了您的訊息，並會在8月4日9時進攻」，但傳遞確認訊息的使者同樣可能會被敵方俘虜。由於擔心將軍甲沒有收到確認訊息而退縮，將軍乙會猶豫要否按計劃進攻。

再次發送確認訊息看來可以解決問題——將軍甲再讓新信使發送確認訊息：「我已收到您確認在8月4日9時進攻」。但是，將軍甲的新信使也可能被俘虜。顯然，無論確認幾次都無法滿足該問題的條件二，即兩方都必須確保對方已同意計劃，兩名將軍總會懷疑他們最後派遣的使者有否順利穿過敵方領土。

歷史

1975年，E. A. Akkoyunlu、K. Ekanadham和R. V. Huber在《網絡通訊設計中的一些限制和取捨（Some Constraints and Trade-offs in the Design of Network Communications）》一文首次提到兩軍問題（但以兩組黑幫表示通訊雙方），並證明問題無解。

1978年，詹姆斯·尼古拉·格雷在《數據庫操作系統筆記（Notes on Data Base Operating Systems）》 一文將問題命名為「兩軍悖論」（Two Generals Paradox），雖然問題並非初次發表，但文獻依然獲廣泛引用證明兩軍問題無解。