Consensus-Agnostic State-Machine Replication
Pages 341 - 353
Abstract
State-machine replication (SMR) is a popular fault-tolerance technique for building highly-available services. Usually, consensus protocols are used to enforce a deterministic service-request ordering among replicas, in order to prevent their state from diverging. Over the last decades, a multitude of consensus protocols have been developed which come with different characteristics but also with different communication and programming models. Our Consensus-Agnostic Replication Toolkit (CART) is a wrapper for consensus protocols that relieves clients from most consensus configuration and support. Besides, it implements a generic client and application interface to support different consensus protocols and configurations, e.g. in cloud deployments. CART has built-in authentication of services based on BLS threshold signatures. It can further prove malicious behaviour of replicas, thus speeding up recovery in case of Byzantine faults. We evaluate the performance overhead of our approach in a real-world WAN deployment for two different consensus protocol implementations using the YCSB benchmark. Our results show that CART is able to reach up to 90% of the throughput achieved by the native consensus protocol with an additional latency overhead of only 10%.
References
[1]
Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson, Michael K. Reiter, and Jay J. Wylie. 2005. Fault-scalable Byzantine fault-tolerant services. In 20th ACM Symp. on Op. Sys. Princ. (SOSP). ACM, 59--74.
[2]
D. F. Aranha, C. P. L. Gouvêa, T. Markmann, R. S. Wahby, and K. Liao. 2022. RELIC is an Efficient LIbrary for Cryptography. https://github.com/relic-toolkit/relic.
[3]
Pierre-Louis Aublin, Rachid Guerraoui, Nikola Knezevic, Vivien Quéma, and Marko Vukolic. 2015. The Next 700 BFT Protocols. ACM Trans. Comp. Sys. 32, 4 (2015), 12:1--12:45.
[4]
Christian Berger and Hans P. Reiser. 2018. WebBFT: Byzantine Fault Tolerance for Resilient Interactive Web Applications. In 18th Int. Conf. on Distr. Appl. & Interop. Sys. (DAIS) (LNCS, Vol. 10853). Springer, 1--17.
[5]
Christian Berger, Hans P. Reiser, and Alysson Bessani. 2021. Making Reads in BFT State Machine Replication Fast, Linearizable, and Live. In 40th Int. Symp. on Rel. Distr. Sys. (SRDS). IEEE, 1--12.
[6]
Alysson Neves Bessani, João Sousa, and Eduardo Adílio Pelinson Alchieri. 2014. State Machine Replication for the Masses with BFT-SMART. In 44th Ann IEEE/IFIP Int. Conf. on Dep. Sys. and Netw. (DSN). IEEE, 355--362.
[7]
Dan Boneh, Ben Lynn, and Hovav Shacham. 2004. Short Signatures from the Weil Pairing. J. Cryptol. 17, 4 (2004), 297--319.
[8]
Miguel Castro and Barbara Liskov. 2002. Practical Byzantine Fault Tolerance and Proactive Recovery. ACM Trans. Comp. Sys. 20, 4 (2002), 398--461.
[9]
Miguel Castro, Rodrigo Rodrigues, and Barbara Liskov. 2003. BASE: Using abstraction to improve fault tolerance. ACM Trans. Comp. Sys. 21, 3 (2003), 236--269.
[10]
Hua Chai and Wenbing Zhao. 2012. Byzantine Fault Tolerance as a Service. Comm. in Comp. & Inform. Sci. 342 (01 2012), 173--179.
[11]
Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking cloud serving systems with YCSB. In 1st ACM Symp. on Cloud Comp. (SoCC). ACM, 143--154.
[12]
James A. Cowling, Daniel S. Myers, Barbara Liskov, Rodrigo Rodrigues, and Liuba Shrira. 2006. HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance. In 7th Symp. on Oper. Sys. Des. & Impl. (OSDI). USENIX, 177--190.
[13]
Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. 1988. Consensus in the presence of partial synchrony. J. ACM 35, 2 (1988), 288--323.
[14]
Michael Eischer and Tobias Distler. 2021. Egalitarian Byzantine Fault Tolerance. In 26th IEEE Pacific Rim Int. Symp. on Dep. Comp (PRDC). IEEE, 1--10.
[15]
Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. 1985. Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32, 2 (1985), 374--382.
[16]
Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. 1999. Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. In Advances in Cryptology - Int. Conf. on the Theory and Appl. of Crypt. Techn. (EUROCRYPT) (LNCS, Vol. 1592). Springer, 295--310.
[17]
Guy Golan-Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019. SBFT: A Scalable and Decentralized Trust Infrastructure. In 49th Annual IEEE/IFIP Int. Conf. on Dep. Sys. and Netw. (DSN). IEEE, 568--580.
[18]
Rachid Guerraoui, Nikola Knezevic, Vivien Quéma, and Marko Vukolic. 2010. The next 700 BFT protocols. In 5th Eur. Conf. on Comp. Sys. (EuroSys). ACM, 363--376.
[19]
Prashant Gupta, Arumugam Seetharaman, and John Rudolph Raj. 2013. The usage and adoption of cloud computing by small and medium businesses. Int. J. Inf. Manag. 33, 5 (2013), 861--874.
[20]
Franz J. Hauck, Gerhard Habiger, and Jörg Domaschka. 2016. UDS: A Novel and Flexible Scheduling Algorithm for Deterministic Multithreading. In 35th IEEE Symp. on Rel. Distr. Sys. (SRDS). IEEE, 177--186.
[21]
Peter H. Hochschild, Paul Turner, Jeffrey C. Mogul, Rama Govindaraju, Parthasarathy Ranganathan, David E. Culler, and Amin Vahdat. 2021. Cores That Don't Count. In Workshop on Hot Topics in Oper. Sys. (HotOS). ACM, New York, NY, USA, 9--16.
[22]
Neal Koblitz and Alfred Menezes. 2005. Pairing-Based Cryptography at High Security Levels. In Cryptography and Coding, 10th IMA Int. Conf., Cirencester, UK, December 19--21 (LNCS, Vol. 3796). Springer, 13--36.
[23]
Ramakrishna Kotla, Lorenzo Alvisi, Michael Dahlin, Allen Clement, and Edmund L. Wong. 2009. Zyzzyva: Speculative Byzantine fault tolerance. ACM Trans. Comp. Sys. 27, 4 (2009), 7:1--7:39.
[24]
Leslie Lamport. 2002. Paxos Made Simple, Fast, and Byzantine. In 6th Int. Conf. on Princ. of Distr. Sys. (OPODIS), Vol. 3. Suger, Saint-Denis, rue Catulienne, France, 7--9.
[25]
Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. 1982. The Byzantine Generals Problem. ACM Trans. Program. Lang. Sys. 4, 3 (1982), 382--401.
[26]
Odorico Machado Mendizabal, Ruda S. T. De Moura, Fernando Luís Dotti, and Fernando Pedone. 2017. Efficient and Deterministic Scheduling for Parallel State Machine Replication. In Int. Par. & Distr. Proc. Symp. (IPDPS). IEEE, 748--757.
[27]
M.G. Merideth, Arun Iyengar, T. Mikalsen, S. Tai, I. Rouvellou, and P. Narasimhan. 2005. Thema: Byzantine-fault-tolerant middleware for Web-service applications. In 24th Symp. on Rel. Distr. Sys. (SRDS). IEEE, 131--140.
[28]
Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. 2016. The Honey Badger of BFT Protocols. In Conf. on Comp. & Comm. Sec. (CCS). ACM, 31--42.
[29]
Sajeeva L. Pallemulle, Haraldur D. Thorvaldsson, and Kenneth J. Goldman. 2008. Byzantine Fault-Tolerant Web Services for n-Tier and Service Oriented Architectures. In 28th Int. Conf. on Distr. Comp. Sys. (ICDCS). IEEE, 260--268.
[30]
Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. 1980. Reaching Agreement in the Presence of Faults. J. ACM 27, 2 (1980), 228--234.
[31]
Ariana Polyviou and Nancy Pouloudi. 2015. Understanding Cloud Adoption Decisions in the Public Sector. In 48th Hawaii Int. Conf. on Sys. Sci. (HICSS). IEEE, 2085--2094.
[32]
Aarthi Raghavan, Mehmet Akif Demircioglu, and Araz Taeihagh. 2021. Public Health Innovation through Cloud Adoption: A Comparative Analysis of Drivers and Barriers in Japan, South Korea, and Singapore. Int. J. of Env. Res. & Public Health 18, 1 (2021).
[33]
Hans P. Reiser, Jörg Domaschka, Franz J. Hauck, Rüdiger Kapitza, and Wolfgang Schröder-Preikschat. 2006. Consistent Replication of Multithreaded Distributed Objects. In 25th Symp. on Rel. Distr. Sys. (SRDS). IEEE, 257--266.
[34]
Signe Rüsch, Kai Bleeke, and Rüdiger Kapitza. 2019. Themis: An Efficient and Memory-Safe BFT Framework in Rust: Research Statement. In 3rd Workshop on Scal. & Res. Infrastr. f. Distr. Ledgers (SERIAL). ACM, New York, NY, USA, 9--10.
[35]
Fred B. Schneider. 1990. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Comp. Surv. 22, 4 (1990), 299--319.
[36]
Nicola Sfondrini, Gianmario Motta, and Antonella Longo. 2018. Public Cloud Adoption in Multinational Companies: A Survey. In Int. Conf. on Services Comp. (SCC). IEEE, 177--184.
[37]
Asma A. Shaikh. 2016. Attacks on cloud computing and its countermeasures. In Int. Conf. on Sign. Proc., Comm., Power & Embed. Sys. (SCOPES). 748--752.
[38]
Atul Singh, Tathagata Das, Petros Maniatis, Peter Druschel, and Timothy Roscoe. 2008. BFT Protocols Under Fire. In 5th USENIX Symp. on Netw. Sys. Des. & Impl. (NSDI). USENIX Assoc., 189--204.
[39]
João Sousa and Alysson Neves Bessani. 2012. From Byzantine Consensus to BFT State Machine Replication: A Latency-Optimal Transformation. In 9th Eur. Dep. Comp. Conf. (EDCC). IEEE, 37--48.
[40]
Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In Symp. on Princ. of Distr. Comp. (PODC). ACM, 347--356.
[41]
Wenbing Zhao. 2009. Design and implementation of a Byzantine fault tolerance framework for Web services. J. Sys. Softw. 82, 6 (2009), 1004--1015.
Index Terms
- Consensus-Agnostic State-Machine Replication
Index terms have been assigned to the content through auto-classification.
Recommendations
High performance state-machine replication
DSN '11: Proceedings of the 2011 IEEE/IFIP 41st International Conference on Dependable Systems&NetworksState-machine replication is a well-established approach to fault tolerance. The idea is to replicate a service on multiple servers so that it remains available despite the failure of one or more servers. From a performance perspective, state-machine ...
From Byzantine Consensus to BFT State Machine Replication: A Latency-Optimal Transformation
EDCC '12: Proceedings of the 2012 Ninth European Dependable Computing ConferenceWe 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 ...
Resilient State Machine Replication
PRDC '05: Proceedings of the 11th Pacific Rim International Symposium on Dependable ComputingNowadays, one of the major concerns about the services provided over the Internet is related to their availability. Replication is a well known way to increase the availability of a service. However, replication has some associated costs, namely it is ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2024
515 pages
ISBN:9798400706233
DOI:10.1145/3652892
- Chair:
- Jiannong Cao,
- Program Chair:
- Zhi Jin,
- Program Co-chair:
- Valerio Schiavoni,
- Workshop Chair:
- Janick Edinger
This work is licensed under a Creative Commons Attribution-ShareAlike International 4.0 License.
In-Cooperation
- IFIP
- Usenix
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 02 December 2024
Check for updates
Badges
Qualifiers
- Research-article
Conference
Middleware '24
Acceptance Rates
Overall Acceptance Rate 203 of 948 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 59Total Downloads
- Downloads (Last 12 months)59
- Downloads (Last 6 weeks)59
Reflects downloads up to 04 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in