Byzantine fault tolerance
From Freepedia
The Byzantine Generals problem and several solutions were originally described by Lamport, Shostak, and Pease in ACM Transaction on Progamming Languages and Systems in 1982 (see References).
The Byzantine Generals problem describes a group of generals, each commanding a division of the Byzantine army, encircling a city. These generals wish to formulate a plan for attacking the city. In its simplest form, the generals must only decide whether to attack or retreat. Some generals may prefer to attack, while others prefer to retreat. The important thing is that every general agrees on a common decision, for a halfhearted attack by a few generals would be worse than a coordinated attack or a coordinated retreat.
The problem is made difficult by the presence of traitorous generals who may not only cast a vote for a suboptimal strategy, they may do so selectively. For instance, if nine generals are voting, four of whom support attacking while four others are in favor of retreat, the ninth general may give a vote of retreat to a few generals and a vote of attack to the rest. Those who received a retreat vote from the ninth general will retreat, while the rest will attack (which may not go well for the attackers).
Byzantine fault tolerance can be achieved if the loyal generals have a strategy to compare notes with each other such that conflicting information is disregarded.
More generally, a Byzantine fault is one in which a component of some system not only behaves erroneously, but also fails to behave consistently when interacting with multiple other components. Correctly functioning components of a Byzantine fault tolerant system will be able to reach the same group decisions regardless of Byzantine faulty components.
Solutions
Lamport, Shostak, and Pease propose several solutions. They begin by noting that the Generals Problem can be reduced to solving a Commander and Lieutenants problem where Loyal Lieutenants must all act in unison and that their action must correspond to what the Commander ordered in the case that the Commander is Loyal. Roughly speaking, the Generals vote by treating each others' orders as votes.
One allows scenarios in which messages may be forged, and is Byzantine Fault Tolerant as long as the number of traitorous generals does not equal or exceed one third. The impossibility of dealing with one-third or more traitors ultimately reduces to proving that the 1 Commander + 2 Lieutenants problem cannot be solved if the Commander is traitorous.
A second solution requires unforgeable signatures (in modern computer systems, this may be achieved through public key cryptography), but maintains Byzantine Fault Tolerance in the presence of an arbitrary number of traitorous generals.
Also presented is a variation on the first two solutions allowing Byzantine Fault Tolerant behavior in some situations where not all generals can communicate directly with each other.
See also
References
- Byzantine Fault Tolerance paper (PDF) by Lamport, Shostak, and Pease: ACM Transaction on Progamming Languages and Systems, 1982.
