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.