Contents

1 Byzantine Fault Tolerance 2 Solutions 3 See Also 4 External Links

Byzantine Fault Tolerance

The Byzantine Generals problem and several solutions were originally described by Lamport, Shostak, and Pease (http://www.cs.wisc.edu/~bart/739/papers/byzantine.pdf) in ACM Transaction on Progamming Languages and Systems in 1982.

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 give out false information, they may do so selectively. For instance, if nine generals are voting what to do, 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 compare notes with each other and disregard conficting information.

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 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. One allows messages to be forged, and is Byzantine Fault Tolerant as long as the number of traitorous generals does not exceed roughly one third.

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

• Peer-to-Peer

External Links

• The Byzantine Generals Problem (http://www.cs.wisc.edu/~bart/739/papers/byzantine.pdf) Lamport, Shostak, and Pease, ACM Transaction on Progamming Languages and Systems, 1982.