An O (log n ) expected rounds randomized byzantine generals protocol

Publisher Website
Google Scholar
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 ε > 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 ε > 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.

This publication has 4 references indexed in Scilit: