A communication-efficient canonical form for fault-tolerant distributed protocols

Abstract

Many fault-tolerant distributed protocols are known.Some of these require a large (exponential) amount of communication.We present a general simulation of any synchronous fault-tolerant consensus protocol by a communication-efficient protocol.An important corollary of the simulation technique is a new communicationefficient Byzantine agreement protocol that uses about half the number of rounds required by the best previouslyknown communication-efficient Byzantine agreement protocol.Our new protocol approaches the known lower bound for rounds to within a small factor arbitrarily close to 1.The only known protocols which achieve the lower bound for rounds use an exponential amount of communication.