L. Lamport, R. Shostak, and M. Pease @ SRI International
ACM Transactions on Programming Languages and Systems, July 1982, pages 382401
The
Classic Problem


The
problem can be restated as:


The
above problem can be reduced into a series of one commanding general and
multiple lieutenants problem  Byzantine Generals Problem :

One way to achieve reliability is to have multiple replica of system (or component) and take the majority voting among them  
In
order for the majority voting to yield a reliable system, the following
two conditions should be satisfied:

No solution exists if less than or equal to 2/3 generals are loyal 
A1
 Every message that is sent is delivered correctly


A2
 The receiver of a message knows who sent it


A3
 The absence of a message can be detected

If less than 1/3 generals are traitors, this problem can be solved  
Algorithm
 recursive

A4:


Implication

If at least two generals are loyal, this problem can be solved  
Algorithm
 recursive

Network topology or policy could keep a general sending/receiving messages to/from another general 

This constraint makes Byzantine problem more general 
If
the communication graph is 3mregular and less than or equal to m generals
are traitors, this problem can be solved


Algorithm
 extension of oral message

If the subgraph of loyal generals is connected, this problem can be solved 