Two Generals' Problem: Difference between revisions

Revision as of 19:06, 21 November 2024

Latest revision as of 18:48, 26 August 2025

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'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 |access-date=16 February 2024 |website=[[Imperial College London]]}}</ref>

Line 18:

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.{{cn|date=June 2024}}