Article

Free access

Randomized Byzantine Agreements

Author:

Sam TouegAuthors Info & Claims

PODC '84: Proceedings of the third annual ACM symposium on Principles of distributed computing

Pages 163 - 178

https://doi.org/10.1145/800222.806744

Published: 02 June 2019 Publication History

Abstract

Randomized algorithms for reaching Byzantine Agreement were recently proposed in [Rabi83]. With these algorithms, agreement is reached within an expected number of phases that is a small constant independent of the number of processes n and the number of faulty processes t. The algorithms in [Rabi83] tolerate up to [(n-1)/10] faulty processes in asynchronous systems, and up to [(n-1)/4] faulty processes in synchronous systems. In this paper, using the same computation model as in [Rabi83], we describe algorithms that overcome up to [(n-1)/3] faulty processes in asynchronous systems, and up to [(n-1)/2] faulty processes in synchronous systems. With both proposed algorithms, agreement is reached within an expected number of phases that is a small constant independent of n and t, but the communication complexity is higher than in [Rabi83]. It is also shown that no Byzantine Agreement algorithm can overcome more than [(n-1)/3] faulty processes in asynchronous authenticated systems, and hence the asynchronous algorithm proposed here is optimal in this respect.

References

[1]

M. Ben-Or, Another advantage of free choice: Completely asynchronous agreement protocols, Proc. 2nd Symposium on the Principles of Distributed Computing, Montreal, Canada, pp. 27-30, Aug. 1983.

Digital Library

[2]

G. Bracha and S. Toueg, Resilient consensus protocols, Proc. 2nd Symposium on the Principles of Distributed Computing, Montreal, Canada, pp. 12-26, Aug. 1983.

Digital Library

[3]

G. Bracha, An asynchronous {(n-1)/3}-resilient consensus protocol, Proc. 3rd Symposium on the Principles of Distributed Computing, Vancouver, Canada, Aug. 1984.

Digital Library

[4]

D. Dolev, Unanimity in an unknown and unreliable environment, Proc. 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, pp. 159-168, Oct. 1981.

Digital Library

[5]

D. Dolev, The Byzantine Generals strike again, Journal of Algorithms, Vol. 3, pp. 14-30, 1982.

[6]

D. Dolev, Polynomial algorithms for multiple processor agreement, Proc. 14th Annual ACM Symposium on Theory of Computing, San Francisco, California, pp. 401-407, May 1982.

Digital Library

[7]

D. Dolev and H. R. Strong, Authenticated algorithms for Byzantine Agreement, SIAM J. Comput., vol. 12, no. 4, pp. 656-666, Nov. 1983.

Digital Library

[8]

M. J. Fischer, N. A. Lynch, and M. S. Paterson, Impossibility of distributed consensus with one faulty process, Proc. 2nd ACM SIGACT-SIGMOD Symposium on Principles of Database systems, Atlanta, Georgia, pp. 1-7, March 1983.

Digital Library

[9]

L. Lamport, R. Shostak, and M. Pease, The Byzantine Generals problem, ACM Transactions on Programming Languages and Systems, vol. 4, no. 3, pp. 382-401, July 1982.

Digital Library

[10]

N. Lynch, M. Fischer, and R. Fowler, A simple and efficient Byzantine Generals algorithm, Proc. Second IEEE Symposium on Reliability in Distributed Software and Data Base Systems, Pittsburgh, Pennsylvania, pp. 46-52, 1982.

[11]

M. Pease, R. Shostak and L. Lamport, Reaching agreement in the presence of faults, Journal of the ACM, vol. 27, no. 2, pp. 228-234, April 1980.

Digital Library

[12]

K. J. Perry, Randomized Byzantine Agreement, Technical Report TR 84-595, Cornell University, March 1984.

Digital Library

[13]

K. J. Perry and S. Toueg, An authenticated Byzantine Generals algorithm with early stopping, Technical Report, Cornell University, June 1984.

[14]

M. Rabin, Randomized Byzantine generals, Proc. 24th Symposium on Foundations of Computer Science, Tucson, Arizona, pp. 403-409, Nov. 1983.

[15]

A. Shamir, How to share a secret Comm. of the ACM, vol. 22, no. 11, pp. 612-613, Nov. 1979.

Digital Library

[16]

T. K. Srikanth and S. Toueg, Byzantine Agreement made simple: Simulating authentication without signatures, Technical Report in preparation.

[17]

R. Turpin and B. C. Coan, Extenting binary Byzantine Agreement to multivalued Byzantine Agreement, Information Processing Letters, Vol. 18, pp. 73-76, Feb. 1984.

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
Duvignau RRaynal MSchiller E(2024)Self-stabilizing Byzantine Multivalued Consensus: (extended abstract)Proceedings of the 25th International Conference on Distributed Computing and Networking10.1145/3631461.3631540(12-21)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3631461.3631540
Yang GChen CChen QJiang JLi JHe D(2024)Sweeper: Breaking the Validity-Latency Tradeoff in Asynchronous Common SubsetIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.338260219(4534-4546)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3382602
Show More Cited By

Index Terms

Randomized Byzantine Agreements
1. Networks
  1. Network protocols
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems
  2. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

Randomized Asynchronous Byzantine Agreements
A Simple and Efficient Randomized Byzantine Agreement Algorithm

A new randomized Byzantine agreement algorithm is presented. This algorithm operates in a synchronous system of n processors, at most t of which can fail. The algorithm reaches agreement in 0(t/log n) expected rounds and O(n2tf/log n) expected message ...
Randomized Byzantine Agreement

A randomized model of distributed computation was recently presented by Rabin [ 81. This model admits a solution to the Byzantine Agreement Problem for systems of n asynchronous processes where no more than t are faulty. The algorithm described by Rabin ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '84: Proceedings of the third annual ACM symposium on Principles of distributed computing

August 1984

301 pages

ISBN:0897911431

DOI:10.1145/800222

Copyright © 1984 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2019

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

87
Total Citations
View Citations
1,530
Total Downloads

Downloads (Last 12 months)146
Downloads (Last 6 weeks)17

Reflects downloads up to 25 Nov 2024

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
Duvignau RRaynal MSchiller E(2024)Self-stabilizing Byzantine Multivalued Consensus: (extended abstract)Proceedings of the 25th International Conference on Distributed Computing and Networking10.1145/3631461.3631540(12-21)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3631461.3631540
Yang GChen CChen QJiang JLi JHe D(2024)Sweeper: Breaking the Validity-Latency Tradeoff in Asynchronous Common SubsetIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.338260219(4534-4546)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3382602
Zhao LDecouchant JLiu JLu QYu J(2024)Trusted Hardware-Assisted Leaderless Byzantine Fault Tolerance ConsensusIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.335752121:6(5086-5097)Online publication date: Nov-2024
https://doi.org/10.1109/TDSC.2024.3357521
Brodsky MChoudhuri AJain APaneth O(2024)Monotone-Policy Aggregate SignaturesAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58737-5_7(168-195)Online publication date: 28-Apr-2024
https://doi.org/10.1007/978-3-031-58737-5_7
Dai XZhang BJin HRen LMeng WJensen CCremers CKirda E(2023)ParBFT: Faster Asynchronous BFT Consensus with a Parallel Optimistic PathProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623101(504-518)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623101
Othmane MSiam AMoumen H(2023)Minimal synchrony for implementing Timely Provable Reliable Send primitive with Byzantine failuresInternational Journal of Parallel, Emergent and Distributed Systems10.1080/17445760.2023.219999238:4(280-287)Online publication date: 27-Apr-2023
https://doi.org/10.1080/17445760.2023.2199992
Duvignau RRaynal MSchiller E(2023)Self-stabilizing Byzantine fault-tolerant repeated reliable broadcastTheoretical Computer Science10.1016/j.tcs.2023.114070972(114070)Online publication date: Sep-2023
https://doi.org/10.1016/j.tcs.2023.114070
Freitas TSoares JCorreia MMartins R(2023)Deterministic or probabilistic? - A survey on Byzantine fault tolerant state machine replicationComputers and Security10.1016/j.cose.2023.103200129:COnline publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1016/j.cose.2023.103200
Georgiou CRaynal MSchiller E(2023)Self-stabilizing Byzantine-Tolerant RecyclingStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_39(518-535)Online publication date: 30-Sep-2023
https://doi.org/10.1007/978-3-031-44274-2_39
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents