Two Generals' Problem: Difference between revisions

Revision as of 17:56, 5 March 2019

Revision as of 09:11, 16 March 2019

Line 3:

In computing, the '''Two Generals Problem''' is a [[thought experiment]] meant to illustrate the pitfalls and design challenges of attempting to coordinate an action by communicating over an unreliable link. In the experiment, two generals are only able to communicate with one another by sending a messenger through enemy territory. The experiment asks how they might reach an agreement on the time to launch an attack, while knowing that any messenger they send could be captured.

It is related to the more general [[Byzantine Generals]] Problem and appears often in introductory classes about [[computer networking]] (particularly with regard to the [[Transmission Control Protocol]], where it shows that TCP can't guarantee state consistency between endpoints and why), though it applies to any type of two-party communication where failures of communication are possible. A key concept in [[epistemic logic]], this problem highlights the importance of [[common knowledge (logic)|common knowledge]]. Some authors also refer to this as the '''Two Generals Paradox''', the '''Two Armies Problem''', or the '''Coordinated Attack Problem'''.<ref>{{cite journal|last=Gmytrasiewicz|first=Piotr J.|author2=Edmund H. Durfee |title=Decision-theoretic recursive modeling and the coordinated attack problem|journal=Proceedings of the firstFirst internationalInternational conferenceConference on Artificial intelligenceIntelligence planningPlanning systemsSystems|year=1992|pages=88–95|url=http://dl.acm.org/citation.cfm?id=139492.139503|accessdate=27 December 2013|publisher=Morgan Kaufmann Publishers|___location=San Francisco|doi=10.1016/B978-0-08-049944-4.50016-1|isbn=9780080499444}}</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> The Two Generals Problem was the first computer communication problem to be proved to be unsolvable. An important consequence of this proof is that generalizations like the Byzantine Generals problem are also unsolvable in the face of arbitrary communication failures, thus providing a base of realistic expectations for any distributed consistency protocols.

==Definition==

Line 54:

==History==

The Two Generals Problem and its impossibility proof was first published by E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber in 1975 in "Some Constraints and Trade-offs in the Design of Network Communications",<ref>{{cite webbook|chapter-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 |publisherpages=Portal.acm.org67–74 |accessdate=2010-03-19}}</ref> where it is described starting on page 73 in the context of communication between two groups of gangsters.

|publisher=Portal.acm.org |accessdate=2010-03-19|chapter=Some constraints and tradeoffs in the design of network communications

|year=1975

|last1=Akkoyunlu

|first1=E. A.

|last2=Ekanadham

|first2=K.

|last3=Huber

|first3=R. V.

}}</ref> where it is described starting on page 73 in the context of communication between two groups of gangsters.

This problem was given the name the ''Two Generals Paradox'' by [[Jim Gray (computer scientist)|Jim Gray]]<ref>{{cite web|url=http://research.microsoft.com/~Gray/JimGrayHomePageSummary.htm |title=Jim Gray Summary Home Page |publisher=Research.microsoft.com |date=2004-05-03 |accessdate=2010-03-19}}</ref> in 1978 in "Notes on Data Base Operating Systems"<ref>{{cite web|url=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=723863 |title=Notes on Data Base Operating Systems |publisher=Portal.acm.org |accessdate=2010-03-19}}</ref> starting on page 465. This reference is widely given as a source for the definition of the problem and the impossibility proof, though both were published previously as above.