An O(lg n) Expected Rounds Probabilistic Byzantine Generals Algorithm (The Bigger They Are, The Harder They Fall)
Byzantine Generals algorithms enable processes to reliably broadcast messages in a system of $n$ processes where up to $t$ of the processes may be faulty. The algorithms are conducted in synchronous rounds of message exchange. For a system where $n = (3 + \delta)t$ we prove the existence of a randomized algorithm whose expected number of rounds is $O(lg n)$. This is an improvement on the lower bound of $t + 1$ rounds required for deterministic algorithms and on the previous result of $t/lg n$ expected number of rounds for randomized algorithms.
computer science; technical report
Previously Published As