Bernoulli Meets PBFT: Modeling BFT Protocols in the Presence of Dynamic Failures

• Autorzy: Nischwitz Martin , Esche Marko , Tschorsch Florian

Identyfikatory

DOI

10.15439/2021F38

• Konferencja: Federated Conference on Computer Science and Information Systems (16 ; 02-05.09.2021 ; online)
• Języki publikacji: EN

Abstrakty

EN

The publication of the pivotal state machine replication protocol PBFT laid the foundation for a body of BFT protocols. We introduce a probabilistic model for evaluating BFT protocols in the presence of dynamic link and crash failures. The model is derived from the communication pattern, facilitating an adaptation to other protocols. The state of replicas is captured and used to derive the success probability of the protocol execution. To this end, we examine the influence of link and crash failure rates as well as the number of replicas. A comparison in protocol behavior of PBFT, Zyzzyva and SBFT is performed.

Słowa kluczowe

EN

distributed processing; probability; protocols; software; fault tolerance

PL

przetwarzanie rozproszone; prawdopodobieństwo; protokoły; odporność na błędy; oprogramowanie

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2021
• Tom: Vol. 25
• Strony: 291--300
• Opis fizyczny: Bibliogr. 30 poz., wykr., wz., tab.

Twórcy

autor

Nischwitz Martin

• Physikalisch-Technische Bundesanstalt Berlin, Germany

autor

Esche Marko

• Physikalisch-Technische Bundesanstalt Berlin, Germany

autor

Tschorsch Florian

• Department for Distributed Security Infrastructures Technische Universität Berlin Berlin, Germany

Bibliografia

• 1. F. Thiel, M. Esche, F. Grasso Toro, A. Oppermann, J. Wetzlich, and D. Peters, “The European Metrology Cloud,” in Proceedings of the 18th International Congress of Metrology, Jan. 2017. http://dx.doi.org/10.1051/metrology/201709001
• 2. M. Castro and B. Liskov, “Practical Byzantine Fault Tolerance and Proactive Recovery,” ACM Trans. Comput. Syst., vol. 20, no. 4, pp. 398–461, Nov. 2002. http://dx.doi.org/10.1145/571637.571640
• 3. P. Sazonova, “The general universal model of blockchain technology based on an analysis of some implementations,” in Communication Papers of the 2020 Federated Conference on Computer Science and Information Systems. PTI, Sep. 2020. http://dx.doi.org/10.15439/2020f190. [Online]. Available: https://doi.org/10.15439/2020f190
• 4. A. Bessani, J. Sousa, and E. E. P. Alchieri, “State Machine Replication for the Masses with BFT-SMART,” in 2014 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, Jun. 2014. http://dx.doi.org/10.1109/DSN.2014.43. ISSN 1530-0889 pp. 355–362.
• 5. E. Buchman, J. Kwon, and Z. Milosevic, “The latest gossip on BFT consensus,” CoRR, vol. abs/1807.04938, 2018.
• 6. P. Aublin, S. B. Mokhtar, and V. Quéma, “RBFT: Redundant Byzantine Fault Tolerance,” in 2013 IEEE 33rd International Conference on Distributed Computing Systems, Jul. 2013. http://dx.doi.org/10.1109/ICDCS.2013.53. ISSN 1063-6927 pp. 297–306.
• 7. R. Kapitza, J. Behl, C. Cachin, T. Distler, S. Kuhnle, S. V. Mohammadi, W. Schröder-Preikschat, and K. Stengel, “CheapBFT: Resource-efficient Byzantine Fault Tolerance,” in Proceedings of the 7th ACM European Conference on Computer Systems, ser. EuroSys ’12. New York, NY, USA: ACM, 2012. http://dx.doi.org/10.1145/2168836.2168866. ISBN 978-1-4503-1223-3 pp. 295–308.
• 8. E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis, A. De Caro, D. Enyeart, C. Ferris, G. Laventman, Y. Manevich, S. Muralidharan, C. Murthy, B. Nguyen, M. Sethi, G. Singh, K. Smith, A. Sorniotti, C. Stathakopoulou, M. Vukolić, S. W. Cocco, and J. Yellick, “Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains,” in Proceedings of the Thirteenth EuroSys Conference, ser. EuroSys ’18. New York, NY, USA: ACM, 2018. http://dx.doi.org/10.1145/3190508.3190538. ISBN 978-1-4503-5584-1 pp. 30:1–30:15.
• 9. N. Santoro and P. Widmayer, “Time is not a healer,” in STACS 89, B. Monien and R. Cori, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1989. http://dx.doi.org/10.1007/BFb0028994. ISBN 978-3-540-46098-5 pp. 304–313.
• 10. R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong, “Zyzzyva: Speculative Byzantine Fault Tolerance,” SIGOPS Oper. Syst. Rev., vol. 41, no. 6, pp. 45–58, Oct. 2007. http://dx.doi.org/10.1145/1323293.1294267
• 11. G. Golan Gueta, I. Abraham, S. Grossman, D. Malkhi, B. Pinkas, M. Reiter, D. Seredinschi, O. Tamir, and A. Tomescu, “Sbft: A scalable and decentralized trust infrastructure,” in 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), 2019. http://dx.doi.org/10.1109/DSN.2019.00063 pp. 568–580.
• 12. G. Bracha and S. Toueg, “Asynchronous Consensus and Broadcast Protocols,” J. ACM, vol. 32, no. 4, pp. 824–840, Oct. 1985. http://dx.doi.org/10.1145/4221.214134
• 13. C. Dwork, N. Lynch, and L. Stockmeyer, “Consensus in the Presence of Partial Synchrony,” J. ACM, vol. 35, no. 2, pp. 288–323, Apr. 1988. http://dx.doi.org/10.1145/42282.42283
• 14. M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of Distributed Consensus with One Faulty Process,” J. ACM, vol. 32, no. 2, pp. 374–382, Apr. 1985. http://dx.doi.org/10.1145/3149.214121
• 15. B. Liskov, “From Viewstamped Replication to Byzantine Fault Tolerance,” in Replication: Theory and Practice, ser. Lecture Notes in Computer Science, no. 5959, 2010.
• 16. A. S. de Sá, A. E. Silva Freitas, and R. J. de Araújo Macêdo, “Adaptive Request Batching for Byzantine Replication,” SIGOPS Oper. Syst. Rev., vol. 47, no. 1, pp. 35–42, Jan. 2013. http://dx.doi.org/10.1145/2433140.2433149
• 17. U. Schmid, “How to model link failures: a perception-based fault model,” in 2001 International Conference on Dependable Systems and Networks, Jul. 2001. http://dx.doi.org/10.1109/DSN.2001.941391 pp. 57–66.
• 18. U. Schmid, B. Weiss, and I. Keidar, “Impossibility Results and Lower Bounds for Consensus under Link Failures,” SIAM Journal on Computing, vol. 38, no. 5, pp. 1912–1951, 2009. http://dx.doi.org/10.1137/S009753970443999X
• 19. R. Halalai, T. A. Henzinger, and V. Singh, “Quantitative Evaluation of BFT Protocols,” in 2011 Eighth International Conference on Quantitative Evaluation of SysTems, Sep. 2011. http://dx.doi.org/10.1109/QEST.2011.40 pp. 255–264.
• 20. H. Sukhwani, J. M. Martínez, X. Chang, K. S. Trivedi, and A. Rindos, “Performance Modeling of PBFT Consensus Process for Permissioned Blockchain Network (Hyperledger Fabric),” in 2017 IEEE 36th Symposium on Reliable Distributed Systems (SRDS), Sep. 2017. doi: 10.1109/SRDS.2017.36 pp. 253–255.
• 21. A. Singh, T. Das, P. Maniatis, P. Druschel, and T. Roscoe, “BFT Protocols Under Fire,” in Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, ser. NSDI’08. Berkeley, CA, USA: USENIX Association, 2008. ISBN 111-999-5555-22-1 pp. 189–204.
• 22. M. Abd-El-Malek, G. R. Ganger, G. R. Goodson, M. K. Reiter, and J. J. Wylie, “Fault-scalable Byzantine Fault-tolerant Services,” SIGOPS Oper. Syst. Rev., vol. 39, no. 5, pp. 59–74, Oct. 2005. http://dx.doi.org/10.1145/1095809.1095817
• 23. N. Fathollahnejad, E. Villani, R. Pathan, R. Barbosa, and J. Karlsson, “On reliability analysis of leader election protocols for virtual traffic lights,” in 2013 43rd Annual IEEE/IFIP Conference on Dependable Systems and Networks Workshop (DSN-W), Jun. 2013. http://dx.doi.org/10.1109/D-SNW.2013.6615529. ISSN 2325-6664 pp. 1–12.
• 24. W. Xu and R. Kapitza, “RATCHETA: Memory-Bounded Hybrid Byzantine Consensus for Cooperative Embedded Systems,” in 2018 IEEE 37th Symposium on Reliable Distributed Systems (SRDS), Oct. 2018. http://dx.doi.org/10.1109/SRDS.2018.00021. ISSN 2575-8462 pp. 103–112.
• 25. U. Schmid, B. Weiss, and J. Rushby, “Formally verified Byzantine agreement in presence of link faults,” in Proceedings 22nd International Conference on Distributed Computing Systems, Jul. 2002. http://dx.doi.org/10.1109/ICDCS.2002.1022311. ISSN 1063-6927 pp. 608–616.
• 26. M. Biely, U. Schmid, and B. Weiss, “Synchronous consensus under hybrid process and link failures,” Theoretical Computer Science, vol. 412, no. 40, pp. 5602–5630, 2011. http://dx.doi.org/10.1016/j.tcs.2010.09.032 Stabilization, Safety and Security.
• 27. A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song, “The Honey Badger of BFT Protocols,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’16. New York, NY, USA: ACM, 2016. http://dx.doi.org/10.1145/2976749.2978399. ISBN 978-1-4503-4139-4 pp. 31–42.
• 28. M. Nischwitz, M. Esche, and F. Tschorsch, “Bernoulli meets pbft: Modeling bft protocols in the presence of dynamic failures,” 2020.
• 29. C. Cachin, “Yet another visit to Paxos,” Apr. 2011.
• 30. H. H. Nguyen, K. Palani, and D. M. Nicol, “Extensions of Network Reliability Analysis,” in 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), Jun. 2019. http://dx.doi.org/10.1109/DSN.2019.00023 pp. 88–99.

Uwagi

1. Track 2: Computer Science and Systems

2. Session: 14th Workshop on Computer Aspects of Numerical Algorithms