Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We address the problem of designing distributed algorithms for large scale networks that are robust to Byzantine faults. We consider a message passing, full information model: the adversary is malicious, controls a constant fraction of processors, and can view all messages in a round before sending out its own messages for that round. Furthermore, each corrupt processor may send an unlimited number of messages. The adversary is constrained to choose its corrupt processors at the start, without knowledge of the processors' private random bits, but is otherwise adaptive. To the authors' best knowledge, there have been no subexponential protocols in the asynchronous version of this model and no protocols that compute Byzantine agreement without all-to-all communication in this model even a model in which private channels or cryptography are assumed, unless corrupt processors' messages are limited. We announce a polylogarithmic time protocol in the asynchronous model which appeared in SODA 08 and was recently improved to a resilience of n/(3 + ε). We also give a polylogarithmic time protocol for Byzantine agreement using only Õ(n^3/2) total bits of pairwise communication which succeeds with high probability. These results rest on our solution to the problem of selecting a small representative sample of processors (universe reduction). This work extends the authors' work on scalable almost everywhere agreement to everywhere agreement and is an unpublished manuscript.

REFERENCES

• 1: Edward Bortnikov , Maxim Gurevich , Idit Keidar , Gabriel Kliot , Alexander Shraer, Brahms: byzantine resilient random membership sampling, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400772]
• 2: Uriel Feige, Noncryptographic Selection Protocols, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.142, October 17-18, 1999
• 3: Chryssis Georgiou , Seth Gilbert , Rachid Guerraoui , Dariusz R. Kowalski, On the complexity of asynchronous gossip, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400771]
• 4: Ronen Gradwohl, Salil P. Vadhan, and David Zuckerman. Random selection with an adversarial majority. In CRYPTO, pages 409--426, 2006.
• 5: Dan Holtby, Bruce M. Kapron, and Valerie King. Lower bound for scalable byzantine agreement. Distributed Computing, 21(4):239--248, 2008.
• 6: Bruce Kapron , David Kempe , Valerie King , Jared Saia , Vishal Sanwalani, Fast asynchronous byzantine agreement and leader election with full information, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1038-1047, January 20-22, 2008, San Francisco, California
• 7: Valerie King and Jared Saia. Unpublished manuscript.
• 8: Valerie King , Jared Saia , Vishal Sanwalani , Erik Vee, Scalable leader election, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.990-999, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109667]
• 9: Valerie King , Jared Saia , Vishal Sanwalani , Erik Vee, Towards Secure and Scalable Computation in Peer-to-Peer Networks, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.87-98, October 21-24, 2006 [doi>10.1109/FOCS.2006.77]
• 10: Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin , Allen Clement , Edmund Wong, Zyzzyva: speculative byzantine fault tolerance, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Algorithms, Reliability, Theory

Keywords:
asychrony, byzantine agreement, communication complexity, gossiping, leader election, message complexity, synchrony