ON AGREEMENT AND KNOWLEDGE IN A FAULTY NETWORK

Abstract

Asynchronous Randomized Byzantine Agreement Against Enhanced Omission Faults A network of processors, each given an initial value, is said to reach Byzantine Agreement (BA) if the correct processors unanimously agree on a decision value which, if all initial values are identical, must equal the initial value. We consider a completely asynchronous network of pairwise link-connected processors in which no global clock exists and message transit time is unbounded. In such a network rando111ized protocols, in which a processor's behavior may be influenced by the contents of its random tape (which is a sequence of independent, identically distributed random variables), arc able to achieve Rando1nized Byzantine Agreement (RBA), a practical alternative to (deterministic) BA which cannot be achieved in such a network against the most benign fault. We enhance the severity of the processor omission fault, which is standard, to consider an adversary with some of the following capabilities: M, scheduling and suppressing messages; I, reading processors' incoming messages; 0, reading processors' outgoing messages; R, reading random tapes and W, writing on random tapes. All processors arc assumed correct. We define twelve enhanced omission faults, grouped under four categories: failure modes with secure 10 ports, compromised input ports, compromised output ports and compromised 10 ports. We first present a protocol for achieving RBA assuming the existence of a trusted dealer, who reliably broadcasts the outcomes of ( possibly biased ) coin-tosses. We then present protocols which perform the function of a trusted dealer, and thereby achieving RBA (without actually requiring a trusted dealer) against the various enhanced omission faults. Our protocols proceed in sessions. The expected number of sessions required to achieve RBA is an important performance parameter. All our protocols achieve constant expected number of sessions, independent of the size of the network.