Towards optimal distributed consensus

In a distributed consensus protocol all processors (of which t may be faulty) are given (binary) initial values; after exchanging messages all correct processors must agree on one of them. The quality of a protocol is measured here using as parameters the total number of processors n, number of rounds of message exchange r, and maximal message length m, with optima, respectively, of 3t + 1, t + 1, and 1. Although no known protocol is optimal in all these three aspects simultaneously, the protocols that take further steps in this direction are presented. The first protocol has n > 4t, r = t + 1, and polynomial message size. The second protocol has n > 3t, r = 3t + 3, and m = 2, and it is asymptotically optimal in all three quality parameters while using the optimal number of processors. Using these protocols as building blocks, families of protocols with intermediate quality parameters, offering better tradeoffs than previous results, are obtained. All the protocols work in polynomial time and have succinct descriptions.