The Byzantine Generals Problem 383
may be traitors, trying to prevent the loyal generals from reaching agreement.
The generals must have an algorithm to guarantee that
A. All loyal generals decide upon the same plan of action.
The loyal generals will all do what the algorithm says they should, but the
traitors may do anything they wish. The algorithm must guarantee condition A
regardless of what the traitors do.
The loyal generals should not only reach agreement, but should agree upon a
reasonable plan. We therefore also want to insure that
B. A small number of traitors cannot cause the loyal generals to adopt a bad
Condition B is hard to formalize, since it requires saying precisely what a bad
plan is, and we do not attempt to do so. Instead, we consider how the generals
reach a decision. Each general observes the enemy and communicates his obser-
vations to the others. Let
be the information communicated by the ith
general. Each general uses some method for combining the values v (1) ..... v (n)
into a single plan of action, where n is the number of generals. Condition A is
achieved by having all generals use the same method for combining the infor-
mation, and Condition B is achieved by using a robust method. For example, if
the only decision to be made is whether to attack or retreat, then
General i's opinion of which option is best, and the final decision can be based
upon a majority vote among them. A small number of traitors can affect the
decision only if the loyal generals were almost equally divided between the two
possibilities, in which case neither decision could be called bad.
While this approach may not be the only way to satisfy conditions A and B, it
is the only one we know of. It assumes a method by which the generals
communicate their values v (i) to one another. The obvious method is for the ith
general to send v (i) by messenger to each other general. However, this does not
work, because satisfying condition A requires that every loyal general obtain the
same values v(1) .....
and a traitorous general may send different values to
different generals. For condition A to be satisfied, the following must be true:
1. Every loyal general must obtain the same information v (1) .... , v (n).
Condition 1 implies that a general cannot necessarily use a value of
obtained directly from the ith general, since a traitorous ith general may send
different values to different generals. This means that unless we are careful, in
meeting condition 1 we might introduce the possibility that the generals use a
value of v (i) different from the one sent by the ith general--even though the ith
general is loyal. We must not allow this to happen if condition B is to be met. For
example, we cannot permit a few traitors to cause the loya~ generals to base their
decision upon the values "retreat",..., "retreat" if every loyal general sent the
value "attack". We therefore have the following requirement for each i:
2. If the ith general is loyal, then the value that he sends must be used by every
loyal general as the value of v (i).
ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982.