An O(lg n) expected rounds randomized Byzantine generals protocol

Abstract

Byzantine Generals protocols enable processes to reliably broadcast messages in the presence of faulty processes. These protocols are run in a system of consists of n processes, t of which are faulty. The protocols are conducted in synchronous rounds of message exchange. We show that, without using cryptography, for t = n/(3 + d), there is a randomized protocol with O(lg n) expected number of rounds. If we allow cryptographic methods, then, for t = n / (2 + d), there is a randomized protocol with O(lg n) expected number of rounds. This is an improvement on the lower bound of t + 1 rounds required for det … … previous result of t/lg n expected nu rounds for randomized protocols.