Citation:
L. Lamport, R. Shostak, and M. Pease, "The Byzantine Generals Problem", ACM
Transactions on Programming Languages and Systems, July 1982, pp. 382-401.

* Summary

Reliable computer systems must handle malfunctioning components that give
conflicting information to different parts of the system. This situation can
be expressed abstractly in terms of a group of generals of the Byzantine army
camped with their troops around an enemy city. Communicating only by messenger,
the generals must agree upon a common battle plan. However, one or more of them
may be traitors who will try to confuse the others. The problem is to find an
algorithm to ensure that the loyal generals will reach agreement. It is shown
that, using only oral messages, this problem is solvable iff more than two-
thirds of the generals are loyal. With unforgeable written messages, the 
problem is solvable for any number of generals and possible traitors.

* Reaching Agreement

The problem is making sure that all loyal generals decide upon the same plan
of action and a small number of traitors cannot cause the loyal generals to
adopt a bad plan. To reach a decision, each general sends his recommendation
to all other generals, and all generals use the same method for combining the
information. To prevent a small number of traitors from having undue influence
on the decision, the method chosen for combining must be robust.

* Byzantine Generals Problem

A commanding general must send an order to his n-1 lieutenant generals such
that:
IC1. All loyal lieutenants obey the same order
IC2. If the commanding general is loyal, then every loyal lieutenant obeys the
     order he sends

The solution to this problem can be used in meeting the requirements for 
reaching agreement in the original problem, by having each general send his
order to all the other generals, acting as lieutenants.

* Solution with Oral Messages

The solution to the BGP for oral messages that copes with m traitors requires
there to be at least 3m+1 generals. The assumptions made for oral messages are:
(A1) every message sent is delivered correctly
(A2) the receiver of a message knows who sent it
(A3) the absence of a message can be detected

The algorithm is defined inductively for all nonnegative integers m, by which
a commander sends an order to n-1 lieutenants. The algorithm solves the BGP for
at most m traitors with at least 3m+1 generals.

OM(0):
(1) the commander sends his value to every lieutenant
(2) each lieutenant uses the value he receives from the commander, or uses the
    value retreat if he receives no value

OM(m), m>0:
(1) the commander sends his value to every lieutenant
(2) for each i, let v_i be the value lieutenant i receives from the commander,
    or retreat if no value was received. lieutenant i acts as the commander in
    algorithm OM(m-1) to send the value v_i to each of the n-2 other lieutenants
(3) for each i, and each j!=i, let v_i be the value lieutenant i received from
    lieutenant j in step (2), or else retreat if no value was received. 
    lieutenant i uses the value majority(v_1, ... , v_n-1)

* Solution with Signed Messages

This solution solves the problem for m traitors and any number of loyal 
lieutenants. The following assumption is added to those of the oral message
solution:
(A4) a loyal general's signature cannot be forged, and any alteration can be
     detected. anyone can verify the authenticity of a general's signature

SM(m):
Initially, V_i = {}.
(1) the commander signs and sends his value to every lieutenant
(2) for each i:
  a) if lieutenant i receives a message of the form v:0 from the commander
     and he has not yet received any order, then
     i. he lets V_i equal {v}
    ii. he sends the message v:0:i to every other lieutenant
  b) if lieutenant i receives a message of the form v:0:j_1:...:j_k and v is
     not in the set V_i, then
     i. he adds v to V_i
    ii. if k<m, then he sends the message v:0:j_1:...:j_k:i to every lieutenant
        other than j_1 ... j_k.
(3) for each i, when lieutenant i will receive no more messages, he obeys the 
    order choice(V_i)

* Missing Communication Paths

It can be shown that OM(m,p) and SM(m,p) are still valid solutions to the BGP
if the graph of generals is p-regular. A graph is p-regular if every node i has
a set of p neighbors such that for any general k different than i, there exists
paths from any neighbor to k not passing through i where any two paths have no
node in common.

* Reliable Systems

Using the redundant components in a system as generals, the BGP solutions can 
be used to reach agreement. Care must be taken to show that the assumptions
made by the algorithms are valid within a hardware environment.