Logo PTI Logo FedCSIS

Proceedings of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 25

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

, ,

DOI: http://dx.doi.org/10.15439/2021F38

Citation: Proceedings of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 25, pages 291–300 ()

Full text

Abstract. 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.

References

  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.