Research Abstracts - 2007

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:

1. Stronger protocols for Random Selection: In particular, we show how to remove the setup assumptions that were implicit in the existing protocols, while maintaining the efficiency and fault-tolerance.
2. Various applications of (1) to solving long-standing open questions in distributed computing.

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 [1] and Goldreich, Goldwasser and Linial [4]) 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 [5], 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:

1. Efficient Byzantine Agreement: Byzantine Agreement -- a central problem in distributed computing -- is the problem of how n players, each of whom has a single bit input can agree on a common bit as the output.

   We construct an O(log n)-round randomized Byzantine Agreement (BA) protocol in a synchronous full-information network tolerating t < (1/3-ε)n faulty players (for any constant ε > 0). This achieves asymptotically optimal fault tolerance as Pease, Shostak and Lamport [7] and Karlin and Yao [6] show that BA is not possible if n < 3t+1. Our protocol improves on the fault-tolerance of the protocol of Ben-Or, Pavlov and Vaikuntanathan [2] who show an O(log n)-round Byzantine agreement for t < (1/4-ε)n.

2. A Fault-tolerance Boosting Compiler for Protocols: A fail-stop adversary models a benign fault whereas a Byzantine adversary models a much more severe fault. We use the techniques used to construct the random selection protocol to show a compiler that takes any randomized protocol designed to tolerate a Fail Stop adversary (with a technical condition) into a protocol that tolerates a Byzantine adversary. The round-complexity and fault-tolerance of the resulting protocol are the best possible. This partially answers the open question of Bracha [3].
3. Constant-round Byzantine Agreement for Small Number of Faults: In practice, it might be the case that the number of faults that actually occur in a system is much smaller than the worst-case number of faults that the system is designed to tolerate. Thus, it would be desirable to have protocols that are very efficient, but have a smaller fault-tolerance. As yet another application of the random selection protocol, we construct an O(1)-round randomized BA protocol tolerating O(n/log n) faulty players.

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.

Future Work

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.

Acknowledgments

This work was generously supported by NSF grants CNS-0430450 and CCF0514167.

References:

[1] Michael Ben-Or and Nathan Linial. Collective coin flipping, robust voting schemes and minima of banzhaf values. In FOCS, pages 408--416, 1985.

[2] Michael Ben-Or, Elan Pavlov, and Vinod Vaikuntanathan. Byzantine agreement in the full-information model in O(log n) rounds. In STOC, 2006.

[3] Gabriel Bracha. An asynchronous (n-1)/3-resilient consensus protocol. In PODC, pages 154--162, 1984.

[4] 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.

[5] Shafi Goldwasser, Elan Pavlov and Vinod Vaikuntanathan. Fault-tolerant Distributed Computing in the Full-Information Model In FOCS, 2006.

[6] Anna Karlin and Andrew Chi-Chih Yao. Probabilistic lower bounds for byzantine agreement. Manuscript, 1986.

[7] Marshall Pease, Robert Shostak and Leslie Lamport. Reaching agreement in the presence of faults. In Journal of the ACM, 27:228--234, 1980.