Randomized distributed agreement revisited

The authors present a succint and efficient randomized distributed agreement (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 (/spl Theta/(log n) message size) and does not require any 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 some previous solutions. The authors contrast their 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.