An <i>O</i> (log <i>n</i> ) expected rounds randomized byzantine generals protocol

Abstract

Byzantine Generals protocols enable processes to broadcast messages reliably in the presence of faulty processes. These protocols are run in a system that consists of n processes, t of which are faulty. The protocols are conducted in synchronous rounds of message exchange. It is shown that, in the absence of eavesdropping, without using cryptography, for any ε &gt; 0 and t = n /(3 + ε), there is a randomized protocol with O (log n ) expected number of rounds. If cryptographic methods are allowed, then, for ε &gt; 0 and t = n /(2 + ε), there is a randomized protocol with O (log n ) expected number of rounds. This is an improvement on the lower bound of t + 1 rounds required for deterministic protocols, and on a previous result of t /log n expected number of rounds for randomized noncryptographic protocols.