Abstracts - 2007
Random Selection and Byzantine Agreement in the Full-Information Model
Shafi Goldwasser, Elan Pavlov & Vinod Vaikuntanathan
Random Selection is the problem of how n players can make a common and random selection of an element from a set, despite some of the players being faulty. Random Selection, when achievable, has proven immensely useful in the design of distributed algorithms and cryptographic protocols. Our work aims to address this fundamental primitive in the strongest adversarial setting -- the full-information model, where the adversary has unlimited computational and eavesdropping power. We show:
Stronger Protocols for Random Selection
The problem of random selection was studied in various network models: the private channels model where players can communicate via perfectly private pairwise communication channels; the computational model where the faulty players are assumed to be computationally bounded and cryptographic primitives are assumed to exist; and the full information model where no assumptions are made on the existence of private channels nor are the faulty players computationally restricted. Our focus is on the full-information model, which is the strongest of these adversarial settings.
There is an extensive body of work (starting with the work of Ben-Or and Linial  and Goldreich, Goldwasser and Linial ) on efficient random selection protocols in the full information model. However, these protocols all make an additional assumption: reliable broadcast channels exist for free. Namely, when an honest player receives a message that is 'broadcast', he is guaranteed that all other honest players received the same message even if it was sent by a faulty player. Thus, no part of the protocol needs to be dedicated to ambiguity. Indeed, both the correctness and efficiency (including the round complexity) of these protocols hold only under the additional assumption that broadcast is an atomic unit-cost operation.
In recent work , we show how to achieve random selection from scratch -- that is, without set-up assumptions such as the existence of a reliable broadcast channel. While removing the set-up assumptions, our protocols incur a cost -- while the random selection protocols with reliable broadcast channels have a round-complexity of log* n, our protocol incurs a round-complexity of O(log n).
Applications to Distributed Algorithms
We show numerous applications of the stronger random selection protocol we construct, as well as the techniques used therein. For example, we use the random selection protocol to construct:
Technical Tools: Auditing Protocols
The technical tools we construct and use to design these protocols are, in our opinion, as valuable as the results themselves. The main tool we define and construct is what we called the auditing compiler -- which takes any distributed protocol that uses broadcast channels and compiles them into ones that do not assume reliable broadcast. The resulting protocol (which does not assume reliable broadcast), however, has a slightly weaker guarantee than the original protocol (which assumes reliable broadcast). Despite this, we use this tool in constructing our random selection protocol, and applications thereof.
There are two directions that we envisage for future work in this area. The first one is to improve the efficiency of the random selection protocols -- while the protocol we construct has a round-complexity of O(log n), it would be desirable to achieve a log* n-round (or, where achievable, a constant-round) protocol. The second direction is to find more applications of the tools we construct in this work -- namely, auditing of protocols. Auditing has already given us an impressive array of applications, and we expect that there are more.
This work was generously supported by NSF grants CNS-0430450 and CCF0514167.
 Michael Ben-Or and Nathan Linial. Collective coin flipping, robust voting schemes and minima of banzhaf values. In FOCS, pages 408--416, 1985.
 Michael Ben-Or, Elan Pavlov, and Vinod Vaikuntanathan. Byzantine agreement in the full-information model in O(log n) rounds. In STOC, 2006.
 Gabriel Bracha. An asynchronous (n-1)/3-resilient consensus protocol. In PODC, pages 154--162, 1984.
 Oded Goldreich, Shafi Goldwasser, and Nathan Linial. Fault-tolerant computation in the full information model. In SIAM Journal of Computing, 27(2):506--544, 1998.
 Shafi Goldwasser, Elan Pavlov and Vinod Vaikuntanathan. Fault-tolerant Distributed Computing in the Full-Information Model In FOCS, 2006.
 Anna Karlin and Andrew Chi-Chih Yao. Probabilistic lower bounds for byzantine agreement. Manuscript, 1986.
 Marshall Pease, Robert Shostak and Leslie Lamport. Reaching agreement in the presence of faults. In Journal of the ACM, 27:228--234, 1980.