Review of: The Byzantine Generals Problem

Summary: A mechanism for distributed computers to arrive at a correct
concensus in the face of failures is developed using a Byzantine
Generals allegory.

The most important ideas in this paper are:

-In the Byzantine Generals Problem the goal is to have the different
 units communicate with each other to decide upon a common desirable
 plan.  This is an allegory for the collaboration in a distributed
 computer system.

-Using non-signed messages there must be fewer than 1/3 traitors in
 the group to come to the correct agreement, even if the agreement is
 approximate.

-If all loyal generals can communicate with each other via other loyal
 generals and they sign their messages then they can reach agreement
 if there are 2 or more of them.

-All of the assumptions used in the Byzantine Generals Problem hold
 true with real distributed computer systems, as long as distributed
 clocks can be synchronized within some error.  This means the same
 class of problems are solved for distributed computer systems.

The largest one or two flaws in the paper are:

-The paper went into great detail on how to use unsigned messages to
 come to a correct concensus as long as there were fewer than m
 traitors amongst 3m+1 generals.  It was also shown that if signing
 was employed at least 2 generals have to be loyal, as long as they
 are connected.  Signing seems to be vastly superior and obviates the
 more expensive non-signing problem.  There was no discussion on why
 one would design a system without signing.

Relevance of paper to modern systems:

In distributed systems errors will occur.  The Byzantine Generals
Problem goes a step further by showing a mechanism that overcomes
maliciously incorrect errors as long as they're kept below a certain
threshold and a certain network connectivity is in place.  There is an
upper bound to the number of errors sustainable in the system.  One
good application of this information is in P2P networks.  As long as
the RIAA controls less than 1/3 -1 of the P2P nodes the file swapping
may continue.