Two Generals' Problem: Difference between revisions

Revision as of 05:25, 16 February 2024

Latest revision as of 18:48, 26 August 2025

(7 intermediate revisions by 6 users not shown)

Line 4:

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.

The Two Generals' Problem appears often as an introduction to the more general [[Byzantine Generals]] problem in introductory classes about [[computer networking]] (particularly with regard to the [[Transmission Control Protocol]], where it shows that TCP can'tcannot 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 journalbook|last=Gmytrasiewicz|first=Piotr J.|author2=Edmund H. Durfee |titlechapter=Decision-theoreticTheoretic recursiveRecursive modelingModeling and the coordinatedCoordinated attackAttack problemProblem |title=Artificial Intelligence Planning Systems|journal=Proceedings of the First International Conference on Artificial Intelligence Planning Systems|year=1992|pages=88–95|chapter-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 provedproven to be unsolvable.<ref>

Leslie Lamport.

[https://lamport.azurewebsites.net/pubs/solved-and-unsolved.pdf "Solved Problems, Unsolved Problems and Non-Problems in Concurrency"].

Line 12:

==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 is a chance that any given messenger sent through the valley will be captured.<ref>{{Cite web |last=Ruby |first=Matt |title=How the Byzantine General’sGeneral's Problem Relates to You in 2024 |url=https://www.swanbitcoin.com/byzantine-generals-problem/ |access-date=2024-02-16 |website=Swan Bitcoin |language=en}}</ref>

While the two generals have agreed that they will attack, they haven't agreed upon a time for an attack. It is required that the two generals have their armies attack the city simultaneously to succeed, lest the lone attacker army 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]].<ref>{{Cite web |title=The Byzantine Generals Problem (Consensus in the presence of uncertainties) |url=https://www.doc.ic.ac.uk/~jnm/DistrAlg/Notes/Byzantine-4up-final.pdf |url-status=live |access-date=16 February 2024 |website=[[Imperial College London]]}}</ref>

The thought experiment involves considering how they might go about coming to a consensus. In its simplest form, one general is known to be the leader, decides on the time of the attack, and must communicate this time to the other general. The problem is to come up with algorithms that the generals can use, including sending messages and processing received messages, that can allow them to correctly conclude:

:{{block indent|Yes, we will both attack at the agreed-upon time.}}

Allowing that it is quite simple for the generals to come to an agreement on the time to attack (i.e. one successful message with a successful acknowledgement), the subtlety of the Two Generals' Problem is in the impossibility of designing algorithms for the generals to use to safely agree to the above statement.<ref>{{Cite web |last=Shrestha |first=Ajay cn|date=2024-01-15June |title=Bitcoin’s technical contribution: Solving Byzantine General’s Problem |url=https://towardsdatascience.com/bitcoins-technical-contribution-solving-byzantine-general-s-problem-f0449973437c |access-date=2024-02-16 |website=Medium |language=en}}</ref>

==Illustrating the problem==

The first general may start by sending a message: "Attack at 0900 on August 4." However, once dispatched, the first general has no idea whether or not the messenger got through. This uncertainty may lead the first general to hesitate to attack due to the risk of being the sole attacker.

To be sure, the second general may send a confirmation back to the first: "I received your message and will attack at 0900 on August 4." However, the messenger carrying the confirmation could face capture, and the second general may hesitate, knowing that the first might hold back without the confirmation.

Further confirmations may seem like a solution—let the first general send a second confirmation: "I received your confirmation of the planned attack at 0900 on August 4." However, this new messenger from the first general is liable to be captured, too. Thus, it quickly becomes evident that no matter how many rounds of confirmation are made, there is no way to guarantee the second requirement that each general is sure the other has agreed to the attack plan. Both generals will always be left wondering whether their last messenger got through.<ref>{{Cite web |lastlast1=Lamport |firstfirst1=Leslie |last2=Shostak |first2=Robert |last3=Pease |first3=Marshall |title=The Byzantine Generals Problem |url=https://lamport.azurewebsites.net/pubs/byz.pdf |url-status=live |access-date=16 February 2024 |website=[[SRI International]]}}</ref>

== Proof ==

Line 57:

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 book|author=R. Bayer, R. M. Graham, and G. Seegmüller|year=1978|title=Operating Systems|pages=393–481|publisher=Springer-Verlag|isbn=0-387-09812-7}}

Online version: {{cite book|url=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=723863 |title=Notes on Data Base Operating Systems |date=January 1978 |pages=393–481 |publisher=Portal.acm.org |isbn=978-3-540-08755-7 |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 mentioned above.

==References==