两军问题：修订间差异
通过翻译页面“Two Generals' Problem”创建 |
|||
| 第1行： | 第1行： | ||
#REDIRECT [[拜占庭将军问题]] |
|||
[[File:2-generals.svg|右|缩略图|军队位置示意图：军队A1与A2通过派遣信使相互通信，但信使可能被军队B俘虏。]] |
|||
'''两军问题'''（英文：'''Two Generals' Problem'''）是计算机领域中的一个[[思想實驗|思想实验]]。两军问题显示，通过不可靠的通信通道交换信息并达成共识是难以实现的。 |
|||
在该问题中，两支军队的将军只能通过派遣信使穿越敌方领土来互相通信，以此约定在同一时间点协同进攻。该问题希望求解如何在两位将军派出的任何信使都可能被俘虏的情况下，就发动攻击的时间点达成一致。 |
|||
两军问题是[[拜占庭将军问题|拜占庭将军]]问题的一个特例，常被编入与[[计算机网络]]相关的入门课程中。在[[传输控制协议]]（TCP）相关的课程中，该问题可用作解释TCP协议无法保证通信双方之间的状态一致性的原因。该问题也适用于其他存在信息丢失的双方通信的情况。作为[[认识逻辑|认知逻辑]]的一个重要概念，该问题突出了共同知识的重要性。一些学者也将此问题称作“'''两军悖论'''”或“'''协同进攻问题'''”。<ref>{{cite journal|title=Decision-theoretic recursive modeling and the coordinated attack problem|url=http://dl.acm.org/citation.cfm?id=139492.139503|last=Gmytrasiewicz|first=Piotr J.|journal=Proceedings of the First International Conference on Artificial Intelligence Planning Systems|publisher=Morgan Kaufmann Publishers|accessdate=27 December 2013|doi=10.1016/B978-0-08-049944-4.50016-1|year=1992|location=San Francisco|pages=88–95|isbn=9780080499444|author2=Edmund H. Durfee}}</ref><ref>[http://www.dsi.uniroma1.it/~asd3/dispense/attack+amazons.pdf The coordinated attack and the jealous amazons] Alessandro Panconesi. Retrieved 2011-05-17.</ref>两军问题是第一个被证明无解的计算机通信问题。该证明的重要意义在于，其显示了对于存在通信错误的更广泛的问题（如[[拜占庭将军问题|拜占庭将军]]问题），同样是无解的。这也为所有的分布式一致性协议的实现提供了一个符合现实的预期。 |
|||
== 定义 == |
|||
两支由不同的[[將軍 (軍銜)|将军]]领导的[[陆军|军队]]，正准备进攻一座坚固的城市。军队在城市附近的位于两个山谷扎营。由于有另一个山谷将两个山丘隔开，两个将军交流的唯一方法是派遣信使穿越山谷。然而，这座山谷被城市的守卫者占领，并且有可能会俘虏途径该山谷传递信息的任意信使。 |
|||
尽管两位将军已经约定要同时发起进攻，但尚未约定进攻的具体时间点。要使攻击顺利，两支军队必须同时进攻城市。如果同一时间仅一组军队进攻，将会战败。因此，两位将军须通过沟通约定攻击时间，并且他们都必须确保另一位将军知道自己已同意了进攻计划。但由于传递[[確認訊息|确认讯息]]与原始消息的信使一样，都可能被俘虏造成消息丢失，即使双方不断确认已收到对方的上一条信息，也无法确保对方已与自己[[共識機制|达成共识]]。 |
|||
== 问题演示 == |
|||
将军A1首先让信使向将军A2传递消息“在8月4日9时整进攻”。然而，派遣信使后，将军A1不知道信使是否成功穿过敌方领土。由于担心自己成为唯一的进攻军队，将军A1可能会犹豫是否要按计划进攻。 |
|||
为了消除不确定性，将军A2可以向将军A1发送确认讯息：“我收到了您的消息，并将在8月4日9时整进攻”。但是，传递确认讯息的使者同样可能会被敌方俘虏。由于担心将军A1在没有收到确认讯息的情况下退缩，将军A2会犹豫是否要按计划进攻。 |
|||
再次发送确认讯息看上去可以解决问题——将军A1再让新信使发送确认讯息：“我已收到您对8月4日9时攻击计划的确认”。但是，将军A1的新信使也可能被俘虏。显然，无论进行多少轮确认，都无法满足该问题的第二个条件，即两位将军都必须确保对方已同意攻击计划。两位将军总是会怀疑他们派遣的最后一位使者是否顺利穿过敌方领土。 |
|||
== 证明 == |
|||
== 工程中的解决方案 == |
|||
== 历史 == |
|||
1975年，E. A. Akkoyunlu、K. Ekanadham 和 R. V. Huber 在《网络通信设计中的一些限制和取舍（Some Constraints and Trade-offs in the Design of Network Communications）》<ref>{{cite book|url=http://hydra.infosys.tuwien.ac.at/teaching/courses/AdvancedDistributedSystems/download/1975_Akkoyunlu,%20Ekanadham,%20Huber_Some%20constraints%20and%20tradeoffs%20in%20the%20design%20of%20network%20communications.pdf|doi=10.1145/800213.806523|title=Some constraints and trade-offs in the design of network communications|pages=67–74|publisher=Portal.acm.org|accessdate=2010-03-19|year=1975|last1=Akkoyunlu|first1=E. A.|last2=Ekanadham|first2=K.|last3=Huber|first3=R. V.|s2cid=788091}}</ref>一文中首次提到了两军问题（尽管使用了两组黑帮表示通信双方），并将该问题证明为无解。 |
|||
1978年，[[詹姆斯·尼古拉·格雷]]<ref>{{Cite web|title=Jim Gray Summary Home Page|url=http://research.microsoft.com/~Gray/JimGrayHomePageSummary.htm|accessdate=2010-03-19|date=2004-05-03|publisher=Research.microsoft.com}}</ref>在《关于数据库操作系统的记事（Notes on Data Base Operating Systems）》 <ref>{{Cite web|title=Notes on Data Base Operating Systems|url=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=723863|accessdate=2010-03-19|publisher=Portal.acm.org}}</ref>一文中将该问题命名为“两军悖论”（Two Generals Paradox）。虽然这并非该问题的初次发表，但该文献被广泛用作双军问题及其不可能性证明的参考文献。 |
|||
== 参考文献 == |
|||
[[Category:思想實驗]] |
|||
[[Category:計算理論]] |
|||
2021年1月23日 (六) 22:06的版本
两军问题（英文：Two Generals' Problem）是计算机领域中的一个思想实验。两军问题显示，通过不可靠的通信通道交换信息并达成共识是难以实现的。
在该问题中，两支军队的将军只能通过派遣信使穿越敌方领土来互相通信，以此约定在同一时间点协同进攻。该问题希望求解如何在两位将军派出的任何信使都可能被俘虏的情况下，就发动攻击的时间点达成一致。
两军问题是拜占庭将军问题的一个特例，常被编入与计算机网络相关的入门课程中。在传输控制协议（TCP）相关的课程中，该问题可用作解释TCP协议无法保证通信双方之间的状态一致性的原因。该问题也适用于其他存在信息丢失的双方通信的情况。作为认知逻辑的一个重要概念，该问题突出了共同知识的重要性。一些学者也将此问题称作“两军悖论”或“协同进攻问题”。[1][2]两军问题是第一个被证明无解的计算机通信问题。该证明的重要意义在于，其显示了对于存在通信错误的更广泛的问题（如拜占庭将军问题），同样是无解的。这也为所有的分布式一致性协议的实现提供了一个符合现实的预期。
定义
两支由不同的将军领导的军队，正准备进攻一座坚固的城市。军队在城市附近的位于两个山谷扎营。由于有另一个山谷将两个山丘隔开，两个将军交流的唯一方法是派遣信使穿越山谷。然而，这座山谷被城市的守卫者占领，并且有可能会俘虏途径该山谷传递信息的任意信使。
尽管两位将军已经约定要同时发起进攻，但尚未约定进攻的具体时间点。要使攻击顺利，两支军队必须同时进攻城市。如果同一时间仅一组军队进攻，将会战败。因此，两位将军须通过沟通约定攻击时间，并且他们都必须确保另一位将军知道自己已同意了进攻计划。但由于传递确认讯息与原始消息的信使一样，都可能被俘虏造成消息丢失，即使双方不断确认已收到对方的上一条信息，也无法确保对方已与自己达成共识。
问题演示
将军A1首先让信使向将军A2传递消息“在8月4日9时整进攻”。然而，派遣信使后，将军A1不知道信使是否成功穿过敌方领土。由于担心自己成为唯一的进攻军队，将军A1可能会犹豫是否要按计划进攻。
为了消除不确定性，将军A2可以向将军A1发送确认讯息：“我收到了您的消息，并将在8月4日9时整进攻”。但是，传递确认讯息的使者同样可能会被敌方俘虏。由于担心将军A1在没有收到确认讯息的情况下退缩，将军A2会犹豫是否要按计划进攻。
再次发送确认讯息看上去可以解决问题——将军A1再让新信使发送确认讯息：“我已收到您对8月4日9时攻击计划的确认”。但是，将军A1的新信使也可能被俘虏。显然，无论进行多少轮确认，都无法满足该问题的第二个条件，即两位将军都必须确保对方已同意攻击计划。两位将军总是会怀疑他们派遣的最后一位使者是否顺利穿过敌方领土。
证明
工程中的解决方案
历史
1975年，E. A. Akkoyunlu、K. Ekanadham 和 R. V. Huber 在《网络通信设计中的一些限制和取舍（Some Constraints and Trade-offs in the Design of Network Communications）》[3]一文中首次提到了两军问题（尽管使用了两组黑帮表示通信双方），并将该问题证明为无解。
1978年，詹姆斯·尼古拉·格雷[4]在《关于数据库操作系统的记事（Notes on Data Base Operating Systems）》 [5]一文中将该问题命名为“两军悖论”（Two Generals Paradox）。虽然这并非该问题的初次发表，但该文献被广泛用作双军问题及其不可能性证明的参考文献。
参考文献
- ^ Gmytrasiewicz, Piotr J.; Edmund H. Durfee. Decision-theoretic recursive modeling and the coordinated attack problem. Proceedings of the First International Conference on Artificial Intelligence Planning Systems (San Francisco: Morgan Kaufmann Publishers). 1992: 88–95 [27 December 2013]. ISBN 9780080499444. doi:10.1016/B978-0-08-049944-4.50016-1.
- ^ The coordinated attack and the jealous amazons Alessandro Panconesi. Retrieved 2011-05-17.
- ^ Akkoyunlu, E. A.; Ekanadham, K.; Huber, R. V. Some constraints and trade-offs in the design of network communications (PDF). Portal.acm.org. 1975: 67–74 [2010-03-19]. S2CID 788091. doi:10.1145/800213.806523.
- ^ Jim Gray Summary Home Page. Research.microsoft.com. 2004-05-03 [2010-03-19].
- ^ Notes on Data Base Operating Systems. Portal.acm.org. [2010-03-19].