Content deleted Content added
summarise problem in lead, move image to top |
|||
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. 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 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}}</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.▼
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.
▲
==Definition==
Two [[army|armies]], each led by a different [[general]], are preparing to attack a fortified city. The armies are encamped near the city, each in its own valley. A third valley separates the two hills, and the only way for the two generals to communicate is by sending [[Runner (war)|messenger]]s through the valley. Unfortunately, the valley is occupied by the city's defenders and there's a chance that any given messenger sent through the valley will be captured.
▲[[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.]]
While the two generals have agreed that they will attack, they haven't agreed upon a time for attack. It is required that the two generals have their armies attack the city at the same time in order to succeed, else the lone attacker army will die trying. They must thus communicate with each other to decide on a time to attack and to agree to attack at that time, and each general must know that the other general knows that they have agreed to the attack plan. Because [[Acknowledgement (data networks)|acknowledgement of message receipt]] can be lost as easily as the original message, a potentially infinite series of messages is required to come to [[Consensus (computer science)|consensus]].
| |||