Randomized Byzantine Agreement

Abstract

A randomized model of distributed computation was presented in [Rabin83]. This model admits a solution to the Byzantine Agreement Problem for systems of $n$ asynchronous processes where no more than $t$ are faulty. The algorithm described in [Rabin83] produces agreement in an expected number of rounds whish is a small constant independent of $n$ and $t$. Using the same model, we present an algorithm of similar complexity which is able to tolerate a greater proportion of malicious processes. The algorithm is also applicable, with minor changes, to systems of synchronous processes.