research-article

Open access

State machine replication scalability made simple

Authors:

Chrysoula Stathakopoulou,

Matej Pavlovic,

Marko VukolićAuthors Info & Claims

EuroSys '22: Proceedings of the Seventeenth European Conference on Computer Systems

Pages 17 - 33

https://doi.org/10.1145/3492321.3519579

Published: 28 March 2022 Publication History

Abstract

Consensus, state machine replication (SMR) and total order broadcast (TOB) protocols are notorious for being poorly scalable with the number of participating nodes. Despite the recent race to reduce overall message complexity of leader-driven SMR/TOB protocols, scalability remains poor and the throughput is typically inversely proportional to the number of nodes. We present Insanely Scalable State Machine Replication, a generic construction to turn leader-driven protocols into scalable multi-leader ones. For our scalable SMR construction we use a novel primitive called Sequenced (Total Order) Broadcast (SB) which we wrap around PBFT, HotStuff and Raft leader-driven protocols to make them scale. Our construction is general enough to accommodate most leader-driven ordering protocols (BFT or CFT) and make them scale. Our implementation improves the peak throughput of PBFT, HotStuff, and Raft by 37x, 56x, and 55x, respectively, at a scale of 128 nodes.

References

[1]

Cosmos: A network of distributed ledgers. https://github.com/dedis/kyber. Accessed: 30.05.2021.

[2]

Bitcoin visuals: Transaction sizes. https://bitcoinvisuals.com/chaintx-size, 2019.

[3]

Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin, Konstantinos Christidis, Angelo De Caro, David Enyeart, Christopher Ferris, Gennady Laventman, Yacov Manevich, Srinivasan Muralidharan, Chet Murthy, Binh Nguyen, Manish Sethi, Gari Singh, Keith Smith, Alessandro Sorniotti, Chrysoula Stathakopoulou, Marko Vukolic, Sharon Weed Cocco, and Jason Yellick. Hyperledger fabric: a distributed operating system for permissioned blockchains. In Proceedings of the Thirteenth EuroSys Conference, EuroSys 2018, Porto, Portugal, April 23--26, 2018, pages 30:1--30:15, 2018.

Digital Library

[4]

Karolos Antoniadis, Rachid Guerraoui, Dahlia Malkhi, and Dragos-Adrian Seredinschi. State machine replication is more expensive than consensus. Technical report, 2018.

[5]

Pierre-Louis Aublin, Sonia Ben Mokhtar, and Vivien Quéma. RBFT: redundant Byzantine fault tolerance. In IEEE 33rd International Conference on Distributed Computing Systems, ICDCS 2013, 8--11 July, 2013, Philadelphia, Pennsylvania, USA, pages 297--306, 2013.

Digital Library

[6]

Zeta Avarikioti, Lioba Heimbach, Roland Schmid, and Roger Wattenhofer. Fnf-bft: Exploring performance limits of BFT protocols. CoRR, abs/2009.02235, 2020.

[7]

Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. In International conference on the theory and application of cryptology and information security, pages 514--532. Springer, 2001.

Digital Library

[8]

C. Cachin, R. Guerraoui, and L. Rodrigues. Introduction to reliable and secure distributed programming. Springer-Verlag New York Inc, 2010.

[9]

M. Castro and B. Liskov. Practical byzantine fault tolerance. Operating Systems Review, 33:173--186, 1998.

Digital Library

[10]

Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance and proactive recovery. ACM Trans. Comput. Syst., 20(4):398--461, November 2002.

Digital Library

[11]

Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. Making Byzantine fault tolerant systems tolerate Byzantine faults. In NSDI, 2009.

Digital Library

[12]

Tyler Crain, Vincent Gramoli, Mikel Larrea, and Michel Raynal. Dbft: Efficient leaderless byzantine consensus and its application to blockchains. In 2018 IEEE 17th International Symposium on Network Computing and Applications (NCA), pages 1--8. IEEE, 2018.

[13]

Tyler Crain, Christopher Natoli, and Vincent Gramoli. Evaluating the Red Belly blockchain. CoRR, abs/1812.11747, 2018.

[14]

Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for Byzantine agreement. J. ACM, 1985.

Digital Library

[15]

Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. J. ACM, 35(2):288--323, April 1988.

Digital Library

[16]

Michael Eischer and Tobias Distler. Scalable byzantine fault-tolerant state-machine replication on heterogeneous servers. Computing, 101(2):97--118, 2019.

Digital Library

[17]

Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling Byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, pages 51--68. ACM, 2017.

Digital Library

[18]

Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. SBFT: A scalable and decentralized trust infrastructure. In 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2019, Portland, OR, USA, June 24--27, 2019, pages 568--580, 2019.

[19]

Rachid Guerraoui, Nikola Knezevic, Vivien Quema, and Marko Vukolic. The Next 700 BFT Protocols. In Proceedings of the ACM European conference on Computer systems (EuroSys), 2010.

Digital Library

[20]

Suyash Gupta, Jelle Hellings, and Mohammad Sadoghi. RCC: resilient concurrent consensus for high-throughput secure transaction processing. In 37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19--22, 2021, pages 1392--1403. IEEE, 2021.

[21]

Kadir Korkmaz, Joachim Bruneau-Queyreix, Sonia Ben Mokthar, and Laurent Réveillère. Dandelion: multiplexing byzantine agreements to unlock blockchain performance. arXiv preprint arXiv:2104.15063, 2021.

[22]

Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: speculative Byzantine fault tolerance. In Proceedings of the Symposium on Operating Systems Principles (SOSP). ACM, 2007.

[23]

L. Baird. The Swirlds Hashgraph consensus algorithm: Fair, fast, Byzantine fault tolerance. https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf, 2016.

[24]

Leslie Lamport. Paxos made simple. ACM SIGACT News, 32(4):18--25, 2001.

[25]

Dahlia Malkhi and Michael Reiter. Unreliable intrusion detection in distributed computations. In Proceedings 10th Computer Security Foundations Workshop, pages 116--124. IEEE, 1997.

[26]

Yanhua Mao, Flavio P. Junqueira, and Keith Marzullo. Mencius: Building efficient replicated state machines for wans. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI'08, pages 369--384, Berkeley, CA, USA, 2008. USENIX Association.

[27]

Zarko Milosevic, Martin Biely, and André Schiper. Bounded delay in byzantine-tolerant state machine replication. In IEEE 32nd Symposium on Reliable Distributed Systems, SRDS, 2013.

Digital Library

[28]

Diego Ongaro and John K. Ousterhout. In search of an understandable consensus algorithm. In Proc. USENIX Annual Technical Conference, pages 305--319, 2014.

Digital Library

[29]

HariGovind V. Ramasamy and Christian Cachin. Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast. In James H. Anderson, Giuseppe Prencipe, and Roger Wattenhofer, editors, Principles of Distributed Systems, 9th International Conference, OPODIS 2005, Pisa, Italy, December 12--14, 2005, Revised Selected Papers, volume 3974 of Lecture Notes in Computer Science, pages 88--102. Springer, 2005.

[30]

Michael K. Reiter. A secure group membership protocol. IEEE Trans. Software Eng., 22(1):31--42, 1996.

Digital Library

[31]

Chrysoula Stathakopoulou, Tudor David, Matej Pavlovic, and Marko Vukolić. Mir-bft: High-throughput bft for blockchains. arXiv preprint arXiv:1906.05552, 2019.

[32]

Chrysoula Stathakopoulou, Matej Pavlovic, and Marko Vukolić. State-machine replication scalability made simple (extended version). https://arxiv.org/abs/2203.05681, 2022.

[33]

Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. Hotstuff: BFT consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC, 2019.

Digital Library

Cited By

Antunes DOliveira ABreda AFranco MMoniz HRodrigues RVanbever LZhang I(2024)Alea-BFTProceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation10.5555/3691825.3691844(313-328)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.5555/3691825.3691844
Gao YLi XPeng ZZhang YYu G(2024)NeuChain+: A Sharding Permissioned Blockchain System with Ordering-Free ConsensusApplied Sciences10.3390/app1411489714:11(4897)Online publication date: 5-Jun-2024
https://doi.org/10.3390/app14114897
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
Show More Cited By

Index Terms

State machine replication scalability made simple
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks

Recommendations

Churn Tolerance Algorithm for State Machine Replication
WI-IAT '12: Proceedings of the The 2012 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technology - Volume 02

State machine replication is a general approach for building a Byzantine fault-tolerant (BFT) distributed systems like a grid or a cloud or a data center. Various BFT protocols based on state machine replication have been introduced for modern ...
State Machine Replication Under Changing Network Conditions
Advances in Cryptology – ASIACRYPT 2022
Abstract
Protocols for state machine replication (SMR) are typically designed for synchronous or asynchronous networks, with a lower corruption threshold in the latter case. Recent network-agnostic protocols are secure when run in either a synchronous or ...
From Byzantine Consensus to BFT State Machine Replication: A Latency-Optimal Transformation
EDCC '12: Proceedings of the 2012 Ninth European Dependable Computing Conference

We present a new algorithm for state machine replication that is built around a leader-driven consensus primitive. This algorithm requires only two additional communication steps between replicas and clients if the consensus leader is correct and the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '22: Proceedings of the Seventeenth European Conference on Computer Systems

March 2022

783 pages

ISBN:9781450391627

DOI:10.1145/3492321

General Chair:
Yérom-David Bromberg
University of Rennes 1
,
Program Chairs:
Anne-Marie Kermarrec
EPFL
,
Christos Kozyrakis
Stanford University

Copyright © 2022 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 March 2022

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Conference

EuroSys '22

Sponsor:

SIGOPS

EuroSys '22: Seventeenth European Conference on Computer Systems

April 5 - 8, 2022

Rennes, France

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
2,831
Total Downloads

Downloads (Last 12 months)772
Downloads (Last 6 weeks)78

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Antunes DOliveira ABreda AFranco MMoniz HRodrigues RVanbever LZhang I(2024)Alea-BFTProceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation10.5555/3691825.3691844(313-328)Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.5555/3691825.3691844
Gao YLi XPeng ZZhang YYu G(2024)NeuChain+: A Sharding Permissioned Blockchain System with Ordering-Free ConsensusApplied Sciences10.3390/app1411489714:11(4897)Online publication date: 5-Jun-2024
https://doi.org/10.3390/app14114897
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
von Seck RRezabek FGallenmüller SCarle G(2024)On the Impact of Network Transport Protocols on Leader-Based Consensus CommunicationProceedings of the 6th ACM International Symposium on Blockchain and Secure Critical Infrastructure10.1145/3659463.3660030(1-11)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1145/3659463.3660030
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
Zhang GPan FMao YTijanic SDang’ana MMotepalli SZhang SJacobsen H(2024)Reaching Consensus in the Byzantine Empire: A Comprehensive Review of BFT Consensus AlgorithmsACM Computing Surveys10.1145/363655356:5(1-41)Online publication date: 12-Jan-2024
https://dl.acm.org/doi/10.1145/3636553
Liu XZheng ZWang WXu HXiao FLi K(2024)Towards Cost-Effective and Robust Packaging in Multi-Leader BFT Blockchain SystemsIEEE Transactions on Computers10.1109/TC.2024.339851073:11(2590-2604)Online publication date: Nov-2024
https://doi.org/10.1109/TC.2024.3398510
Kang DRahnama SHellings JSadoghi M(2024)SpotLess: Concurrent Rotational Consensus Made Practical Through Rapid View Synchronization2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00157(1916-1929)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00157
Zhang GPan FTijanic SJacobsen H(2024)PrestigeBFT: Revolutionizing View Changes in BFT Consensus Algorithms with Reputation Mechanisms2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00156(1930-1943)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00156
Tong XYe ZZhang ZJin CZhou A(2024)TELL: Efficient Transaction Execution Protocol Towards Leaderless Consensus2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00154(1902-1915)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00154
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

Figures

Tables

Media

View Table of Conten