Report Number: CS-TR-81-846
Institution: Stanford University, Department of Computer Science
Title: The Byzantine Generals strike again
Author: Dolev, Danny
Date: March 1981
Abstract: Can unanimity be achieved in an unreliable distributed system? This problem was named "The Byzantine Generals Problem," by Lamport, Pease and Shostak [1980]. The results obtained in the present paper prove that unanimity is achievable in any distributed system if and only if the number of faulty processors in the system is: 1) less than one third of the total number of processors; and 2) less than one half of the connectivity of the system's network. In cases where unanimity is achievable, algorithms to obtain it are given. This result forms a complete characterization of networks in light of the Byzantine Problem.
http://i.stanford.edu/pub/cstr/reports/cs/tr/81/846/CS-TR-81-846.pdf