两军问题：修订间差异

删除的内容添加的内容

行内

2022年8月23日 (二) 12:59的最新版本

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

两军问题（英語：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），虽然问题并非初次发表，但文献依然獲广泛引用证明两军问题無解。

参考文献

^ 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）.
^ 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]. doi:10.1145/800213.806523. （原始内容 (PDF)存档于2020-11-28）.
^ Jim Gray Summary Home Page. Research.microsoft.com. 2004-05-03 [2010-03-19]. （原始内容存档于2008-11-13）.
^ Notes on Data Base Operating Systems. Portal.acm.org. [2010-03-19]. （原始内容存档于2007-03-10）.

[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）.

[1]

[2]

[3]

[4]

[5]

@@ 第3行： / 第3行： @@
 }}
 {{request translation}}
-[[File:2-generals.svg|右|缩略图|军队位置示意图：军队A1与A2通过派遣信使相互通信，但信使可能被军队B俘虏。]]
+[[File:2-generals.svg|右|缩略图|军队位置示意图：军队甲（A1）与乙（A2）派遣信使互相通訊，但信使可能被敵军（Ｂ）俘虏。]]
-'''两军问题'''（{{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协议无法保证通信双方之间的状态一致性的原因。该问题也适用于其他存在信息丢失的双方通信的情况。作为[[认识逻辑]]的一个重要概念，该问题突出了共同知识的重要性。一些学者也将此问题称作两军悖论（{{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}}</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可能会犹豫是否要按计划进攻。
+将军甲首先派信使向将军乙传递訊息“在8月4日9时进攻”。然而，派遣信使后，将军甲不知道信使是否成功穿过敌方领土。由于担心自己成为唯一的进攻军队，将军甲可能会犹豫要否按计划进攻。
-为了消除不确定性，将军A2可以向将军A1发送确认消息：“我收到了您的消息，并将在8月4日9时整进攻”。但是，传递确认消息的使者同样可能会被敌方俘虏。由于担心将军A1在没有收到确认消息的情况下退缩，将军A2会犹豫是否要按计划进攻。
+为了消除不确定性，将军乙可以向将军甲发送确认訊息“我收到了您的訊息，并會在8月4日9时进攻”，但传递确认訊息的使者同样可能会被敌方俘虏。由于担心将军甲没有收到确认訊息而退缩，将军乙会犹豫要否按计划进攻。
-再次发送确认消息看上去可以解决问题——将军A1再让新信使发送确认消息：“我已收到您对8月4日9时攻击计划的确认”。但是，将军A1的新信使也可能被俘虏。显然，无论进行多少轮确认，都无法满足该问题的第二个条件，即两位将军都必须确保对方已同意攻击计划。两位将军总是会怀疑他们派遣的最后一位使者是否顺利穿过敌方领土。
+再次发送确认訊息看來可以解决问题——将军甲再让新信使发送确认訊息：“我已收到您确认在8月4日9时进攻”。但是，将军甲的新信使也可能被俘虏。显然，无论确认幾次都无法满足该问题的条件二，即两方都必须确保对方已同意计划，两名将军总会怀疑他们最后派遣的使者有否顺利穿过敌方领土。
 == 证明 ==
@@ 第27行： / 第25行： @@
 == 历史 ==
-年，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>一文中首次提到了两军问题（尽管使用了两组黑帮表示通信双方），并将该问题证明为无解。
+年，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.|archive-date=2020-11-28|archive-url=https://web.archive.org/web/20201128104320/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}}</ref>一文首次提到两军问题（但以两组黑帮表示通訊双方），并证明问题无解。
-年，[[詹姆斯·尼古拉·格雷]]<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）。虽然这并非该问题的初次发表，但该文献被广泛用作双军问题及其不可能性证明的参考文献。
+年，[[詹姆斯·尼古拉·格雷]]<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|archive-date=2008-11-13|archive-url=https://web.archive.org/web/20081113011249/http://research.microsoft.com/~gray/JimGrayHomePageSummary.htm}}</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|archive-date=2007-03-10|archive-url=https://web.archive.org/web/20070310153414/http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=723863|dead-url=no}}</ref>一文将问题命名为“两军悖论”（Two Generals Paradox），虽然问题并非初次发表，但文献依然獲广泛引用证明两军问题無解。
 == 参考文献 ==