Article

Free access

Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols

Author:

Michael Ben-OrAuthors Info & Claims

PODC '83: Proceedings of the second annual ACM symposium on Principles of distributed computing

Pages 27 - 30

https://doi.org/10.1145/800221.806707

Published: 17 August 1983 Publication History

PDF eReader

Abstract

Recently, Fischer, Lynch and Paterson [3] proved that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We exhibit here a probabilistic solution for this problem, which guarantees that as long as a majority of the processes continues to operate, a decision will be made (Theorem 1). Our solution is completely asynchronous and is rather strong: As in [4], it is guaranteed to work with probability 1 even against an adversary scheduler who knows all about the system.

References

[1]

Dolev, D. and Strong, R. Polynomial Algorithms for Byzantine Agreement. Proc. 14th ACM Symp. on Theory of Computing (1982), 401-407.

Digital Library

Google Scholar

[2]

Fischer, M. and Lynch, N. A Lower Bound for the Time to Assure Interactive Consistency. Information Processing Letters 14, 4 (1982), 182-186.

Crossref

Google Scholar

[3]

Fischer, M., Lynch, N. and Paterson, M. Impossibility of Distributed Consensus With One Faulty Process. MIT/LCS/TR-282.

Digital Library

Google Scholar

[4]

Lehman, D. and Rabin, M. On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. to appear.

Google Scholar

Cited By

View all

Hao RDing CDai XFan HXiang J(2025)High-performance BFT consensus for Metaverse through block linking and shortcut loopComputer Communications10.1016/j.comcom.2024.107990229(107990)Online publication date: Jan-2025
https://doi.org/10.1016/j.comcom.2024.107990
Dong HLiu S(2024)Asynchronous Consensus Quorum Read: Pioneering Read Optimization for Asynchronous Consensus ProtocolsElectronics10.3390/electronics1303048113:3(481)Online publication date: 23-Jan-2024
https://doi.org/10.3390/electronics13030481
Song AZhou C(2024)FlexBFT: A Flexible and Effective Optimistic Asynchronous BFT ProtocolApplied Sciences10.3390/app1404146114:4(1461)Online publication date: 10-Feb-2024
https://doi.org/10.3390/app14041461
Show More Cited By

Index Terms

Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials
2. Theory of computation
  1. Models of computation
    1. Probabilistic computation

Recommendations

Perfectly-Secure Asynchronous MPC for General Adversaries (Extended Abstract)
Progress in Cryptology – INDOCRYPT 2020
Abstract
We study perfectly-secure Multiparty Computation (MPC) in the asynchronous communication setting, tolerating a generalized non-threshold adversary, characterized by an adversary structure. Ashwin Kumar et al. (ACISP2002) presented a condition ...
High Throughput Secure MPC over Small Population in Hybrid Networks (Extended Abstract)
Progress in Cryptology – INDOCRYPT 2020
Abstract
We study secure multi-party computation (MPC) among small number of parties, in partially synchronous and completely asynchronous settings. Prior works have only considered the synchronous setting. The setting considered in this paper is that of $n =...$
The Resiliency of MPC with Low Interaction: The Benefit of Making Errors (Extended Abstract)
Theory of Cryptography
Abstract
We study information-theoretic secure multiparty protocols that achieve full security, including guaranteed output delivery, at the presence of an active adversary that corrupts a constant fraction of the parties. It is known that 2 rounds are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '83: Proceedings of the second annual ACM symposium on Principles of distributed computing

August 1983

305 pages

ISBN:0897911105

DOI:10.1145/800221

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: 17 August 1983

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

450
Total Citations
View Citations
4,879
Total Downloads

Downloads (Last 12 months)576
Downloads (Last 6 weeks)80

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hao RDing CDai XFan HXiang J(2025)High-performance BFT consensus for Metaverse through block linking and shortcut loopComputer Communications10.1016/j.comcom.2024.107990229(107990)Online publication date: Jan-2025
https://doi.org/10.1016/j.comcom.2024.107990
Dong HLiu S(2024)Asynchronous Consensus Quorum Read: Pioneering Read Optimization for Asynchronous Consensus ProtocolsElectronics10.3390/electronics1303048113:3(481)Online publication date: 23-Jan-2024
https://doi.org/10.3390/electronics13030481
Song AZhou C(2024)FlexBFT: A Flexible and Effective Optimistic Asynchronous BFT ProtocolApplied Sciences10.3390/app1404146114:4(1461)Online publication date: 10-Feb-2024
https://doi.org/10.3390/app14041461
Zarnstorff JLebow LSiems CRemuck DRuiz CTseng L(2024)Racos: Improving Erasure Coding State Machine Replication using Leaderless ConsensusProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698511(600-617)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698511
Mostefaoui APerrin MWeibel JKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Randomized Consensus: Common Coins Are not the Holy Grail!Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662824(36-39)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662824
Das SDuan SLiu SMomose ARen LShoup VLuo BLiao XXu JKirda ELie D(2024)Asynchronous Consensus without Trusted Setup or Public-Key CryptographyProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670327(3242-3256)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670327
Garay JKiayias ALeonardos N(2024)The Bitcoin Backbone Protocol: Analysis and ApplicationsJournal of the ACM10.1145/365344571:4(1-49)Online publication date: 18-Apr-2024
https://dl.acm.org/doi/10.1145/3653445
Vonlanthen YSliwinski JAlbarello MWattenhofer RSchiavoni VEdinger JCao JJin Z(2024)Banyan: Fast Rotating Leader BFTProceedings of the 25th International Middleware Conference10.1145/3652892.3700788(494-507)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3652892.3700788
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
Giuliari GSonnino AFrei MStreun FKokoris-Kogias LPerrig AQuek TGao DZhou JCardenas A(2024)An Empirical Study of Consensus Protocols’ DoS ResilienceProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3656997(1345-1360)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3656997
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Perfectly-Secure Asynchronous MPC for General Adversaries (Extended Abstract)

High Throughput Secure MPC over Small Population in Hybrid Networks (Extended Abstract)

The Resiliency of MPC with Low Interaction: The Benefit of Making Errors (Extended Abstract)