article

Free access

Asynchronous consensus and broadcast protocols

Authors:

Gabriel Bracha,

Sam TouegAuthors Info & Claims

Journal of the ACM (JACM), Volume 32, Issue 4

Pages 824 - 840

https://doi.org/10.1145/4221.214134

Published: 01 October 1985 Publication History

PDF eReader

Abstract

A consensus protocol enables a system of n asynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes that can only die and malicious processes that can also send false messages. The class of asynchronous systems with fair schedulers is defined, and consensus protocols that terminate with probability 1 for these systems are investigated. With fail-stop processes, it is shown that ⌈(n + 1)/2⌉ correct processes are necessary and sufficient to reach agreement. In the malicious case, it is shown that ⌈(2n + 1)/3⌉ correct processes are necessary and sufficient to reach agreement. This is contrasted with an earlier result, stating that there is no consensus protocol for the fail-stop case that always terminates within a bounded number of steps, even if only one process can fail. The possibility of reliable broadcast (Byzantine Agreement) in asynchronous systems is also investigated. Asynchronous Byzantine Agreement is defined, and it is shown that ⌈(2n + 1)/3⌉ correct processes are necessary and sufficient to achieve it.

References

[1]

BEN-OR, M. Another advantage of free choice: Completely asynchronous agreement protocols. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (Montreal, Ont., Canada, Aug.). ACM, New York, 1983, pp. 27-30.

Crossref

Google Scholar

[2]

DOLEV, D. Unanimity in an unknown and unreliable environment. In Proceedings of the 22nd Annual Symposium on Foundations of Computer Science (Nashville, Tenn., Oct.). IEEE, New York, 1981, pp. 159-168.

Google Scholar

[3]

FISCHER, M. J., LYNCH, N. A., AND PATERSON, M. S.Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (Apr. 1985), 374-382.

Crossref

Google Scholar

[4]

ISAACSON, D. L., AND MADSEN, R. W Markov Chains Theory and Practice. Wiley, New York. 1976, pp. 89-100.

Google Scholar

[5]

ITAI, A. AND RODEH, M. Symmetry breaking in distributive networks. In Proceedings of the 22nd Annual Symposium on Foundation of Computer Science (Nashville, Tenn. Oct.), IEEE, New York, 1981, pp. 150-158.

Google Scholar

[6]

LAMPORT, L., SHOSTAK, R., AND PEASE, M.The Byzantine Generals problem. ACM Trans. Prog. Lang. Syst. 4, 3, (July 1982), 382-401.

Crossref

Google Scholar

[7]

PEASE, M., SHOSTAK, R., AND LAMPORT, L.Reaching agreement in the presence of faults. J. ACM 27, 2, (April 1980), 228-234.

Crossref

Google Scholar

[8]

RABIN, M., AND LEHMANN, D. On the advantages of free choice: A symmetric and fully distributed solution to the dining philosophers problem. In Proceedings of the 8th ACM Symposium on the Principles of Programming Languages (Williamsburg, Va. Jan. 26-28). ACM, New York, 1981, pp. 133-138.

Crossref

Google Scholar

[9]

SCHLICHTING, R. D., AND SCHNEIDER, F. B.Fail-stop processes: An approach to designing faulttolerant computing systems. ACM Trans. Comput. Syst. 1, 3 (Aug. 1983), 222-238.

Crossref

Google Scholar

Cited By

View all

Solat S(2025)Parallel Committees: a scalable, secure, and fault-tolerant distributed NoSQL database architectureCluster Computing10.1007/s10586-024-05081-328:4Online publication date: 25-Feb-2025
https://doi.org/10.1007/s10586-024-05081-3
Raynal M(2025)Invited Paper: Distributed Computability: A Few Results Masters Students Should KnowDistributed Computing and Intelligent Technology10.1007/978-3-031-81404-4_3(24-44)Online publication date: 8-Jan-2025
https://dl.acm.org/doi/10.1007/978-3-031-81404-4_3
Malkhi DStathakopoulou CYin M(2025)BBCA-Chain: Low Latency, High Throughput BFT Consensus on a DAGFinancial Cryptography and Data Security10.1007/978-3-031-78676-1_4(51-73)Online publication date: 22-Feb-2025
https://doi.org/10.1007/978-3-031-78676-1_4
Show More Cited By

Index Terms

Asynchronous consensus and broadcast protocols

Recommendations

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

A consensus protocol enables a system of n asynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes can only die, malicious processes can also send false messages. We investigate ...
An Asynchronous [(n-1)/3]-Resilient Consensus Protocols
Necessary and sufficient conditions for broadcast consensus protocols

We consider consensus protocols in asynchronous distributed systems that are based on broadcast communication. We show that a necessary and sufficient condition for the existence of a deterministic consensus protocol is delivery of each broadcast ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 32, Issue 4

Oct. 1985

234 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/4221

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1985

Published in JACM Volume 32, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

376
Total Citations
View Citations
4,053
Total Downloads

Downloads (Last 12 months)670
Downloads (Last 6 weeks)67

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Solat S(2025)Parallel Committees: a scalable, secure, and fault-tolerant distributed NoSQL database architectureCluster Computing10.1007/s10586-024-05081-328:4Online publication date: 25-Feb-2025
https://doi.org/10.1007/s10586-024-05081-3
Raynal M(2025)Invited Paper: Distributed Computability: A Few Results Masters Students Should KnowDistributed Computing and Intelligent Technology10.1007/978-3-031-81404-4_3(24-44)Online publication date: 8-Jan-2025
https://dl.acm.org/doi/10.1007/978-3-031-81404-4_3
Malkhi DStathakopoulou CYin M(2025)BBCA-Chain: Low Latency, High Throughput BFT Consensus on a DAGFinancial Cryptography and Data Security10.1007/978-3-031-78676-1_4(51-73)Online publication date: 22-Feb-2025
https://doi.org/10.1007/978-3-031-78676-1_4
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
Nagda HSinghal SAmiri MLoo B(2024)Rashnu: Data-Dependent Order-FairnessProceedings of the VLDB Endowment10.14778/3665844.366586117:9(2335-2348)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665861
Giridharan NSuri-Payer FAbraham IAlvisi LCrooks NWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)Autobahn: Seamless high speed BFTProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695942(1-23)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695942
Geffner ITennenholtz MKleinberg RSaban DBergemann D(2024)Making a Nash Equilibrium Resilient to CoalitionsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673552(213-238)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3670865.3673552
Tonkikh AFreitas LKuznetsov PGelles ROlivetti D(2024)Swiper: a new paradigm for efficient weighted distributed protocolsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662799(283-294)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662799
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
Wang BLiu SDong HWang XXu WZhang JZhong PZhang Y(2024)Bandle: Asynchronous State Machine Replication Made EfficientProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3650091(265-280)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3650091
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.

Abstract

References

Cited By

Index Terms

Recommendations

Resilient consensus protocols

An Asynchronous [(n-1)/3]-Resilient Consensus Protocols

Necessary and sufficient conditions for broadcast consensus protocols

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations