{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T18:25:29Z","timestamp":1775067929269,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T00:00:00Z","timestamp":1718582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Deutsche Forschungsgemeinschaft (DFG, German Re- search Foundation)","award":["446811880 (BFT2Chain)"],"award-info":[{"award-number":["446811880 (BFT2Chain)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,17]]},"DOI":"10.1145\/3662158.3662810","type":"proceedings-article","created":{"date-parts":[[2024,6,5]],"date-time":"2024-06-05T14:38:06Z","timestamp":1717598286000},"page":"170-181","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Probabilistic Byzantine Fault Tolerance"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-5838-1667","authenticated-orcid":false,"given":"Diogo","family":"Avelas","sequence":"first","affiliation":[{"name":"LASIGE, Faculdade de Ciencias, Universidade de Lisboa, Lisbon, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2309-2457","authenticated-orcid":false,"given":"Hasan","family":"Heydari","sequence":"additional","affiliation":[{"name":"LASIGE, Faculdade de Ciencias, Universidade de Lisboa, Lisbon, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6022-3631","authenticated-orcid":false,"given":"Eduardo","family":"Alchieri","sequence":"additional","affiliation":[{"name":"Universidade de Brasilia, Bras\u00edlia, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2440-5366","authenticated-orcid":false,"given":"Tobias","family":"Distler","sequence":"additional","affiliation":[{"name":"Friedrich-Alexander-Universit\u00e4t Erlangen-N\u00fcrnberg, Erlangen, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8386-1628","authenticated-orcid":false,"given":"Alysson","family":"Bessani","sequence":"additional","affiliation":[{"name":"LASIGE, Faculdade de Ciencias, Universidade de Lisboa, Lisbon, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2024,6,17]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC '21)","author":"Abraham Ittai","year":"2021","unstructured":"Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. 2021. Good-case Latency of Byzantine Broadcast: a Complete Categorization. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC '21)."},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of th 19th International Symposium on Distributed Computing (DISC '05)","author":"Aiyer Amitanand","unstructured":"Amitanand Aiyer, Lorenzo Alvisi, and Rida A. Bazzi. 2005. On the Availability of Non-strict Quorum Systems. In Proceedings of th 19th International Symposium on Distributed Computing (DISC '05)."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Diogo Avel\u00e3s Hasan Heydari Eduardo Alchieri Tobias Distler and Alysson Bessani. 2024. Probabilistic Byzantine Fault Tolerance (Extended Version). arXiv:2405.04606 [cs.DC]","DOI":"10.1145\/3662158.3662810"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 2nd Symposium on Principles of Distributed Computing (PODC '83)","author":"Ben-Or Michael","year":"1983","unstructured":"Michael Ben-Or. 1983. Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols. In Proceedings of the 2nd Symposium on Principles of Distributed Computing (PODC '83)."},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 50th IEEE\/IFIP Int. Conference on Dependable Systems and Networks (DSN '20)","author":"Bessani Alysson","year":"2020","unstructured":"Alysson Bessani, Eduardo Alchieri, Jo\u00e3o Sousa, Andr\u00e9 Oliveira, and Fernando Pedone. 2020. From Byzantine Replication to Blockchain: Consensus is only the Beginning. In Proceedings of the 50th IEEE\/IFIP Int. Conference on Dependable Systems and Networks (DSN '20)."},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 44th International Conference on Dependable Systems and Networks (DSN '14)","author":"Bessani Alysson","unstructured":"Alysson Bessani, Jo\u00e3o Sousa, and Eduardo E. P. Alchieri. 2014. State Machine Replication for the Masses with BFT-SMaRt. In Proceedings of the 44th International Conference on Dependable Systems and Networks (DSN '14)."},{"key":"e_1_3_2_1_7_1","volume-title":"Making Byzantine Consensus Live. Distributed Computing 35, 6","author":"Bravo Manuel","year":"2022","unstructured":"Manuel Bravo, Gregory Chockler, and Alexey Gotsman. 2022. Making Byzantine Consensus Live. Distributed Computing 35, 6 (2022)."},{"key":"e_1_3_2_1_8_1","unstructured":"Vitalik Buterin and Virgil Griffith. 2019. Casper the Friendly Finality Gadget. arXiv:1710.09437 [cs.CR]"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/646766.704283"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 19th Symposium on Principles of Distributed Computing (PODC '00)","author":"Cachin Christian","year":"2000","unstructured":"Christian Cachin, Klaus Kursawe, and Victor Shoup. 2000. Random Oracles in Constantipole: Practical Asynchronous Byzantine Agreement Using Cryptography. In Proceedings of the 19th Symposium on Principles of Distributed Computing (PODC '00)."},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the 26th International Conference on Principles of Distributed Systems (OPODIS '22)","author":"Cachin Christian","year":"2022","unstructured":"Christian Cachin, Giuliano Losa, and Luca Zanolini. 2022. Quorum Systems in Permissionless Network. In Proceedings of the 26th International Conference on Principles of Distributed Systems (OPODIS '22)."},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 40th International Symposium on Reliable Distributed Systems (SRDS '21)","author":"Cason Daniel","year":"2021","unstructured":"Daniel Cason, Enrique Fynn, Nenad Milosevic, Zarko Milosevic, Ethan Buchman, and Fernando Pedone. 2021. The Design, Architecture and Performance of the Tendermint Blockchain Network. In Proceedings of the 40th International Symposium on Reliable Distributed Systems (SRDS '21)."},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI '99)","author":"Castro Miguel","year":"1999","unstructured":"Miguel Castro and Barbara Liskov. 1999. Practical Byzantine Fault Tolerance. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI '99)."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the IEEE Symposium on Security and Privacy (SP '21)","author":"Crain Tyler","year":"2021","unstructured":"Tyler Crain, Christopher Natoli, and Vincent Gramoli. 2021. Red Belly: A Secure, Fair and Scalable Open Blockchain. In Proceedings of the IEEE Symposium on Security and Privacy (SP '21)."},{"key":"e_1_3_2_1_15_1","volume-title":"Byzantine Fault-Tolerant State-Machine Replication from a Systems Perspective. Comput. Surveys 54, 1","author":"Distler Tobias","year":"2021","unstructured":"Tobias Distler. 2021. Byzantine Fault-Tolerant State-Machine Replication from a Systems Perspective. Comput. Surveys 54, 1 (2021)."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/646334.687813"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243812"},{"key":"e_1_3_2_1_18_1","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"Dubhashi Devdatt P","unstructured":"Devdatt P Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_19_1","volume-title":"Consensus in the Presence of Partial Synchrony. J. ACM 35, 2","author":"Dwork Cynthia","year":"1988","unstructured":"Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988. Consensus in the Presence of Partial Synchrony. J. ACM 35, 2 (1988)."},{"key":"e_1_3_2_1_20_1","volume-title":"Paterson","author":"Fischer Michael J.","year":"1985","unstructured":"Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32, 2 (1985)."},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS '22)","author":"Gao Yingzi","year":"2022","unstructured":"Yingzi Gao, Yuan Lu, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. 2022. Dumbo-NG: Fast Asynchronous BFT Consensus with Throughput-Oblivious Latency. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (CCS '22)."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132757"},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings of the 49th International Conference on Dependable Systems and Networks (DSN '19)","author":"Gueta Guy Golan","year":"2019","unstructured":"Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael Reiter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. 2019. SBFT: A Scalable and Decentralized Trust Infrastructure. In Proceedings of the 49th International Conference on Dependable Systems and Networks (DSN '19)."},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC '21)","author":"Keidar Idit","year":"2021","unstructured":"Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. 2021. All You Need is DAG. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (PODC '21)."},{"key":"e_1_3_2_1_27_1","volume-title":"Breaking the O(n2) bit barrier: Scalable Byzantine agreement with an adaptive adversary. J. ACM 58, 4","author":"King Valerie","year":"2011","unstructured":"Valerie King and Jared Saia. 2011. Breaking the O(n2) bit barrier: Scalable Byzantine agreement with an adaptive adversary. J. ACM 58, 4 (2011)."},{"key":"e_1_3_2_1_28_1","volume-title":"The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems 4, 3","author":"Lamport Leslie","year":"1982","unstructured":"Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems 4, 3 (1982)."},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the 27th International Conference on Principles of Distributed Systems (OPODIS '23)","author":"Lewis-Pye Andrew","year":"2023","unstructured":"Andrew Lewis-Pye and Ittai Abraham. 2023. Fever: Optimal Responsive View Synchronisation. In Proceedings of the 27th International Conference on Principles of Distributed Systems (OPODIS '23)."},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the 11th Symposium on Cloud Computing (SoCC '20)","author":"Li Peilun","year":"2020","unstructured":"Peilun Li, Guosai Wang, Xiaoqi Chen, Fan Long, and Wei Xu. 2020. Gosig: A Scalable and High-Performance Byzantine Consensus for Consortium Blockchains. In Proceedings of the 11th Symposium on Cloud Computing (SoCC '20)."},{"key":"e_1_3_2_1_31_1","volume-title":"A Scalable Multi-Layer PBFT Consensus for Blockchain","author":"Li Wenyu","year":"2020","unstructured":"Wenyu Li, Chenglin Feng, Lei Zhang, Hao Xu, Bin Cao, and Muhammad Ali Imran. 2020. A Scalable Multi-Layer PBFT Consensus for Blockchain. IEEE Transactions on Parallel and Distributed Systems 32, 5 (2020)."},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the 37th International Symposium on Distributed Computing (DISC '23)","author":"Li Xiao","year":"2023","unstructured":"Xiao Li, Eric Chan, and Mohsen Lesani. 2023. Quorum Subsumption for Heterogeneous Quorum Systems. In Proceedings of the 37th International Symposium on Distributed Computing (DISC '23)."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613164"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the ACM Symposium on Operating Systems Principles (SOSP '19)","author":"Lokhava Marta","year":"2019","unstructured":"Marta Lokhava, Giuliano Losa, David Mazi\u00e8res, Graydon Hoare, Nicolas Barry, Eli Gafni, Jonathan Jove, Rafa\u0142 Malinowsky, and Jed McCaleb. 2019. Fast and Secure Global Payments with Stellar. In Proceedings of the ACM Symposium on Operating Systems Principles (SOSP '19)."},{"key":"e_1_3_2_1_35_1","volume-title":"A Fault-tolerant Protocol for Atomic Broadcast","author":"Luan Shyh-Wei","year":"1990","unstructured":"Shyh-Wei Luan and Virgil D Gligor. 1990. A Fault-tolerant Protocol for Atomic Broadcast. IEEE Transactions on Parallel & Distributed Systems 1, 3 (1990)."},{"key":"e_1_3_2_1_36_1","volume-title":"Probabilistic Quorum Systems. Information and Computation 170, 2","author":"Malkhi Dahlia","year":"2001","unstructured":"Dahlia Malkhi, Michael Reiter, Avishai Wool, and Rebecca Wright. 2001. Probabilistic Quorum Systems. Information and Computation 170, 2 (2001)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796482"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-981-10-2738-3","volume-title":"Proceedings of the 23rd Conference on Computer and Communications Security (CCS '16)","author":"Miller Andrew","year":"2016","unstructured":"Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. 2016. The Honey Badger of BFT Protocols. In Proceedings of the 23rd Conference on Computer and Communications Security (CCS '16)."},{"key":"e_1_3_2_1_39_1","volume-title":"Miguel Correia, and Paulo Verissimo.","author":"Moniz Henrique","year":"2011","unstructured":"Henrique Moniz, Nuno Ferreria Neves, Miguel Correia, and Paulo Verissimo. 2011. RITAS: Services for Randomized Intrusion Tolerance. IEEE Transactions on Dependable and Secure Computing 8, 1 (2011)."},{"key":"e_1_3_2_1_40_1","volume-title":"O(n2) Messages, and O(1) Expected Time. J. ACM 62, 4","author":"Most\u00e9faoui Achour","year":"2015","unstructured":"Achour Most\u00e9faoui, Hamouma Moumen, and Michel Raynal. 2015. Signature-free Asynchronous Binary Byzantine Consensus with t < n\/3, O(n2) Messages, and O(1) Expected Time. J. ACM 62, 4 (2015)."},{"key":"e_1_3_2_1_41_1","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_42_1","volume-title":"Bitcoin: A Peer-to-Peer Electronic Cash System.","author":"Nakamoto Satoshi","year":"2008","unstructured":"Satoshi Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System."},{"key":"e_1_3_2_1_43_1","volume-title":"Cogsworth: Byzantine View Synchronization. Cryptoeconomic Systems 1, 2","author":"Naor Oded","year":"2021","unstructured":"Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. 2021. Cogsworth: Byzantine View Synchronization. Cryptoeconomic Systems 1, 2 (2021)."},{"key":"e_1_3_2_1_44_1","volume-title":"Proceedings of the 34th International Symposium on Distributed Computing (DISC '20)","author":"Naor Oded","year":"2020","unstructured":"Oded Naor and Idit Keidar. 2020. Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR. In Proceedings of the 34th International Symposium on Distributed Computing (DISC '20)."},{"key":"e_1_3_2_1_45_1","volume-title":"Proceedings of the 28th Symposium on Operating Systems Principles (SOSP '21)","author":"Neiheiser Ray","year":"2021","unstructured":"Ray Neiheiser, Miguel Matos, and Lu\u00eds Rodrigues. 2021. Kauri: Scalable BFT Consensus with Pipelined Tree-based Dissemination and Aggregation. In Proceedings of the 28th Symposium on Operating Systems Principles (SOSP '21)."},{"key":"e_1_3_2_1_46_1","volume-title":"Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT '17)","author":"Pass Rafael","year":"2017","unstructured":"Rafael Pass and Elaine Shi. 2017. The Sleepy Model of Consensus. In Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT '17)."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/645955.758421"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.48"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/98163.98167"},{"key":"e_1_3_2_1_50_1","volume-title":"Proceedings of the 9th European Conference on Dependable Computing (EDCC'12)","author":"Sousa Jo\u00e3o","year":"2012","unstructured":"Jo\u00e3o Sousa and Alysson Bessani. 2012. From Byzantine Consensus to BFT State Machine Replication: A Latency-Optimal Transformation. In Proceedings of the 9th European Conference on Dependable Computing (EDCC'12)."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3559361"},{"key":"e_1_3_2_1_52_1","volume-title":"Proceedings of the 43rd International Conference on Distributed Computing Systems (ICDCS '23)","author":"Vassantlal Robin","year":"2023","unstructured":"Robin Vassantlal, Hasan Heydari, and Alysson Bessani. 2023. On the Minimal Knowledge Required for Solving Stellar Consensus. In Proceedings of the 43rd International Conference on Distributed Computing Systems (ICDCS '23)."},{"key":"e_1_3_2_1_53_1","first-page":"101","volume":"2","author":"Vukoli\u0107 Marko","year":"2013","unstructured":"Marko Vukoli\u0107. 2013. The Origin of Quorum Systems. Bulletin of EATCS 2, 101 (2013).","journal-title":"EATCS"},{"key":"e_1_3_2_1_54_1","volume-title":"BFT Replication. In Proceedings of the International Workshop on Open Problems in Network Security (iNetSec '15)","author":"Vukoli\u0107 Marko","year":"2015","unstructured":"Marko Vukoli\u0107. 2015. The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication. In Proceedings of the International Workshop on Open Problems in Network Security (iNetSec '15)."},{"key":"e_1_3_2_1_55_1","volume-title":"Proceedings of the 38th Symposium on Principles of Distributed Computing (PODC '19)","author":"Yin Maofan","year":"2019","unstructured":"Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In Proceedings of the 38th Symposium on Principles of Distributed Computing (PODC '19)."},{"key":"e_1_3_2_1_56_1","volume-title":"Signed Quorum Systems. Distributed Computing 18, 4","author":"Haifeng Yu.","year":"2006","unstructured":"Haifeng Yu. 2006. Signed Quorum Systems. Distributed Computing 18, 4 (2006)."},{"key":"e_1_3_2_1_57_1","volume-title":"Proceedings of the 2018 Conference on Computer and Communications Security (CCS '18)","author":"Zamani Mahdi","year":"2018","unstructured":"Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. 2018. RapidChain: Scaling Blockchain via Full Sharding. In Proceedings of the 2018 Conference on Computer and Communications Security (CCS '18)."},{"key":"e_1_3_2_1_58_1","volume-title":"Proceedings of the 32nd USENIX Security Symposium (USENIX Security 23)","author":"Zhang Haibin","year":"2023","unstructured":"Haibin Zhang, Sisi Duan, Boxin Zhao, and Liehuang Zhu. 2023. WaterBear: Practical Asynchronous BFT Matching Security Guarantees of Partially Synchronous BFT. In Proceedings of the 32nd USENIX Security Symposium (USENIX Security 23)."}],"event":{"name":"PODC '24: 43rd ACM Symposium on Principles of Distributed Computing","location":"Nantes France","acronym":"PODC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGOPS ACM Special Interest Group on Operating Systems"]},"container-title":["Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3662158.3662810","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:43:41Z","timestamp":1750290221000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3662158.3662810"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,17]]},"references-count":56,"alternative-id":["10.1145\/3662158.3662810","10.1145\/3662158"],"URL":"https:\/\/doi.org\/10.1145\/3662158.3662810","relation":{},"subject":[],"published":{"date-parts":[[2024,6,17]]},"assertion":[{"value":"2024-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}