[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3167132.3167179acmconferencesArticle/Chapter ViewAbstractPublication PagessacConference Proceedingsconference-collections
research-article

Dynamic adaptation of byzantine consensus protocols

Published: 09 April 2018 Publication History

Abstract

The problem of distributed consensus in the presence of Byzantine faults has received particular attention in recent decades. Today a variety of solution to this problem exist, each optimized for particular execution conditions. Given that, in most cases, real systems operate under dynamic conditions, it is important to develop mechanisms that allow the algorithms to be adapted or changed at runtime to optimize the system to the current conditions. The problem of dynamic adaptation of consensus algorithms is not new, but the literature is scarce for the Byzantine case and there is no comprehensive comparison of existing solutions. This work has two complementary objectives. First, it studies how the different dynamic adaptation techniques proposed for the crash failure model can be applied in the presence of Byzantine faults. Second, it presents a comparative study of the performance of these switching algorithms in practice. For that purpose, we have implemented the switching algorithms in a common software framework, based on the open source BFT-SMaRt library. Using this framework we have performed an extensive evaluation that offers useful insights on the practical effects of different mechanisms used to support the run-time switching among Byzantine protocols.

References

[1]
Pierre-Louis Aublin, Rachid Guerraoui, Nikola Knežević, Vivien Quéma, and Marko Vukolić. 2015. The Next 700 BFT Protocols. ACM Trans. Comput. Syst. 32, 4, Article 12 (Jan. 2015), 45 pages.
[2]
Alysson Bessani, João Sousa, and Eduardo E. P. Alchieri. 2014. State Machine Replication for the Masses with BFT-SMaRt. In Proceedings of the 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN '14). Atlanta, Georgia, USA, 355--362.
[3]
Vita Bortnikov, Gregory V. Chockler, Dmitri Perelman, Alexey Roytman, Shlomit Shachor, and Ilya Shnayderman. 2015. Reconfigurable State Machine Replication from Non-Reconfigurable Building Blocks. Arxiv preprint arXiv.1512.08943 (2015).
[4]
C. Carvalho. 2017. Dynamic Adaptation of Byzantine Fault Tolerant Protocols. Master's thesis. Instituto Superior Técnico, Universidade de Lisboa.
[5]
Miguel Castro and Barbara Liskov. 1999. Practical Byzantine Fault Tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI '99). New Orleans, Louisiana, USA, 173--186.
[6]
Wen-Ke Chen, M. A. Hiltunen, and R. D. Schlichting. 2001. Constructing Adaptive Software in Distributed Systems. In Proceedings of the The 21st International Conference on Distributed Computing Systems (ICDCS '01). Phoenix, Arizona, USA, 635--643.
[7]
Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. 2009. Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09). Boston, Massachusetts, 153--168.
[8]
M. Couceiro, P. Ruivo, P. Romano, and L. Rodrigues. 2013. Chasing the optimum in replicated in-memory transactional platforms via protocol adaptation. In Proceedings of the 2013 43th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN '13). Budapest, Hungary, 1--12.
[9]
Alírio Santos de Sá, Allan Edgard Silva Freitas, and Raimundo José de Araújo Macêdo. 2013. Adaptive Request Batching for Byzantine Replication. SIGOPS Oper. Syst. Rev. 47, 1 (Jan. 2013), 35--42.
[10]
Rachid Guerraoui and Luís Rodrigues. 2006. Introduction to Reliable Distributed Programming. Springer-Verlag New York, Inc.
[11]
Jamie Hillman and Ian Warren. 2004. An Open Framework for Dynamic Reconfiguration. In Proceedings of the 26th International Conference on Software Engineering (ICSE '04). Edinburgh, Scotland, UK, 594--603.
[12]
Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. 2007. Zyzzyva: Speculative Byzantine Fault Tolerance. In Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles (SOSP '07). Stevenson, Washington, USA, 45--58.
[13]
L. Lamport, D. Malkhi, and L. Zhou. 2008. Stoppable paxos. Technical Report. Microsoft Research.
[14]
Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. 2010. Reconfiguring a State Machine. SIGACT News 41, 1 (March 2010), 63--73.
[15]
Jean-Philippe Martin and Lorenzo Alvisi. 2006. Fast Byzantine Consensus. IEEE Trans. Dependable Secur. Comput. 3, 3 (July 2006), 202--215.
[16]
José Mocito and Luís Rodrigues. 2006. Run-time Switching Between Total Order Algorithms. In Proceedings of the 12th International Conference on Parallel Processing (Euro-Par'06). Dresden, Germany, 582--591.
[17]
M. Pasadinhas. 2017. Policy-Based Adaptation of Byzantine Fault Tolerant Systems. Master's thesis. Instituto Superior Técnico, Universidade de Lisboa.
[18]
Daniel Porto, João Leitão, Cheng Li, Allen Clement, Aniket Kate, Flavio Junqueira, and Rodrigo Rodrigues. 2015. Visigoth Fault Tolerance. In Proceedings of the Tenth European Conference on Computer Systems (EuroSys '15). Bordeaux, France, Article 8, 14 pages.
[19]
Liliana Rosa, Luís Rodrigues, and Antónia Lopes. 2007. A Framework to Support Multiple Reconfiguration Strategies. In Proceedings of the 1st International Conference on Autonomic Computing and Communication Systems (Autonomics '07). Article 15, 10 pages.
[20]
Fred B. Schneider. 1993. Distributed Systems (2Nd Ed.). ACM Press/Addison-Wesley Publishing Co., Chapter Replication Management Using the State-machine Approach, 169--197.
[21]
Atul Singh, Tathagata Das, Petros Maniatis, Peter Druschel, and Timothy Roscoe. 2008. BFT Protocols Under Fire. In Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation (NSDI'08). San Francisco, California, 189--204.
[22]
João Sousa and Alysson Bessani. 2012. From Byzantine Consensus to BFT State Machine Replication: A Latency-Optimal Transformation. In Proceedings of the 2012 Ninth European Dependable Computing Conference (EDCC '12). Sibiu, Romania, 37--48.
[23]
Eddy Truyen, Nico Janssens, Frans Sanen, and Wouter Joosen. 2008. Support for Distributed Adaptations in Aspect-oriented Middleware. In Proceedings of the 7th International Conference on Aspect-oriented Software Development (AOSD '08). Brussels, Belgium, 120--131.

Cited By

View all
  • (2024)StarReact: Detecting Important Network Changes in BFT Protocols with Star-Based Communication2024 IEEE 49th Conference on Local Computer Networks (LCN)10.1109/LCN60385.2024.10639767(1-7)Online publication date: 8-Oct-2024
  • (2022)AWARE: Adaptive Wide-Area Replication for Fast and Resilient Byzantine ConsensusIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2020.303060519:3(1605-1620)Online publication date: 1-May-2022
  • (2020)Resilient Cloud-based Replication with Low LatencyProceedings of the 21st International Middleware Conference10.1145/3423211.3425689(14-28)Online publication date: 7-Dec-2020
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SAC '18: Proceedings of the 33rd Annual ACM Symposium on Applied Computing
April 2018
2327 pages
ISBN:9781450351911
DOI:10.1145/3167132
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: 09 April 2018

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. byzantine fault tolerance
  2. consensus
  3. dynamic adaptation

Qualifiers

  • Research-article

Funding Sources

  • FCT

Conference

SAC 2018
Sponsor:
SAC 2018: Symposium on Applied Computing
April 9 - 13, 2018
Pau, France

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25
The 40th ACM/SIGAPP Symposium on Applied Computing
March 31 - April 4, 2025
Catania , Italy

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)0
Reflects downloads up to 12 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)StarReact: Detecting Important Network Changes in BFT Protocols with Star-Based Communication2024 IEEE 49th Conference on Local Computer Networks (LCN)10.1109/LCN60385.2024.10639767(1-7)Online publication date: 8-Oct-2024
  • (2022)AWARE: Adaptive Wide-Area Replication for Fast and Resilient Byzantine ConsensusIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2020.303060519:3(1605-1620)Online publication date: 1-May-2022
  • (2020)Resilient Cloud-based Replication with Low LatencyProceedings of the 21st International Middleware Conference10.1145/3423211.3425689(14-28)Online publication date: 7-Dec-2020
  • (2019)Resilient Wide-Area Byzantine Consensus Using Adaptive Weighted Replication2019 38th Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS47363.2019.00029(183-18309)Online publication date: Oct-2019
  • (2019)Scalable Efficient Byzantine Fault Tolerance2019 IEEE 3rd Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC)10.1109/IMCEC46724.2019.8983827(1736-1742)Online publication date: Oct-2019

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media