Prolific holes

Two Generals’ Problem

Two 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 messengers 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.

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 be sure the other has agreed to the attack plan. Both generals will always be left wondering whether their last messenger got through.

Byzantine Generals Problem

When besieging a city, several Byzantine generals have a communication problem. It is necessary for the generals to attack the city with their troops simultaneously from different directions. The generals can communicate with each other via messengers. However, some of the generals plot against others. Their goal is to discredit their rivals — for example, by trying to drive the others to an early attack by cleverly scattering misinformation. None of the generals now knows what information is authentic and whom they can trust.

Thus, the problem is one of agreement, which is that the army commanders must unanimously decide whether or not to attack. The problem is complicated by the physical separation of the commanders; thus, they must send messengers back and forth. In addition, there is the possibility that there may be traitors among the generals, who may intentionally send misleading information to the other generals.

One solution considers scenarios in which messages may be forged, but which will be Byzantine-fault-tolerant as long as the number of disloyal generals is less than one third of the generals. The impossibility of dealing with one-third or more traitors ultimately reduces to proving that the one Commander and two Lieutenants problem cannot be solved, if the Commander is traitorous. To see this, suppose we have a traitorous Commander A, and two Lieutenants, B and C: when A tells B to attack and C to retreat, and B and C send messages to each other, forwarding A’s message, neither B nor C can figure out who is the traitor, since it is not necessarily A — another Lieutenant could have forged the message purportedly from A. It can be shown that if n is the number of generals in total, and t is the number of traitors in that n, then there are solutions to the problem only when n > 3t and the communication is synchronous (bounded delay).