Randomized Byzantine Agreements

Randomized algorithms for reaching Byzantine Agreement were recently proposed in Rabi83. With these algorithms, agreement is reached within an expected number of phases that is a small constant independent of the number of processes n and the number of faulty processes t. The algorithms in Rabi83 tolerate up to (n-1)/10 faulty processes in asynchronous systems, and up to (n-1)/4 faulty processes in synchronous systems. In this paper, using the same computation model as in Rabi83, we describe algorithms that overcome up to (n-1)/3 faulty processes in asynchronous systems, and up to (n-1)/2 faulty processes in synchronous systems. With both proposed algorithms, agreement is reached within an expected number of phases that is a small constant independent of n and t, but the communication complexity is higher than in Rabi83. It is also shown that no Byzantine Agreement algorithm can overcome more than (n-1)/3 faulty processes in asynchronous authenticated systems, and hence the asynchronous algorithm proposed here is optimal in this respect.