About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 1983
Conference paper
FLIPPING COINS IN MANY POCKETS (BYZANTINE AGREEMENT ON UNIFORMLY RANDOM VALUES).
Abstract
It was recently shown by M. O. Rabin (1983) that a sequence of random 0-1 values, prepared and distributed by a trusted 'dealer,' can be used to achieve Byzantine agreement in constant expected time in a network of processors. A natural question is whether it is possible to generate these values uniformly at random within the network. The authors present a cryptography-based protocol for agreement on a 0-1 random value, if less than half of the processors are faulty. In fact, the protocol allows uniform sampling from any finite set and thus solves the problem of choosing a network leader uniformly at random. The protocol is usable both when all the communication is via broadcast, in which case it needs three rounds of information exchange, and when each pair of processors communicate on a private line, in which case it needs 3t plus 3 rounds, where t is the number of faulty processors. The protocol remains valid even if passive eavesdropping is allowed. On the other hand, it is shown that no (probabilistic) protocol can achieve agreement on a fair coin in fewer phases than necessary for Byzantine agreement, and hence the 'predealt' nature of the random sequence required for Rabin's algorithm is crucial.