FLIPPING PERSUASIVELY IN CONSTANT EXPECTED TIME.

Abstract

A distributed protocol is presented for achieving a distributed coin in the presence of an extremely powerful adversary in constant time. The prototcol 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 an (n/log n)-resilient probabilistic protocol for Byzantine agreement running in constant expected time is obtained. From this there is further obtained a probabilistic Byzantine agreement protocol tolerant of almost n/3 failures with O(log log n) expected running time.