Two Generals' Problem

In computing, the Two Generals' Problem is a thought experiment meant to illustrate the pitfalls and design challenges of communicating over an unreliable link. It is a simplification of the more general Byzantine Generals' Problem and appears often in introductory classes about computer networking (particularly with regards to the Transport Control Protocol), although it can also apply to other types of communication.

Definition

Two armies, each led by a general, are preparing to attack a city. The armies are encamped outside of the city, each on its own hill. A valley separates the two hills, and the only way for the two generals to communicate is by sending messengers through the valley. Unfortunately, the valley is occupied by the city's defenders, and there is a chance that any given messenger sent through the valley will be captured. Note that the two generals have never met beforehand to arrange a schedule or anything of the sort; each general has no idea when and if the other will send a messenger, nor do they know (immediately) whether a messenger they have sent was captured or not, or how long it will take for any individual messenger to reach the other side.

The two generals must attack the city at the same time to succeed. They must thus communicate with each other to decide on a time to attack. The thought experiment involves considering how they might go about doing this.

Provable Uncertainty

The first general may start by sending a message "Let us attack at 9 o'clock in the morning." However, once dispatched, the first general has no idea whether or not the messenger got through. Any amount of uncertainty may lead the first general to hesitate to attack, since if the second general does not also attack at that time, the city will repel the advance. Knowing this, the second general may send a confirmation back to the first: "I received your message and will attack at 9 o'clock." However, what if the confirmation messenger were captured? The second general, knowing that the first will hesitate without the confirmation, may himself hesitate. A solution would be to have the first general send a second confirmation: "I received your confirmation of the planned attack." However, what if that messenger were captured? It quickly becomes evident that no matter how many rounds of confirmation are made, neither general can be absolutely sure of the other's plans.

Engineering Solutions

The "solution" to the two generals' problem is to use schemes that acknowledge the uncertainty of the communications link and do not attempt to eliminate it, but rather to mediate it to an acceptable degree. For example, the generals could send 100 messengers each time, knowing that the probability of all being captured is low; or they could continue sending messengers until a confirmation is received, using sequence numbers to keep track of each message.