Byzantine fault tolerance

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.

Related Topics:
Byzantine army - Generals

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~