Content deleted Content added
m Serial Number 54129 moved page Two General's Problem to Two Generals' Problem over a redirect without leaving a redirect: It is a possessive plural: The *problem* belongs to *two generals* and so the *s* is apostrophised. This is also the lonf standing title; it should not be moved without consensus which, while you have opened a TP discussion, you have edit-warred through. |
grammar |
||
Line 1:
[[File:2-generals.svg|right|thumb|Positions of the armies. Armies A1 and A2 need to communicate but their messengers may be captured by army B.]]
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 this is the case), 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 First International Conference on Artificial Intelligence Planning Systems|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 book|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 |pages=67–74
|publisher=Portal.acm.org |accessdate=2010-03-19|chapter=Some constraints and tradeoffs in the design of network communications
| |||