跳转到内容

两军问题:修订间差异

维基百科,自由的百科全书
删除的内容 添加的内容
InternetArchiveBot留言 | 贡献
补救2个来源,并将0个来源标记为失效。) #IABot (v2.0.8.7
修飾語句
第3行: 第3行:
}}
}}
{{request translation}}
{{request translation}}
[[File:2-generals.svg|右|缩略图|军队位置示意图:军队A1A2通过派遣信使相通信,但信使可能被军队B俘虏。]]
[[File:2-generals.svg|右|缩略图|军队位置示意图:军队甲(A1)乙(A2)派遣信使相通信,但信使可能被军队丙(B)俘虏。]]
'''两军问题'''({{lang-en|Two Generals' Problem}})是计算机领域一个[[思想實驗]]。两军问题显示,通过不可靠的通信通道交换信息并达成共识是难以实现的。在该问题中,两支军队的将军只能通过派遣信使穿越敌方领土来互相通信,以此约定在同一时间点共同进攻。该问题希望求解如何在两将军派出的任何信使都可能被俘虏的情况下,就发动攻击的时间点达成一致。
'''两军问题'''({{lang-en|Two Generals' Problem}})是计算机领域的[[思想實驗]]。两军问题显示,通过不可靠的通信通道交换信息并达成共识是难以实现的。在该问题中,两支军队的将军只能通过派遣信使穿越敌方领土来互相通信,以此约定在同一时间点共同进攻。该问题希望求解如何在两将军派出的任何信使都可能被俘虏的情况下,就发动攻击的时间点达成一致。


两军问题是[[拜占庭将军问题]]的一个特例,常被编入与[[计算机网络]]相关的入门课程中。在[[传输控制协议]](TCP)相关的课程中,该问题可用作解释TCP协议无法保证通信双方之间的状态一致性的原因。该问题也适用于其他存在信息丢失的双方通信的情况。作为[[认识逻辑]]的一个重要概念,该问题突出了{{link-en|共识|Common_knowledge_(logic)}}的重要性。一些学者也将此问题称作两军悖论({{lang-en|Two Generals Paradox}})或协同进攻问题({{lang-en|Coordinated Attack Problem}})。<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|archive-date=2019-12-15|archive-url=https://web.archive.org/web/20191215220012/https://dl.acm.org/citation.cfm?id=139492.139503|dead-url=no}}</ref><ref>[http://www.dsi.uniroma1.it/~asd3/dispense/attack+amazons.pdf The coordinated attack and the jealous amazons] {{Wayback|url=http://www.dsi.uniroma1.it/~asd3/dispense/attack+amazons.pdf |date=20120206033141 }} Alessandro Panconesi. Retrieved 2011-05-17.</ref>两军问题是第一个被证明无解的计算机通信问题。该证明的重要意义在于,其显示了对于存在通信错误的更广泛的问题(如[[拜占庭将军问题]]),同样是无解的。这也为所有分布式一致性协议的实现提供了一个符合现实的预期。
两军问题是[[拜占庭将军问题]]的一个特例,常被编入与[[计算机网络]]相关的入门课程中。在[[传输控制协议]](TCP)相关的课程中,该问题可用作解释TCP协议无法保证通信双方之间的状态一致性的原因。该问题也适用于其他存在信息丢失的双方通信的情况。作为[[认识逻辑]]的一个重要概念,该问题突出了{{link-en|共识|Common_knowledge_(logic)}}的重要性。一些学者也将此问题称作两军悖论({{lang-en|Two Generals Paradox}})或协同进攻问题({{lang-en|Coordinated Attack Problem}})。<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|archive-date=2019-12-15|archive-url=https://web.archive.org/web/20191215220012/https://dl.acm.org/citation.cfm?id=139492.139503|dead-url=no}}</ref><ref>[http://www.dsi.uniroma1.it/~asd3/dispense/attack+amazons.pdf The coordinated attack and the jealous amazons] {{Wayback|url=http://www.dsi.uniroma1.it/~asd3/dispense/attack+amazons.pdf |date=20120206033141 }} Alessandro Panconesi. Retrieved 2011-05-17.</ref>两军问题是第一个被证明无解的计算机通信问题。该证明的重要意义在于,其显示了对于存在通信错误的更广泛的问题(如[[拜占庭将军问题]]),同样是无解的。这也为所有分布式一致性协议的实现提供了一个符合现实的预期。
第11行: 第11行:
两支由不同的[[將軍 (軍銜)|将军]]领导的[[陆军|军队]],正准备进攻一座坚固的城市。军队在城市附近的两个山谷扎营。由于有另一个山谷将两个山丘隔开,两个将军交流的唯一方法是派遣信使穿越山谷。然而,这座山谷被城市的守卫者占领,并且有可能会俘虏途径该山谷传递信息的任意信使。
两支由不同的[[將軍 (軍銜)|将军]]领导的[[陆军|军队]],正准备进攻一座坚固的城市。军队在城市附近的两个山谷扎营。由于有另一个山谷将两个山丘隔开,两个将军交流的唯一方法是派遣信使穿越山谷。然而,这座山谷被城市的守卫者占领,并且有可能会俘虏途径该山谷传递信息的任意信使。


尽管两将军已经约定要同时发起进攻,但尚未约定进攻的具体时间。要使攻击顺利,两支军队必须同时进攻城市。如果同一时间仅一组军队进攻,将会战败。因此,两将军须通过沟通约定攻击时间,并且他们都必须确保另一将军知道自己已同意了进攻计划。但由于传递[[確認訊息]]的信使与传递原始消息的信使一样,都可能被俘虏造成消息丢失,即使双方不断确认已收到对方的上一条信息,也无法确保对方已与自己[[共識機制|达成共识]]。
尽管两将军已经约定要同时发起进攻,但尚未约定进攻的具体时间。要顺利攻击,两支军队必须同时进攻城市。如果同一时间仅一组军队进攻,将会战败。因此,两将军须通过沟通约定攻击时间,并且他们都必须确保另一将军知道自己已同意了进攻计划。但由于传递[[確認訊息]]的信使与传递原始消息的信使一样,都可能被俘虏造成消息丢失,即使双方不断确认已收到对方的上一条信息,也无法确保对方已与自己[[共識機制|达成共识]]。


== 问题演示 ==
== 问题演示 ==
将军A1首先让信使向将军A2传递消息“在8月4日9时进攻”。然而,派遣信使后,将军A1不知道信使是否成功穿过敌方领土。由于担心自己成为唯一的进攻军队,将军A1可能会犹豫是否要按计划进攻。
将军首先让信使向将军传递消息“在8月4日9时进攻”。然而,派遣信使后,将军不知道信使是否成功穿过敌方领土。由于担心自己成为唯一的进攻军队,将军可能会犹豫是否要按计划进攻。


为了消除不确定性,将军A2可以向将军A1发送确认消息:“我收到了您的消息,并将在8月4日9时进攻”。但是,传递确认消息的使者同样可能会被敌方俘虏。由于担心将军A1在没有收到确认消息的情况下退缩,将军A2会犹豫是否要按计划进攻。
为了消除不确定性,将军可以向将军发送确认消息:“我收到了您的消息,并将在8月4日9时进攻”。但是,传递确认消息的使者同样可能会被敌方俘虏。由于担心将军在没有收到确认消息的情况下退缩,将军会犹豫是否要按计划进攻。


再次发送确认消息看上去可以解决问题——将军A1再让新信使发送确认消息:“我已收到您对8月4日9时攻击计划的确认”。但是,将军A1的新信使也可能被俘虏。显然,无论进行多少轮确认,都无法满足该问题的第二个条件,即两将军都必须确保对方已同意进攻计划。两将军总是会怀疑他们派遣的最后一使者是否顺利穿过敌方领土。
再次发送确认消息看上去可以解决问题——将军再让新信使发送确认消息:“我已收到您对8月4日9时攻击计划的确认”。但是,将军的新信使也可能被俘虏。显然,无论确认多少都无法满足该问题的第二个条件,即两将军都必须确保对方已同意进攻计划。两将军总是会怀疑他们派遣的最后一使者是否顺利穿过敌方领土。


== 证明 ==
== 证明 ==

2022年8月23日 (二) 11:48的版本

军队位置示意图:军队甲(A1)与乙(A2)派遣信使互相通信,但信使可能被军队丙(B)俘虏。

两军问题(英語:Two Generals' Problem)是计算机领域的思想實驗。两军问题显示,通过不可靠的通信通道交换信息并达成共识是难以实现的。在该问题中,两支军队的将军只能通过派遣信使穿越敌方领土来互相通信,以此约定在同一时间点共同进攻。该问题希望求解如何在两名将军派出的任何信使都可能被俘虏的情况下,就发动攻击的时间点达成一致。

两军问题是拜占庭将军问题的一个特例,常被编入与计算机网络相关的入门课程中。在传输控制协议(TCP)相关的课程中,该问题可用作解释TCP协议无法保证通信双方之间的状态一致性的原因。该问题也适用于其他存在信息丢失的双方通信的情况。作为认识逻辑的一个重要概念,该问题突出了共识英语Common_knowledge_(logic)的重要性。一些学者也将此问题称作两军悖论(英語:Two Generals Paradox)或协同进攻问题(英語:Coordinated Attack Problem)。[1][2]两军问题是第一个被证明无解的计算机通信问题。该证明的重要意义在于,其显示了对于存在通信错误的更广泛的问题(如拜占庭将军问题),同样是无解的。这也为所有分布式一致性协议的实现提供了一个符合现实的预期。

定义

两支由不同的将军领导的军队,正准备进攻一座坚固的城市。军队在城市附近的两个山谷扎营。由于有另一个山谷将两个山丘隔开,两个将军交流的唯一方法是派遣信使穿越山谷。然而,这座山谷被城市的守卫者占领,并且有可能会俘虏途径该山谷传递信息的任意信使。

尽管两名将军已经约定要同时发起进攻,但尚未约定进攻的具体时间。要顺利攻击,两支军队必须同时进攻城市。如果同一时间仅一组军队进攻,将会战败。因此,两名将军须通过沟通约定攻击时间,并且他们都必须确保另一名将军知道自己已同意了进攻计划。但由于传递確認訊息的信使与传递原始消息的信使一样,都可能被俘虏造成消息丢失,即使双方不断确认已收到对方的上一条信息,也无法确保对方已与自己达成共识

问题演示

将军甲首先让信使向将军乙传递消息“在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)》[3]一文中首次提到了两军问题(尽管使用了两组黑帮表示通信双方),并证明该问题无解。

1978年,詹姆斯·尼古拉·格雷[4]在《关于数据库操作系统的记事(Notes on Data Base Operating Systems)》 [5]一文中将该问题命名为“两军悖论”(Two Generals Paradox)。虽然这并非该问题的初次发表,但该文献被广泛用作两军问题及其不可能性证明的参考文献。

参考文献

  1. ^ 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. (原始内容存档于2019-12-15). 
  2. ^ The coordinated attack and the jealous amazons页面存档备份,存于互联网档案馆) Alessandro Panconesi. Retrieved 2011-05-17.
  3. ^ 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]. doi:10.1145/800213.806523. (原始内容 (PDF)存档于2020-11-28). 
  4. ^ Jim Gray Summary Home Page. Research.microsoft.com. 2004-05-03 [2010-03-19]. (原始内容存档于2008-11-13). 
  5. ^ Notes on Data Base Operating Systems. Portal.acm.org. [2010-03-19]. (原始内容存档于2007-03-10).