Randomized Asynchronous Byzantine Agreements

Abstract

A randomized protocol for reaching Byzantine Agreement in asynchronous systems with $n$ processes was recently proposed in [Rabi83]. This protocol tolerates up to $\lfloor (n-1)/10 \rfloor$ faulty processes, and agreement is reached within an expected number of phases that is a small constant independent of $n$ and the number of faulty processes $t$. In this paper, using the same computation model as in [Rabi83], it is shown that no Byzantine Agreement protocol can overcome more than $\lfloor (n-1)/3 \rfloor$ faulty processes in an asynchronous system, and we describe a protocol that achieves this upper bound. Agreement is also 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}.