an o(lg n) expected rounds randomized byzantine generals protocol
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 + &dgr; ), there is a randomized protocol with &Ogr; ( lg n ) expected number of rounds. If we allow cryptographic methods, then, for t = n / (2 + &dgr; ), there is a randomized protocol with &Ogr;( 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.
randomization process broadcast message presence systems synchronization cryptography method lower bound