两军问题

军队位置示意图：军队甲（A1）与乙（A2）派遣信使互相通訊，但信使可能被敵军（Ｂ）俘虏。

两军问题（英語：Two Generals' Problem）是電腦领域的假想實驗，显示以不可靠的通訊渠道交换訊息并达成共识难以实现。问题中，两支军队的将军只能派信使穿越敌方领土互相通訊，以此约定进攻時間。该问题希望求解如何在两名将军派出的任何信使都可能被俘虏的情况下，就進攻时间达成共識。

两军问题是拜占庭将军问题的特例，常被编入与電腦网络相关的入门课程中。在传输控制协议（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），虽然问题并非初次发表，但文献依然獲广泛引用证明两军问题無解。