The Byzantine Generals Problem
[Lamport, Shostak, Pease '82]

This paper introduces a very extreme model of fault tolerance in a
distributed system.  The distributed system described is that of a number
of Byzantine generals deciding whether or not to attack a particular city.
In this case, it is essential that either they all attack or all retreat,
since it would be suicide for a single general to attack without the
support of the others.  Furthermore, a  number of generals may be faulty
or, in the worst case, malicious and colluding.  Alternatively, this could
just as well be a problem involving several processors which need to agree
on a binary value, where a number of the processors are controlled by an
evil hacker.

The main contributions of this paper are: 1. A model of malicious,
colluding adversaries and 2. The algorithms used to achieve consensus
despite them.  These algorithms leave something to be desired.  They rest
on a set of assumptions about messages that are difficult to implement, and
even with these assumptions they may require a number of messages which is
exponential in the number of traitors.

In general, there are two desired properties:
(A)  All loyal generals decide on the same plan.
This seems reasonable since we cannot guarantee the traitors' actions.  A
simple solution to this problem is to always attack.  Obviously this is not
a very interesting solution.  The following property addresses this and more:
(B)  A small number of traitors cannot cause the loyal generals to adopt a
"bad" plan.  

They then proceed to give algorithms for different situations.  First let's
go over the guarantees of the algorithms and second the assumptions they
make about messages.  The simplest algorithm relies on the generals having
unforgeable signatures that they can add to orders.  In the processor
model, these could be cryptographically based.  There are two important
features of such a signature.  First, anyone can verify that a general
signed a particular message.  Second, no one can forge the signature of a
general.  In this case, their algorithm ensures that all the good
processors agree on a value, regardless of the number of traitors.  This
consensus value is a prespecified function of the votes of all the
generals, loyal or traitorous.

The next algorithm does not rely on signatures but instead on authenticated
messages.  That is, it assumes that the receiver of any message can verify
who the sender is.  The protocol described is complicated and inefficient,
but guarantees agreement in the case where there are less than 1/3
traitors.  Again, the agreed value is a prespecified function of the votes
of all processors.  It is also shown that this type of agreement can't be
reached if there are at least 1/3 traitors.

The assumptions about the messages are:
1.  Every message that is sent is delivered correctly.
The above algorithms must be able to tolerate a small number of mistakes in
deliveries since these errors could have also been caused by traitors.
That is assuming we don't already have the maximum number of traitors.
2.  The receiver of a message knows who sent it.

This could be implemented by point-to-point communication where there is a
trusted physical wires connecting each pair of computers.  This is only
necessary when we don't have unforgeable signatures.
3.  The absence of a message can be detected.
The simplest way to guarantee this is to have a timeout mechanism.
However, having such a timeout seems to imply synchronized clocks, which is
yet another consensus problem.

In conclusion, the Byzantine algorithms are tolerant of a small number of
traitors.  While it is much easier with unforgeable signatures, both cases
rely on strong assumptions about the communication.