{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,25]],"date-time":"2026-10-25T04:06:09Z","timestamp":1792901169205,"version":"4.5.0"},"reference-count":74,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:00:00Z","timestamp":1780876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"National Science Foundation","award":["2019285"],"award-info":[{"award-number":["2019285"]}]},{"name":"National Science Foundation","award":["2313433"],"award-info":[{"award-number":["2313433"]}]},{"name":"Defense Advanced Research Projects Agency","award":["HR00112590130"],"award-info":[{"award-number":["HR00112590130"]}],"id":[{"id":"https:\/\/ror.org\/02caytj08","id-type":"ROR","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["2442888"],"award-info":[{"award-number":["2442888"]}]},{"name":"Sui Foundation","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,6,8]]},"abstract":"<jats:p>Consensus algorithms play a central role in many distributed systems, including blockchains. The most practical consensus algorithms are based on the partial synchrony model. While partially synchronous protocols are relatively simple, they cannot maintain liveness when the message delivery latency is uncertain. Asynchronous protocols do not rely on bounded latency to maintain liveness, but they are much more difficult to understand and implement, being usually described as a composition of several layers of algorithms. Moreover, due to the FLP impossibility theorem, they only provide probabilistic liveness guarantees. These factors make the correctness of asynchronous protocols challenging to verify, and there have been liveness bugs in these protocols that remain unnoticed for years.<\/jats:p>\n                  <jats:p>We introduce SureDistrib, a formal framework for specifying and verifying probabilistic safety and liveness properties of asynchronous distributed protocols. Our framework supports specifying probabilistic algorithms that depend on other probabilistic functionalities, such as binary agreement algorithms depending on common coins. We define refinement relations for such systems, and prove composition lemmas that replace the underlay functionality with an implementation, so that the composed system refines the original system with an abstract underlay. Based on our framework, we give the first mechanized proof that an asynchronous byzantine fault-tolerant binary agreement algorithm terminates with probability 1 (\u201calmost-sure termination\u201d).<\/jats:p>","DOI":"10.1145\/3808293","type":"journal-article","created":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T18:04:09Z","timestamp":1780941849000},"page":"1152-1177","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["SureDistrib: Verifying Almost-Sure Termination of Composite Asynchronous Byzantine Protocols"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-7811-4231","authenticated-orcid":false,"given":"Longfei","family":"Qiu","sequence":"first","affiliation":[{"name":"Yale University, New Haven, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9430-6165","authenticated-orcid":false,"given":"Jingqi","family":"Xiao","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1595-4849","authenticated-orcid":false,"given":"Ji-Yong","family":"Shin","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8184-7649","authenticated-orcid":false,"given":"Zhong","family":"Shao","sequence":"additional","affiliation":[{"name":"Yale University, New Haven, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,8]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Ittai Abraham Naama Ben-David and Sravya Yandamuri. 2022. Asynchronous Agreement Part 5: Binary Byzantine Agreement from a strong common coin. https:\/\/decentralizedthoughts.github.io\/2022-04-05-aa-part-five-ABBA\/. Accessed: November 2 2025."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538426"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331612"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0162-z"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2019.2"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.OPODIS.2023.6"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/800221.806707"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198088"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2022.10"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-020-00603-x"},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","unstructured":"Christian Cachin Klaus Kursawe and Victor Shoup. 2000. Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement using Cryptography. Cryptology ePrint Archive Paper 2000\/034. https:\/\/eprint.iacr.org\/2000\/034","DOI":"10.1145\/343477.343531"},{"key":"e_1_3_1_14_2","unstructured":"Ran Canetti Ling Cheung Dilsun Kaynar Moses Liskov Nancy Lynch Olivier Pereira and Roberto Segala. 2005. Using Probabilistic I\/O Automata to Analyze an Oblivious Transfer Protocol. Cryptology ePrint Archive Paper 2005\/452. https:\/\/eprint.iacr.org\/2005\/452"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.09.007"},{"key":"e_1_3_1_16_2","unstructured":"Miguel Castro. 2001. Practical Byzantine Fault Tolerance. Ph. D. Dissertation. Massachusetts Institute of Technology. https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2017\/01\/thesis-mcastro.pdf"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_34"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30044-8_13"},{"key":"e_1_3_1_19_2","unstructured":"Karl Crary. 2021. Verifying the Hashgraph Consensus Algorithm. arXiv:2102.01167 [cs.LO] https:\/\/arxiv.org\/abs\/2102.01167"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1060"},{"key":"e_1_3_1_21_2","unstructured":"Xiaohai Dai Chaozheng Ding Hai Jin Julian Loss and Ling Ren. 2024. Ipotane: Balancing the Good and Bad Cases of Asynchronous BFT. Cryptology ePrint Archive Paper 2024\/653. https:\/\/eprint.iacr.org\/2024\/653"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3492321.3519594"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90459-3_21"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3776691"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62225"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-032-01881-6_20"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3586051"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_3_1_30_2","unstructured":"Bryan Ford Philipp Jovanovic and Ewa Syta. 2020. Que Sera Consensus: Simple Asynchronous Agreement with Private Coins and Threshold Logical Clocks. CoRR abs\/2003.02291 (2020). arXiv:2003.02291 https:\/\/arxiv.org\/abs\/2003.02291"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/DSN58291.2024.00047"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3559379"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-18283-9_14"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3674632"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417262"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2166.357214"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815428"},{"key":"e_1_3_1_38_2","first-page":"20","volume-title":"Proceedings of the 2025 USENIX Conference on Usenix Annual Technical Conference (Boston, MA, USA) (USENIX ATC \u201925)","author":"Huang Rongji","year":"2025","unstructured":"Rongji Huang, Xiangzhe Wang, Xiaofeng Yan, Lei Fan, Guangtao Xue, and Shengyun Liu. 2025. Chitu: avoiding unnecessary fallback in Byzantine consensus. In Proceedings of the 2025 USENIX Conference on Usenix Annual Technical Conference (Boston, MA, USA) (USENIX ATC \u201925). USENIX Association, USA, Article 54, 20 pages."},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3763091"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","unstructured":"Annu John Igor Konnov Ulrich Schmid Helmut Veith and Josef Widder. 2013. Parameterized model checking of fault-tolerant distributed algorithms by abstraction. In 2013 Formal Methods in Computer-Aided Design. 201\u2013209. doi:10.1109\/FMCAD.2013.6679411","DOI":"10.1109\/FMCAD.2013.6679411"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467905"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394799"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-19(1:5)2023"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44585-4_17"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_6"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198117"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41852"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3632879"},{"key":"e_1_3_1_49_2","unstructured":"Andrew Miller. 2018. Bug in ABA protocol\u2019s use of Common Coin. https:\/\/github.com\/amiller\/HoneyBadgerBFT\/issues\/59. Accessed: November 2 2025."},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978399"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611468"},{"key":"e_1_3_1_52_2","unstructured":"Satoshi Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System. https:\/\/bitcoin.org\/bitcoin.pdf"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3578358.3592148"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008917"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3656423"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3729306"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","unstructured":"Longfei Qiu Jingqi Xiao Ji Yong Shin and Zhong Shao. 2026. Artifact For PLDI 2026 Paper #304 SureDistrib: Verifying Almost-sure Termination of Composite Asynchronous Byzantine Protocols. doi:10.5281\/zenodo.19616610","DOI":"10.5281\/zenodo.19616610"},{"key":"e_1_3_1_58_2","unstructured":"Longfei Qiu Jingqi Xiao Ji-Yong Shin and Zhong Shao. 2026. SureDistrib: Verifying Almost-Sure Termination of Composite Asynchronous Byzantine Protocols. Technical Report YALEU\/DCS\/TR-1576. Yale Univ. https:\/\/flint.cs.yale.edu\/publications\/suredistrib.html"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","unstructured":"Michael O. Rabin. 1983. Randomized byzantine generals. In 24th Annual Symposium on Foundations of Computer Science (sfcs 1983). 403\u2013409. doi:10.1109\/SFCS.1983.48","DOI":"10.1109\/SFCS.1983.48"},{"key":"e_1_3_1_60_2","volume-title":"Ph. D. Dissertation","author":"Segala Roberto","year":"1996","unstructured":"Roberto Segala. 1996. Modeling and verification of randomized distributed real-time systems. Ph. D. Dissertation. USA. https:\/\/dspace.mit.edu\/handle\/1721.1\/36560"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158116"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613172"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-72208-5"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3559361"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","unstructured":"Xiao Sui Xin Wang and Sisi Duan. 2025. Signature-Free Atomic Broadcast with Optimal \ud835\udc42(\ud835\udc5b2) Messages and \ud835\udc42(1) Expected Time. In 2025 IEEE Symposium on Security and Privacy (SP). 1547\u20131565. doi:10.1109\/SP61157.2025.00244","DOI":"10.1109\/SP61157.2025.00244"},{"key":"e_1_3_1_66_2","first-page":"18","volume-title":"Proceedings of the 18th USENIX Conference on Operating Systems Design and Implementation (Santa Clara, CA, USA) (OSDI \u201924)","author":"Sun Xudong","year":"2024","unstructured":"Xudong Sun, Wenjie Ma, Jiawei Tyler Gu, Zicheng Ma, Tej Chajed, Jon Howell, Andrea Lattuada, Oded Padon, Lalith Suresh, Adriana Szekeres, and Tianyin Xu. 2024. Anvil: verifying liveness of cluster management controllers. In Proceedings of the 18th USENIX Conference on Operating Systems Design and Implementation (Santa Clara, CA, USA) (OSDI \u201924). USENIX Association, USA, Article 35, 18 pages."},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3450967"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/3600006.3613150"},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","unstructured":"The Rocq Development Team. 2025. The Rocq Prover. doi:10.5281\/zenodo.15149629","DOI":"10.5281\/zenodo.15149629"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","unstructured":"S\u00f8ren Eller Thomsen and Bas Spitters. 2021. Formalizing Nakamoto-Style Proof of Stake. In 2021 IEEE 34th Computer Security Foundations Symposium (CSF). 1\u201315. doi:10.1109\/CSF51468.2021.00042","DOI":"10.1109\/CSF51468.2021.00042"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737958"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00056-X"},{"key":"e_1_3_1_73_2","unstructured":"xygdys. 2022. A Bug in the Conf Phase of ABA protocol. https:\/\/github.com\/initc3\/HoneyBadgerBFT-Python\/issues\/57. Accessed: November 2 2025."},{"key":"e_1_3_1_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331591"},{"key":"e_1_3_1_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/3658644.3690355"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808293","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808293","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T10:36:36Z","timestamp":1790073396000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3808293"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,8]]},"references-count":74,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2026,6,8]]}},"alternative-id":["10.1145\/3808293"],"URL":"https:\/\/doi.org\/10.1145\/3808293","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,8]]},"assertion":[{"value":"2025-11-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}