Article

Free access

Byzantine quorum systems

Authors:

Dahlia Malkhi,

Michael ReiterAuthors Info & Claims

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

Pages 569 - 578

https://doi.org/10.1145/258533.258650

Published: 04 May 1997 Publication History

PDF eReader

References

[1]

Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt and N. Shavit. Atomic snapshots of shared memory. Journal of the A CM 40(4):873-890, September 1993.

Digital Library

Google Scholar

[2]

Y. Afek, D. Dolev, lg. Gafni, M. Merritt and N. Shavit. A bounded first-in first-enabled-solution to the/-exclusion problem. In Proceedings of the 4th International Workshop on Distributed Algorithms, LNCS 486, Springer-Verlag, 1990.

Digital Library

Google Scholar

[3]

D. Agrawal and A. El Abbadi. Integrating security with fault-tolerant distributed databases. Computer Journal 33(1 ):71-78, February 1990.

Digital Library

Google Scholar

[4]

D. Agrawal and A. El Abbadi. An efficient and faulttolerant solution for distributed mutual exclusion. A CM Transactions on Computer Systems 9(1):1-20, 1991.

Digital Library

Google Scholar

[5]

J. H. Anderson. Composite registers. Distributed Computing 6(3):141-154, 1993.

Digital Library

Google Scholar

[6]

H. Attiya, A. Bar-Noy and D. Dolev. Sharing Memory Robustly in Message-Passing Systems. Journal of the A CM 42(1):124-142, January 1995.

Digital Library

Google Scholar

[7]

P. A. Bernstein, V. Hadzilacos and N. Goodman. Concurfancy control and recovery in database systems. Addisonwesley, 1981.

Digital Library

Google Scholar

[8]

G. Bracha and S. Toueg. Asynchronous consensus and broadcast protocols. Journal of the A CM 32(4):824-840, October 1985.

Digital Library

Google Scholar

[9]

S. Y. Cheung, M. H. Ammar, and M. Ahamad. The grid protocol: A high performance scheme for maintaining replicared data. In Proceedings of the 6th IEEE International Conference on Data Engineering, pages 438-445, 1990.

Digital Library

Google Scholar

[10]

International Telegraph and Telephone Consultative Committee (CCITT). The Directory- Authentication Framework, Recommendation X.509, 1988.

Google Scholar

[11]

D. Dolev, E. Gafni and N. Shavit. Toward a non-atomic era: /-exclusion as a test case. In Proceedings of the SOth A CM Symposium on Theory of Computing, pages 78-92, May 1988.

Digital Library

Google Scholar

[12]

D. Dolev and N. Shavit. Bounded concurrent time-stamp systems are constructible. SIAM Journal o} Computing, to appear. Also in Proceedings of the 21st A CM Symposium on the Theory of Computing, pages 454-466, 1989.

Digital Library

Google Scholar

[13]

A. El Abbadi and S. Toueg. Maintaining availability in partitioned replicated databases. A CM Transactions on Database Systems 14(2):264-290, June 1989.

Digital Library

Google Scholar

[14]

H. Garcia-Molina and D. Barbara. How to assign votes in a distributed system. Journal of the A CM 32(4):841-860, October 1985.

Digital Library

Google Scholar

[15]

D. K. Gifford. Weighted voting for replicated data. In Proceedings of the 7th A CM Symposium on Operating Systems Principles, pages 150-162, 1979.

Digital Library

Google Scholar

[16]

M. Hall, Jr. Combinatorial Theory. 2nd Ed. Wiley- Interscience Series in Discrete Mathematics, 1986.

Digital Library

Google Scholar

[17]

M. Herlihy. A quorum-consensus replication method for abstract data types. A CM Transactions on Computer Systems 4(1):32-53, February 1986.

Digital Library

Google Scholar

[18]

M. P. Herlihy and J. D. Tygar. How to make replicated data secure. In Advances in Cryptology-- CRYP TO '87 Proceedings (Lecture Notes in Computer Science 293), pages 379- 391, Springer-Verlag, 1988.

Crossref

Google Scholar

[19]

A. Israeli and M. Li. Bounded time-stamps. Distributed Computing 6(4):205-209.

Digital Library

Google Scholar

[20]

A. Kumar. Hierarchical quorum consensus: A new algorithm for managing replicated data. IEEE Transactions on Computers 40(9):996-1004, 1991.

Digital Library

Google Scholar

[21]

A. Israeli and A. Shaham. Optimal multi-write multi-reader atomic register. In Proceedings of the 11th A CM Symposium on Principles of Distributed Computing, pages 71-82, 1992.

Digital Library

Google Scholar

[22]

L. Lamport, R. Shostak and M. Pease. The Byzantine yenerals problem. A CM Transactions on Programming Languages and Systems 4(3):382-401, July 1982.

Digital Library

Google Scholar

[23]

B. Lampson, M. Abadi, M. Burrows, and E. Wobber. Authentication in distributed systems: Theory and practice. A CM Transactions on Computer Systems 10(4):265-310, November 1992.

Digital Library

Google Scholar

[24]

L. Lamport. On interprocess communication (part II: algorithms). Distributed Computing 1:86-101, 1986.

Crossref

Google Scholar

[25]

M. Li, J. Tromp and P. M. B. Vitanyi. How to share concurrent wait-free variables. Journal of the A CM, to appear.

Digital Library

Google Scholar

[26]

M. Maekawa. A ~ algorithm for mutual exclusion in decentralized systems. A CM Transactions on Computer Systems 3(2):145-159, 1985.

Digital Library

Google Scholar

[27]

D. Malkhi and M. Ratter. A high-throughput secure reliable multicast protocol. Journal of Computer Security, to appear. Also in Proceedings of the 9th IEEE Computer Security Foundations Workshop, pages 9-17, June 1996.

Digital Library

Google Scholar

[28]

D. Malkhi, M. Ratter and A. Wool. Optima{ Byzantine quorum systems. Submitted for publication, January 1997.

Google Scholar

[29]

R. Mukkamala. Storage efficient and secure replicated distributed databases. IEEE Transactions on Knowledge and Data Engineering 6(2):337-341, April 1994.

Digital Library

Google Scholar

[30]

M. Nw0r and A. Wool. The load, capacity, and availability of quorum systems. In Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pages 214-225, 1994.

Google Scholar

[31]

M. Naor and A. Wool. Access control and signatures via quorum secret sharing. In Proceedings of the $rd A CM Conference on Computer and Communications Security, pages 157-168, March 1996.

Digital Library

Google Scholar

[32]

M. O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM 36(2):335-348, 1989.

Digital Library

Google Scholar

[33]

M. K. Ratter. Secure agreement protocols: Reliable and atomic group multicast in Rampart. In Proceedings of the,qnd A CM Conference on Computer and Communications Security, pages 68-80, November 1994.

Digital Library

Google Scholar

[34]

M. K. Reiter. Distributing trust with the Rampart toolkit. Communications of the A CM 39(4):71-74, April 1996.

Digital Library

Google Scholar

[35]

R. R/vest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the A CM 21(2):120--126, February 1978.

Digital Library

Google Scholar

[36]

A. Shamir. How to share a secret. Communications of the A CM 22(11):612-613, November 1979.

Digital Library

Google Scholar

[37]

J. J. Tardo and K. Alagappan. SPX: Global authentication using public key certificates. In Proceedings of the 1991 IEEE Symposium on Research in Security and Privacy, pages 232-244, May 1991.

Crossref

Google Scholar

[38]

R. H. Thomas. A majority consensus approach to concurrency control for multiple copy databases. A CM Transactions on Database Systems 4(2):180-209, 1979.

Digital Library

Google Scholar

[39]

S. Toueg. Randomized Byzantine agreement. In Proceedings of the $rd A CM Symposium on Principles of Distributed Computing, pages 163-178, August 1984.

Digital Library

Google Scholar

Cited By

View all

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
Falazi GBreitenbücher ULeymann FSchulte S(2024)Cross-Chain Smart Contract Invocations: A Systematic Multi-Vocal Literature ReviewACM Computing Surveys10.1145/363804556:6(1-38)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3638045
Berger CReiser H(2024)Poster: Optimizing Tree-based Quorum Certification for BFT Systems at Planetary-Scale2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks - Supplemental Volume (DSN-S)10.1109/DSN-S60304.2024.00044(154-156)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN-S60304.2024.00044
Show More Cited By

Index Terms

Byzantine quorum systems
1. Information systems
  1. Data management systems
2. Networks
  1. Network protocols

Recommendations

Synchronous Byzantine quorum systems

Quorum systems have been used to implement many coordination problems in distributed systems such as mutual exclusion, data replication, distributed consensus, and commit protocols. Malkhi and Reiter recently proposed quorum systems that can tolerate ...
Dynamic Byzantine Quorum Systems
DSN '00: Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8)

Byzantine quorum systems enhance the availability and efficiency of fault-tolerant replicated services when servers may suffer Byzantine failures. An important limitation of Byzantine quorum systems is their dependence on a static threshold limit on the ...
Byzantine quorum systems

Quorum systems are well-known tools for ensuring the consistency and availability of replicated data despite the benign failure of data repositories. In this paper we consider the arbitrary (Byzantine) failure of data repositories and present the first ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

May 1997

752 pages

ISBN:0897918886

DOI:10.1145/258533

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: 04 May 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC97

Sponsor:

SIGACT

STOC97: 29th Annual Symposium on Theory of Computing

May 4 - 6, 1997

Texas, El Paso, USA

Acceptance Rates

STOC '97 Paper Acceptance Rate 75 of 211 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

101
Total Citations
View Citations
1,285
Total Downloads

Downloads (Last 12 months)81
Downloads (Last 6 weeks)15

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Falazi GBreitenbücher ULeymann FSchulte S(2024)Cross-Chain Smart Contract Invocations: A Systematic Multi-Vocal Literature ReviewACM Computing Surveys10.1145/363804556:6(1-38)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3638045
Berger CReiser H(2024)Poster: Optimizing Tree-based Quorum Certification for BFT Systems at Planetary-Scale2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks - Supplemental Volume (DSN-S)10.1109/DSN-S60304.2024.00044(154-156)Online publication date: 24-Jun-2024
https://doi.org/10.1109/DSN-S60304.2024.00044
Buser MDowsley REsgin MGritti CKasra Kermanshahi SKuchta VLegrow JLiu JPhan RSakzad ASteinfeld RYu J(2023)A Survey on Exotic Signatures for Post-quantum Blockchain: Challenges and Research DirectionsACM Computing Surveys10.1145/357277155:12(1-32)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1145/3572771
Niu JGai FHan RZhang RZhang YFeng C(2023)Crystal: Enhancing Blockchain Mining Transparency With Quorum CertificateIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2022.321674920:5(4154-4168)Online publication date: 1-Sep-2023
https://doi.org/10.1109/TDSC.2022.3216749
Vassantlal RHeydari HBessani A(2023)On the Minimal Knowledge Required for Solving Stellar Consensus2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00016(682-691)Online publication date: Jul-2023
https://doi.org/10.1109/ICDCS57875.2023.00016
Wang GNixon M(2023)SoK: Essentials of BFT Consensus for Blockchains2023 Fifth International Conference on Blockchain Computing and Applications (BCCA)10.1109/BCCA58897.2023.10338868(315-328)Online publication date: 24-Oct-2023
https://doi.org/10.1109/BCCA58897.2023.10338868
Barbàra FSchifanella C(2023)MP‐HTLC: Enabling blockchain interoperability through a multiparty implementation of the hash time‐lock contractConcurrency and Computation: Practice and Experience10.1002/cpe.765635:9Online publication date: Mar-2023
https://doi.org/10.1002/cpe.7656
Huang MHan RDu ZFu YLiu L(2022)Reputation-based state machine replication2022 IEEE 21st International Symposium on Network Computing and Applications (NCA)10.1109/NCA57778.2022.10013518(225-234)Online publication date: 14-Dec-2022
https://doi.org/10.1109/NCA57778.2022.10013518
Mauri LCimato SDamiani E(2022)Untangling the XRP Ledger: Insights and AnalysisInformation Systems Security and Privacy10.1007/978-3-030-94900-6_3(48-72)Online publication date: 1-Jan-2022
https://doi.org/10.1007/978-3-030-94900-6_3
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

Synchronous Byzantine quorum systems

Dynamic Byzantine Quorum Systems

Byzantine quorum systems