BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-81-846
       ENTRY:: June 05, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: The Byzantine Generals strike again
        TYPE:: Technical Report
      AUTHOR:: Dolev, Danny
        DATE:: March 1981
       PAGES:: 30
    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.
       NOTES:: [Adminitrivia V1/Prg/19950605]
         END:: STAN//CS-TR-81-846