>

字数 2.4k 阅读 12 评论 6

两军问题是计算机领域的一个思想实验，用来阐述在一个不可靠的通信链路上试图通过通信以达成一致是存在缺陷的和困难的。这个问题和更有名的“拜占庭将军问题”有关（译者注：拜占庭将军问题很早就被提出，但是没有普及，后来为了普及，采用故事的方式来说明问题，并命名为拜占庭将军问题），并且经常出现在计算机网络课程的开头（特别是由于解释传输控制协议中的 TCP 协议并不能保证通信两端状态的一致性）。不过两军问题适用于任何有可能通信失败情况下的两点通信。在认知逻辑上一个重要概念是，两军问题强调了常识的重要性。也有些学者称之为“两军悖论”、“两军难题”、“协同攻击问题“等。两军问题是在计算机通信领域首个被证明无解的问题（译者注：据说量子通信可能会解决此问题），由此也可推论出，随机通信失败条件下的“拜占庭将军问题”也同样无解。

[定义]
两支军队，分别由两个将军领导，正在准备攻击一个坚固的城市。两支军队都驻扎在城市旁边的两个不同的山谷里。两军之间隔着第三个山谷，两个将军想要通讯的唯一方法就是穿过第三个山谷传送信件。问题是，第三个山谷被城市的守卫军占据，并且经此传送的信件可能会被守卫军截获（也就意味着信件无法到达对方）。
虽然两个将军商量好要同时对城市发起攻击，但是他们没有约定特定的攻击时间。为了保证取胜，他们必须同时发起攻击，否则任何单独发起攻击的军队都有可能全军覆没。他们必须互相通信来决定一个同时攻击时间，并且同意在那个时间发起攻击。两个将军彼此之间要知道另一个将军知道自己同意了作战计划。（译者注：A同意了作战计划，A将同意作战计划的信发给B，A将军要知道：B知道了A同意了作战计划。）因为返回来的信件和送出去的信件一样容易丢失，未来大量的消息必须保持一致性。
这个思想实验致力于考虑两军怎么做才能达成一致。在最简单的情况下，其中一个将军作为领导人，决定着发起攻击的时间，他必须将这个时间准确无误地通知另外一个将军。现在的问题是提出一种两个将军可以使用的算法。这个算法包含发送和接收处理消息，并正确地做出决定和推断：

没问题，我们会在约定的时间同时发起攻击

考虑到两个将军达成同时攻击的约定非常简单（例如，每一个成功发出去的信件，必须有一个成功的返回）。两军问题的微妙之处在于，对于上面的情形，不可能设计出一种能安全使用的算法。

军队位置图。A1和A2军队需要通信，但是他们的信息有可能被B军队拦截。

[问题描述]

A将军可以先发送一个消息：八月4日9点发起攻击。但是，一旦消息发送出去，A将军并不知道B是否收到了这个消息。这种不确定性使得A将军攻击之前非常犹豫，因为有独自发起攻击的危险。

为了让A将军放心，B将军可能要发送一个确认的返回信息给A将军：“我收到了你消息，我会在八月4日9点发起攻击”。可是，这个给A将军的确认消息也面临着被守卫军截获的可能，B将军也犹豫了，如果A将军没有收到确认信息，那么A将军很有可能停止此次攻击。

[证明]

带有特定消息数量的确定性协议。
http://coolshell.cn//wp-content/uploads/2012/03/0915533324-2.png
因为协议是确定性的的，假设有一个固定数量消息的队列，一些消息成功发送了，另一些失败了。假设两个将军有一个明确的攻击目标。

考虑最后一条消息成功送达。如果最后一条消息没有成功送达，至少有一个将军（很有可能是接收这条消息的将军）估计会不进行攻击。从最后一条消息发送者的角度出发，已发送的和已送达的消息队列顺序和预想的一致，并且包含所有已发送的消息。

因为协议是确定性的，最后一个发送消息的将军依然决定发起攻击。这样会形成如下情形：这个协议让一个将军发起攻击，另一个将军不发起攻击。这个情形与这个协议能解决两军问题的假设相矛盾。

不确定性和变长协议

一个带有变长消息的不确定性协议就像一个有限的森林，每个叶子或者分支（节点）代表一个被发现的相当于特定点的实例。

森林的根节点标记着第一条合适的消息。由根节点衍生出来的分支节点标记着合适的下一条消息。叶子节点代表发送了最后一条消息的实例。在发送任何消息之前，这个协议就是一棵空树。

假设有一个不确定性协议可以解决两军问题。那么，根据之前确定性协议的场景和分析，可以从一棵树去掉所有叶子节点，得到另外一棵树。也就是说，确定性协议一定也可以解决两军问题。

因为不确定性协议是有限的，由此可推断一棵代表空树的协议，也可以解决两军问题。很显然这是扯淡。所以不存在一个不确定性协议可以解决两军问题。

[工程方法]

一个解决两军问题实际可行的办法就是接受而非试图去消除通信信道的不可靠性，但是要将这种不可靠性降低到可以接受的程度。例如，A将军可以送出100个信使，并预期所有信使被抓的可能性是极低的。用了这种方法，A将军无论如何都会发起攻击，B将军只要收到一个信使的信，也会发起攻击。

一个类似的方法是，A将军发起一连串消息，B将军对每一个消息都返回一个应答消息。两个将军对每个返回的消息都感觉是充分的。

但是正如证明里看到的那样，无法确定攻击是协调一致的。没有一种可用的算法（比如收到4个消息）一定能防止只有一个将军发起攻击。

同样的，A将军可以给每一个发送的信息编号，从1到n。这种方法可以让B将军了解信道的可靠性，并且发送适当数量的返回信息来保证至少有一条信息会被收到。如果这个信道是可靠的，一条消息足够了，其他的消息都没什么用了。最后一条消息和第一条消息一样容易丢失。

假设每发送一个消息并被拦截时，将军将会牺牲一批士兵，那么我们可以设计这样一种算法，使得用最少的消息通信换取协同攻击的最大化确认。为了达到这个目的，发送方使用停止发送信息的方式表示已收到至少一次确认信息并承诺发起攻击。假设每个消息通过危险区需要1分钟，发送方收到确认信息后沉默200分钟，这样可以既不用牺牲更多的士兵又能达到高可靠的协同可信度。也就是说，只有当接收方没有收到攻击时间时发送方才会继续发送消息。发送方沉默200分钟后，接收方将得出以下结论：一种可能是连续200个消息都被敌方截获（显然概率极低）；另一种可能是对方已收到我的确认信息也相信我将发起攻击，对方也将发动攻击。

[历史]

两军问题及其无解性证明1975年被E. A. Akkoyunlu、K. Ekanadham和R. V. Huber首次提出。发表在《网络通信设计的约束与权衡》一文中。它在73页的开头用来描述两个匪徒团伙之间的通信。

1978年，Jim Gray在《数据库操作系统笔记》的465页，将这个问题命名为“两军问题”。这个引用被普遍地认为是最早的两军问题的定义和无解证明，但是正如上一段说的，其实他们早就被发表了。

参考
https://en.wikipedia.org/wiki/Two_Generals%27_Problem