research-article

Fast asynchronous Byzantine agreement and leader election with full information

Authors:

Bruce M. Kapron,

Vishal SanwalaniAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 6, Issue 4

Article No.: 68, Pages 1 - 28

https://doi.org/10.1145/1824777.1824788

Published: 03 September 2010 Publication History

Abstract

We resolve two long-standing open problems in distributed computation by describing polylogarithmic protocols for Byzantine agreement and leader election in the asynchronous full information model with a nonadaptive malicious adversary. All past protocols for asynchronous Byzantine agreement had been exponential, and no protocol for asynchronous leader election had been known. Our protocols tolerate up to (1/3 − ϵ) ⋅ n faulty processors, for any positive constant ϵ. They are Monte Carlo, succeeding with probability 1 − o(1) for Byzantine agreement, and constant probability for leader election. A key technical contribution of our article is a new approach for emulating Feige's lightest bin protocol, even with adversarial message scheduling.

References

[1]

Ajtai, M. and Linial, N. 1993. The influence of large coalitions. Combinatorica 13, 2, 129--145.

[2]

Aspnes, J. 1998. Lower bounds for distributed coin-flipping and randomized consensus. J. ACM 45, 3, 415--450.

Digital Library

[3]

Attiya, H. and Censor, K. 2007. Tight bounds for asynchronous randomized consensus. In Proceedings of the 38th ACM Symposium on Theory of Computing. ACM Press, New York, NY, USA, 155--164.

Digital Library

[4]

Attiya, H. and Censor, K. 2008. Lower bounds for randomized consensus under a weak adversary. In Proceedings of the 27th ACM Symposium on Principles of Distributed Computing. 315--324.

Digital Library

[5]

Ben-Or, M. 1983. Another advantage of free choice: Completely asynchronous agreement prototols. In Proceedings of the 2nd ACM Symposium on Principles of Distributed Computing. 27--30.

Digital Library

[6]

Ben-Or, M. and El-Yaniv, R. 2003. Resilient-Optimal interactive consistency in constant time. Distrib. Comput. 16, 4, 249--262.

Digital Library

[7]

Ben-Or, M. and Linial, N. 1989. Collective coin flipping. In Advances in Computing Research 5: Randomness and Computation, S. Micali, Ed. JAI Press, 91--115.

[8]

Ben-Or, M., Pavlov, E., and Vaikuntanathan, V. 2006. Byzantine agreement in the full-information model in o(log n) rounds. In Proceedings of the 37th ACM Symposium on Theory of Computing. 179--186.

Digital Library

[9]

Berman, P. and Garay, J. A. 1993. Randomized distributed agreement revisited. In Digest of Papers: FTCS-23, the 23rd Annual International Symposium on Fault-Tolerant Computing. 412--419.

[10]

Bracha, G. 1984. An asynchronous {(n-1)/3}-resilient consensus protocol. In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing. 154--162.

Digital Library

[11]

Cachin, C., Kursawe, K., and Shoup, V. 2005. Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography. J. Cryptol. 18, 3, 219--246.

Digital Library

[12]

Canetti, R. and Rabin, T. 1993. Fast asynchronous byzantine agreement with optimal resilience. In Proceedings of the 25th ACM Symposium on Theory of Computing. 42--51.

Digital Library

[13]

Chor, B. and Dwork, C. 1989. Randomization in Byzantine agreement. In Advances in Computing Research 5: Randomness and Computation, S. Micali, Ed. JAI Press, 443--497.

[14]

Chor, B., Merritt, M., and Shmoys, D. B. 1989. Simple constant-time consensus protocols in realistic failure models. J. ACM 36, 3, 591--614.

Digital Library

[15]

Feige, U. 1999. Noncryptographic selection protocols. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science. 142--153.

Digital Library

[16]

Fischer, M. J., Lynch, N. A., and Paterson, M. 1983. Impossibility of distributed consensus with one faulty process. In Proceedings of the 2nd ACM Symposium on Principles of Database Systems. 1--7.

Digital Library

[17]

Goldwasser, S., Pavlov, E., and Vaikuntanathan, V. 2006. Fault-Tolerant distributed computing in full-information networks. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science. 15--26.

Digital Library

[18]

Gradwohl, R., Vadhan, S. P., and Zuckerman, D. 2006. Random selection with an adversarial majority. In Proceedings of the 26th International Cryptology Conference (CRYPTO). 409--426.

Digital Library

[19]

King, V., Saia, J., Sanwalani, V., and Vee, E. 2006a. Scalable leader election. In Proceedings of the 17th ACM Symposium on Discrete Algorithms. 990--999.

Digital Library

[20]

King, V., Saia, J., Sanwalani, V., and Vee, E. 2006b. Towards secure and scalable computation in peer-to-peer networks. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science. 87--98.

Digital Library

[21]

McDiarmid, C. 1998. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds. Springer, 195--247.

[22]

Nielsen, J. B. 2002. A threshold pseudorandom function construction and its applications. In Proceedings of the 22nd International Cryptology Conference (CRYPTO). 401--416.

Digital Library

[23]

Ostrovsky, R., Rajagoplan, S., and Vazirani, U. 1994. Simple and efficient leader election in the full information model. In Proceedings of the 26th ACM Symposium on Theory of Computing. 234--242.

Digital Library

[24]

Pease, M. C., Shostak, R. E., and Lamport, L. 1980. Reaching agreement in the presence of faults. J. ACM 27, 2, 228--234.

Digital Library

[25]

Russell, A. and Zuckerman, D. 1998. Perfect information leader election in log^&ast; n + o(1) rounds. In Proceedings of the 39th IEEE Symposium on Foundations of Computer Science. 576--583.

Digital Library

[26]

Saks, M. 1989. A robust noncryptographic protocol for collective coin flipping. SIAM J. Discr. Math. 2, 2, 240--244.

Digital Library

[27]

Toueg, S. 1984. Randomized byzantine agreements. In Proceedings of the 3rd ACM Symposium on Principles of Distributed Computing. 163--178.

Digital Library

[28]

Turpin, R. and Coan, B. A. 1984. Extending binary byzantine agreement to multivalued byzantine agreement. Inform. Process. Lett. 18, 2, 73--76.

[29]

Zuckerman, D. 1997. Randomness-optimal oblivious sampling. Random Struct. Algor. 11, 4, 345--367.

Digital Library

Cited By

Huang SPettie SZhu L(2024)Byzantine Agreement with Optimal Resilience via Statistical Fraud DetectionJournal of the ACM10.1145/363945471:2(1-37)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3639454
Ouaili L(2024)Byzantine and Honest Nodes Distribution in Random Partitions Under an Adaptive AdversarySN Computer Science10.1007/s42979-024-03405-z5:8Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1007/s42979-024-03405-z
Kumar MMolla A(2023)On the Message Complexity of Fault-Tolerant Computation: Leader Election and AgreementIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.3239993(1-12)Online publication date: 2023
https://doi.org/10.1109/TPDS.2023.3239993
Show More Cited By

Index Terms

Fast asynchronous Byzantine agreement and leader election with full information

Recommendations

Simple and efficient asynchronous byzantine agreement with optimal resilience
PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary A_t with unbounded computing power actively controls at most t = ([n/3] − 1) out of n parties in Byzantine ...
Asynchronous Byzantine Agreement with optimal resilience

We present an efficient, optimally-resilient Asynchronous Byzantine Agreement (ABA) protocol involving $$n = 3t+1$$n=3t+1 parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, capable of corrupting ...
Almost-Surely Terminating Asynchronous Byzantine Agreement Revisited
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

The problem of Byzantine Agreement (BA) is of interest to both distributed computing and cryptography community. Following well-known results from the distributed computing literature, BA problem in the asynchronous network setting encounters inevitable ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 6, Issue 4

August 2010

308 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1824777

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 September 2010

Accepted: 01 January 2010

Received: 01 December 2009

Published in TALG Volume 6, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
679
Total Downloads

Downloads (Last 12 months)39
Downloads (Last 6 weeks)11

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang SPettie SZhu L(2024)Byzantine Agreement with Optimal Resilience via Statistical Fraud DetectionJournal of the ACM10.1145/363945471:2(1-37)Online publication date: 12-Apr-2024
https://dl.acm.org/doi/10.1145/3639454
Ouaili L(2024)Byzantine and Honest Nodes Distribution in Random Partitions Under an Adaptive AdversarySN Computer Science10.1007/s42979-024-03405-z5:8Online publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1007/s42979-024-03405-z
Kumar MMolla A(2023)On the Message Complexity of Fault-Tolerant Computation: Leader Election and AgreementIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.3239993(1-12)Online publication date: 2023
https://doi.org/10.1109/TPDS.2023.3239993
Liu KJourenko MLarangeira M(2023)Reducing Latency of DAG-based Consensus in the Asynchronous Setting via the UTXO Model2023 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SocialCom-SustainCom59178.2023.00071(294-304)Online publication date: 21-Dec-2023
https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom59178.2023.00071
Huang SPettie SZhu LLeonardi SGupta A(2022)Byzantine agreement in polynomial time with near-optimal resilienceProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520015(502-514)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520015
Augustine JChatterjee SPandurangan GAgrawal KLee I(2022)A Fully-Distributed Scalable Peer-to-Peer Protocol for Byzantine-Resilient Distributed Hash TablesProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538588(87-98)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538588
Keidar IKokoris-Kogias ENaor OSpiegelman AMiller ACensor-Hillel K(2021)All You Need is DAGProceedings of the 2021 ACM Symposium on Principles of Distributed Computing10.1145/3465084.3467905(165-175)Online publication date: 21-Jul-2021
https://dl.acm.org/doi/10.1145/3465084.3467905
Ahuja A(2021)TensorFIip: A Fast Fully-Decentralized Computational Lottery for Cryptocurrency Networks2021 International Conference on COMmunication Systems & NETworkS (COMSNETS)10.1109/COMSNETS51098.2021.9352857(246-253)Online publication date: 5-Jan-2021
https://doi.org/10.1109/COMSNETS51098.2021.9352857
Delbruel SSmall NAras EOostvogels JHughes DValois FJulien CMurphy AGnawali O(2020)Tackling Contention Through Cooperation: A Distributed Federation in LoRaWAN SpaceProceedings of the 2020 International Conference on Embedded Wireless Systems and Networks10.5555/3400306.3400309(13-24)Online publication date: 17-Feb-2020
https://dl.acm.org/doi/10.5555/3400306.3400309
Chan TPass RShi E(2020)Sublinear-Round Byzantine Agreement Under Corrupt MajorityPublic-Key Cryptography – PKC 202010.1007/978-3-030-45388-6_9(246-265)Online publication date: 4-May-2020
https://dl.acm.org/doi/10.1007/978-3-030-45388-6_9
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents