research-article

Fast asynchronous byzantine agreement and leader election with full information

Authors:

Vishal SanwalaniAuthors Info & Claims

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 1038 - 1047

Published: 20 January 2008 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 non-adaptive 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 n/6+ε 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 paper is a new approach for emulating Feige's lightest bin protocol, even with adversarial message scheduling.

References

[1]

Miklós Ajtai and Nathan Linial. The influence of large coalitions. Combinatorica, 13(2):129--145, 1993.

[2]

Hagit Attiya. Personal communication, 2007.

[3]

Ziv Bar-Joseph and Michael Ben-Or. A tight lower bound for randomized synchronous consensus. In Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 193--199, 1998.

Digital Library

[4]

Michael Ben-Or. Another advantage of free choice: Completely asynchronous agreement prototols. In Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 27--30, 1983.

Digital Library

[5]

Michael Ben-Or and Nathan Linial. Collective coin flipping. In Silvio Micali, editor, Advances in Computing Research 5: Randomness and Computation, pages 91--115. JAI Press, 1989.

[6]

Michael Ben-Or, Elan Pavlov, and Vinod Vaikuntanathan. Byzantine agreement in the full-information model in O(log n) rounds. In Proceedings of the 38th Annual ACM Symposium on Theory of Computin (STOC), pages 179--186, 2006.

Digital Library

[7]

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

[8]

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

Digital Library

[9]

Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography. J. Cryptology, 18(3):219--246, 2005.

[10]

Ran Canetti and Tal Rabin. Fast asynchronous byzantine agreement with optimal resilience. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 42--51, 1993.

Digital Library

[11]

Benny Chor and Cynthia Dwork. Randomization in Byzantine agreement. In Silvio Micali, editor, Advances in Computing Research 5: Randomness and Computation, pages 443--497. JAI Press, 1989.

[12]

Benny Chor, Michael Merritt, and David B. Shmoys. Simple constant-time consensus protocols in realistic failure models. J. ACM, 36(3):591--614, 1989.

Digital Library

[13]

Uriel Feige. Noncryptographic selection protocols. In Proceedings of 40th IEEE Symposium on Foundations of Computer Science (FOCS), pages 142--153, 1999.

Digital Library

[14]

Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. In Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database System (PODS), pages 1--7, 1983.

Digital Library

[15]

Shafi Goldwasser, Elan Pavlov, and Vinod Vaikuntanathan. Fault-tolerant distributed computing in full-information networks. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 15--26, 2006.

Digital Library

[16]

Ronen Gradwohl, Salil P. Vadhan, and David Zuckerman. Random selection with an adversarial majority. In Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, volume 4117 of Lecture Notes in Computer Science, pages 409--426. Springer, 2006.

Digital Library

[17]

Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Scalable leader election. In Proceedings of 27th ACM-SIAM Symposium on Discrete Algorithms(SODA), pages 990--999, 2006.

Digital Library

[18]

Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Towards secure and scalable computation in peer-to-peer networks. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 87--98, 2006.

Digital Library

[19]

Jesper Buus Nielsen. A threshold pseudorandom function construction and its applications. In Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings, volume 2442 of Lecture Notes in Computer Science, pages 401--416. Springer, 2002.

Digital Library

[20]

R. Ostrovsky, S. Rajagoplan, and U. Vazirani. Simple and efficient leader election in the full information model. In Proceedings of the Twenty-Sixth Annual ACM Syposium on Theory of Computing (STOC), pages 234--242, 1994.

Digital Library

[21]

A. Russell and D. Zuckerman. Perfect information leader election in log*n + O(1) rounds. In Proceedings of 39th Annual Symposium on Foundations of Computer Science(FOCS), 1998.

Digital Library

[22]

Michael Saks. A robust noncryptographic protocol for collective coin flipping. SIAM Journal of Discrete Mathematics, pages 240--244, 1989.

Digital Library

[23]

Sam Toueg. Randomized byzantine agreements. In Proceedings of the Third Annual ACM Symposium on Princiles of Distributed Computing (PODC), pages 163--178, 1984.

Digital Library

[24]

David Zuckerman. Randomness-optimal oblivious sampling. Random Struct. Algorithms, 11(4):345--367, 1997.

Digital Library

[25]

David Zuckerman. Personal communication, 2006.

Cited By

Lewko ALewko M(2015)On the complexity of asynchronous agreement against powerful adversariesDistributed Computing10.1007/s00446-014-0224-528:6(377-389)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s00446-014-0224-5
Lewko ALewko MFatourou PTaubenfeld G(2013)On the complexity of asynchronous agreement against powerful adversariesProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484250(280-289)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484250
Lewko A(2011)The contest between simplicity and efficiency in asynchronous byzantine agreementProceedings of the 25th international conference on Distributed computing10.5555/2075029.2075076(348-362)Online publication date: 20-Sep-2011
https://dl.acm.org/doi/10.5555/2075029.2075076
Show More Cited By

Index Terms

Fast asynchronous byzantine agreement and leader election with full information
1. General and reference
  1. Cross-computing tools and techniques
    1. Performance
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Operational analysis
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
    2. Software system structures
      1. Distributed systems organizing principles

Recommendations

Fast asynchronous Byzantine agreement and leader election with full information

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 ...
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 ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

January 2008

1289 pages

Program Chair:
Shang-Hua Teng
Boston University and Akamai Technologies, Inc.

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

Research-article

Conference

SODA08

Sponsor:

SIGACT

SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms

January 20 - 22, 2008

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
278
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lewko ALewko M(2015)On the complexity of asynchronous agreement against powerful adversariesDistributed Computing10.1007/s00446-014-0224-528:6(377-389)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1007/s00446-014-0224-5
Lewko ALewko MFatourou PTaubenfeld G(2013)On the complexity of asynchronous agreement against powerful adversariesProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484250(280-289)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484250
Lewko A(2011)The contest between simplicity and efficiency in asynchronous byzantine agreementProceedings of the 25th international conference on Distributed computing10.5555/2075029.2075076(348-362)Online publication date: 20-Sep-2011
https://dl.acm.org/doi/10.5555/2075029.2075076
King VLonargan SSaia JTrehan A(2011)Load balanced scalable Byzantine agreement through quorum building, with full informationProceedings of the 12th international conference on Distributed computing and networking10.5555/1946143.1946161(203-214)Online publication date: 2-Jan-2011
https://dl.acm.org/doi/10.5555/1946143.1946161
Doerr BGoldberg LMinder LSauerwald TScheideler CMeyer auf der Heide FRajaraman R(2011)Stabilizing consensus with the power of two choicesProceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures10.1145/1989493.1989516(149-158)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1989493.1989516
Alistarh DGilbert SGuerraoui RZadimoghaddam M(2010)How efficient can gossip be? (on the cost of resilient information exchange)Proceedings of the 37th international colloquium conference on Automata, languages and programming: Part II10.5555/1880999.1881012(115-126)Online publication date: 6-Jul-2010
https://dl.acm.org/doi/10.5555/1880999.1881012
Gilbert SKowalski DCharikar M(2010)Distributed agreement with optimal communication complexityProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873679(965-977)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.5555/1873601.1873679
King VSaia J(2010)Scalable byzantine computationACM SIGACT News10.1145/1855118.185513641:3(89-104)Online publication date: 3-Sep-2010
https://dl.acm.org/doi/10.1145/1855118.1855136
Molina ASalajegheh MFu KCamp LFerrari E(2009)HICCUPSProceedings of the first ACM workshop on Security and privacy in medical and home-care systems10.1145/1655084.1655089(21-30)Online publication date: 13-Nov-2009
https://dl.acm.org/doi/10.1145/1655084.1655089
King VSaia JTirthapura SAlvisi L(2009)Brief announcementProceedings of the 28th ACM symposium on Principles of distributed computing10.1145/1582716.1582778(304-305)Online publication date: 10-Aug-2009
https://dl.acm.org/doi/10.1145/1582716.1582778
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten