Beyond Zero and One (Andrew Smart) / quote 68 of 171
Four generals for Byzantine fault tolerance
divisions surround an enemy camp. After observing the enemy, the generals must communicate among themselves and come to consensus on a plan of action. They must decide whether to attack or retreat. If they all agree to attack, they win. If they all agree not to attack, they live to fight another day. If, however, some attack and some do not, then the generals and their divisions will be wiped out. The Byzantine generals communicate either via oral statements or signed written messages. The problem is that some of the generals are traitors. These generals try to disrupt the loyal generals’ attempts to achieve consensus about a plan of action by sending inconsistent messages. For oral messages between generals, Lamport assumes that: A1. Every message that is sent is delivered correctly. No messages are lost. A2. The receiver of a message knows who sent it. A3. The absence of a message can be detected. Lamport and others have shown that consensus cannot be achieved with only three generals when one of the generals turns out to be a traitor. The minimum number of generals needed to reach consensus in this situation is four. If these assumptions were true in the equivalent computer system, for example, we can say simplistically that this would translate to having four redundant processors in an airplane to achieve what is called Byzantine fault tolerance.