The Byzantine Generals Problem
L. Lamport, R. Shostak, and M. Pease

This paper uses the analogy between the components of a distributed
system and the Byzantine Generals problem to formalize the constraints
and to find the conditions under which the underlying communication
protocol can be considered reliable and an agreement is guaranteed to
be reached even with existing malfunctioning components and faulty
transmission media. The basic and fundamental thing is the interactive
consistency conditions. The first condition is concerned with
receiving the same message by all non-faulty processes from the same
input unit. This condition corresponds to obeying the same order by
all loyal lieutenants in the Byzantine Generals Problem. The second
condition is more restricted than the first one. It states if the
input unit is non-faulty then all the non-faulty processes use the
same input value. This is analogous to the condition if the commander
is loyal, then every loyal lieutenant obeys the order he sends.

This interactive consistency is stated by two conditions although both
of them are applied to the same exchanged message. The reason for that
is the protocol is being used has to deal with faulty input unit (or
disloyal commander) trying to confuse the non-faulty components (or
loyal lieutenants) by sending different messages to them. The protocol
has to guarantee that all of the clients will take the same reasonable
action. To achieve this all the clients have to repeat to each other
what they receive from the commander (the input units). But some of
these clients might be faulty (or disloyal) and hence they might try
to confuse the other by claiming wrong commands they received from the
commander (or the input units). This leads to the second condition.

The paper presents first the algorithm the OM to solve this
problem. In which case, the message is under the control of the sender
either the commander or the other clients repeating the messages they
heard from. In OM, the communication media guarantee three
conditions. 1. Any message was sent must be received. 2. The identity
of the sender is well known to the receiver. 3. The receiver has the
ability to detect if a message is lost. With OM algorithm, the problem
is not solvable unless there are at most m traitors (non-faulty)
lieutenants out from a total of (n = 3m + 1) lieutenants. In this
algorithm after the commander sends a message to all other (n -1)
clients, each client receives this message acts as a commander and
sends it to the other clients excluding the commander. At the end each
client will have (n > 1) copies from the same message. It concludes
the actual order by getting the median of these messages.

The second algorithm, SM, uses signed messages for communication. To
use signed messages, the communication protocol has to satisfy one
more condition. 4. The signature of the sender can’t be forged and the
clients can verify the authenticity of the sender’s signature.  There
is no limit of the number of faulty clients like in the SM; instead,
the algorithm can cope with number of faulty clients. Like in OM, SM
protocol asks each client to send to the other clients the signed
message which the commander sends after adding its own signature. The
function choice is used here to get the final action that has to be
taken. The algorithm has to deal with the fact that some
malfunctioning clients may not send their copies of messages at all
and the non-faulty process has to know when to there is no more
messages; otherwise it will wait indefinitely.

The assumption that the graph connecting the nodes in completely
connected can be removed since in the real life, almost all the
networks (not necessarily computer networks) are not completely
connected. The extended OM algorithm can solve (The Byzantine Generals
Problem) with m traitors is if the connecting graph is 3m-regular. The
extended SM algorithm can solve the problem for (n > 2) traitors if
the sub-graph of the loyal generals is connected which is the weakest
connectivity hypothesis. However the general case states that, SM
solves the problem for (m + d > 1) where d is the diameter of
sub-graph of loyal generals.

The paper ends with discussion which is purely related to the computer
field. The factors that make the communication reliable are stated
insufficiently. The time-out technique and the clock synchronization
are also discussed very briefly. At the end the network security and
cryptography are also mentioned.  The paper is easy to read and the
proofs of theorems are intelligently explained and the analogy with
The Byzantine Generals Problem is perfectly used. The authors switch
to use the computer terminology almost at the end of the paper. That
is why the sections about the system reliability, network security and
clock synchronization are inadequate. Apart from this the paper is
really an innovative even in its structure.