Randomized distributed agreement revisited

Distributed Agreement (DA) is one of the fundamental problems in the theory and practice of fault-tolerant distributed systems. It requires correct processors (agents, players) to agree on an initial value held by one of them, despite the (even malicious) behavior of a subset of size t. A randomized solution to the problem achieves agreement with a high probability after a constant number of communication rounds. In this paper we present a succinct and efficient randomized DA protocol for asynchronous networks that works for n > 5t processors, where n is the size of the network. The protocol has low communication complexity (Θ(log n) message size) and does not require an cryptographic assumption. The protocol belongs to the class of protocols that require a `trusted dealer,' who is in charge of a suitable network initialization, and represents an improvement in terms of number of processors to previous solutions presented in. We contrast our approach to the class of protocols that are currently able to perform randomized agreement from scratch, an unlimited number of times, but have a communication cost that might be infeasible in many cases.