Flipping persuasively in constant expected time
Cynthia Dwork, David B. Shmoys, Larry Stockmeyer · 1986
We present a distributed protocol for achieving a distributed coin in the presence of an extremely powerful adversary in constant time. The protocol can tolerate up to n/log n malicious processor failures where n is the number of processors in the system. The protocol needs only a fixed constant number of rounds of message exchange; no preprocessing is required. As a corollary we obtain an (n/log n)-resilient probabilistic protocol for Byzantine agreement running in constant expected time. Combining this with a generalization of a technique of Bracha, we obtain a probabilistic Byzantine agreement protocol tolerant of almost n/3 failures with O(log log n) expected running time.