Efficient distributed consensus with n=(3 + ∊)t processors

In a Distributed Consensus protocol n processors, of which at most t may be faulty, are given initial binary values; after exchanging messages all the processors that are correct must agree on one of the initial values. We measure the quality of a consensus protocol by the following parameters: the total number of processors n, the number of rounds of message exchange r, and the communication complexity, given by the maximal message size. This paper presents a protocol that achieves Distributed Consensus with n=(3 + ε)t, r=t + 1, and polynomial message size for ε ≥ 1/log t, Thus, this is the first consensus protocol to use simultaneously nearly optimal number of processors (n= 3t + 1 is the known lower bound). optimal number of rounds, and short messages. Previous round-optimal protocols with polynomial communication required n=Ω(t²), n > 6t and n > 4t, respectively. In order to obtain this result, we introduce new techniques for the abbreviation of messages in the classical full information consensus protocol. In particular, we introduce the Dynamic Fault Masking technique, called that way because the values that the correct processors use to mask the faults is computed on the fly during the execution of the protocol.