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 synchronous 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 only constraint on the adversary is that it must choose its corrupt processors at the start, without knowledge of the processors’ private random bits. To the authors’ best knowledge, there have been no protocols for such a model that compute Byzantine agreement without all-to-all communication, even if private channels or cryptography are assumed, unless corrupt processors’ messages are limited.
In this paper, we give a polylogarithmic time algorithm to agree on a small representative committee of processors using only \(\tilde{O}(n^{3/2})\) total bits which succeeds with high probability. This representative set can then be used to efficiently solve Byzantine agreement, leader election, or other problems. This work extends the authors’ work on scalable almost everywhere agreement.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. John Wiley Interscience, Chichester (2004)
Ben-Or, M., Pavlov, E., Vaikuntanathan, V.: Byzantine agreement in the full-information model in o(log n) rounds. In: STOC, pp. 179–186 (2006)
Bortnikov, E., Gurevich, M., Keidar, I., Kliot, G., Shraer, A.: Brahms: Byzantine resilient random membership sampling. In: PODC 2008: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, Toronto, Canada, pp. 145–154. ACM, New York (2008)
Dolev, D., Reischuk, R.: Bounds on information exchange for byzantine agreement. J. ACM 32(1), 191–204 (1985)
Feige, U.: Noncryptographic selection protocols. In: FOCS 1999: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p. 142. IEEE Computer Society, Washington (1999)
Garay, J.A., Ostrovsky, R.: Almost-everywhere secure computation. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 307–323. Springer, Heidelberg (2008)
Georgiou, C., Gilbert, S., Guerraoui, R., Kowalski, D.R.: On the complexity of asynchronous gossip. In: Proceedings of the ACM symposium on Principles of distributed computing (PODC), pp. 135–144 (2008)
Goldwasser, S., Pavlov, E., Vaikuntanathan, V.: Fault-tolerant distributed computing in full-information networks. In: FOCS, pp. 15–26 (2006)
Gradwohl, R., Vadhan, S.P., Zuckerman, D.: Random selection with an adversarial majority. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 409–426. Springer, Heidelberg (2006)
Holtby, D., Kapron, B.M., King, V.: Lower bound for scalable byzantine agreement. Distributed Computing 21(4), 239–248 (2008)
Kapron, B.M., Kempe, D., King, V., Saia, J., Sanwalani, V.: Fast asynchronous byzantine agreement and leader election with full information. In: SODA, pp. 1038–1047 (2008)
King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 990–999. ACM Press, New York (2006)
King, V., Saia, J., Sanwalani, V., Vee, E.: Towards secure and scalable computation in peer-to-peer networks. In: FOCS 2006: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 87–98. IEEE Computer Society, Washington (2006)
Kotla, R., Alvisi, L., Dahlin, M., Clement, A., Wong, E.: Zyzzyva: speculative byzantine fault tolerance. SIGOPS Oper. Syst. Rev. 41(6), 45–58 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
King, V., Saia, J. (2009). From Almost Everywhere to Everywhere: Byzantine Agreement with \(\tilde{O}(n^{3/2})\) Bits. In: Keidar, I. (eds) Distributed Computing. DISC 2009. Lecture Notes in Computer Science, vol 5805. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04355-0_47
Download citation
DOI: https://doi.org/10.1007/978-3-642-04355-0_47
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04354-3
Online ISBN: 978-3-642-04355-0
eBook Packages: Computer ScienceComputer Science (R0)