两军问题

军队位置示意图：军队甲（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），虽然问题并非初次发表，但文献依然获广泛引用证明两军问题无解。