The Byzantine generals strike again |
| |
Authors: | Danny Dolev |
| |
Institution: | Computer Science Department, Stanford University, Stanford, California 94305 USA |
| |
Abstract: | Can unanimity be achieved in an unreliable distributed system? This problem was named the “Byzantine Generals Problem” by L. Lamport, R. Shostak, and M. Pease (Technical Report 54, Computer Science Laboratory, SRI International, March 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 for obtaining it are given. This result forms a complete characterization of networks in the light of the Byzantine Problem. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|