{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T21:40:46Z","timestamp":1763415646754,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":86,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T00:00:00Z","timestamp":1686873600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,19]]},"DOI":"10.1145\/3583668.3594567","type":"proceedings-article","created":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T22:28:38Z","timestamp":1686954518000},"page":"332-343","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["On the Validity of Consensus"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2394-1201","authenticated-orcid":false,"given":"Pierre","family":"Civit","sequence":"first","affiliation":[{"name":"Sorbonne University, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3298-7412","authenticated-orcid":false,"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[{"name":"NUS Singapore, Singapore, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4794-8902","authenticated-orcid":false,"given":"Rachid","family":"Guerraoui","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9714-4079","authenticated-orcid":false,"given":"Jovan","family":"Komatovic","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-5821-2571","authenticated-orcid":false,"given":"Manuel","family":"Vidigueira","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2023,6,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095809.1095817"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11516798_17"},{"key":"e_1_3_2_1_3_1","unstructured":"Ittai Abraham and Cristian Cachin. [n. d.]. What about Validity? https:\/\/decentralizedthoughts.github.io\/2022-12-12-what-about-validity\/."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331629"},{"key":"e_1_3_2_1_5_1","volume-title":"Brief Announcement: Practical Synchronous Byzantine Consensus. In 31st International Symposium on Distributed Computing (DISC","author":"Abraham Ittai","year":"2017","unstructured":"Ittai Abraham, Srinivas Devadas, Kartik Nayak, and Ling Ren. 2017. Brief Announcement: Practical Synchronous Byzantine Consensus. In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_6_1","volume-title":"Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus. arXiv preprint arXiv:1612.02916","author":"Abraham Ittai","year":"2016","unstructured":"Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman. 2016. Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus. arXiv preprint arXiv:1612.02916 (2016)."},{"key":"e_1_3_2_1_7_1","volume-title":"Solidus: An Incentive-compatible Cryptocurrency Based on Permissionless Byzantine Consensus. CoRR, abs\/1612.02916","author":"Abraham Ittai","year":"2016","unstructured":"Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman. 2016. Solidus: An Incentive-compatible Cryptocurrency Based on Permissionless Byzantine Consensus. CoRR, abs\/1612.02916 (2016)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331612"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060289.1060291"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2006.63"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0081-5"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/800221.806707"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0083-3"},{"key":"e_1_3_2_1_14_1","unstructured":"Michael Ben-Or Shafi Goldwasser and Avi Wigderson. 2019. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali. 351--371."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198088"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90020-F"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.06.009"},{"key":"e_1_3_2_1_18_1","volume-title":"Tendermint: Byzantine Fault Tolerance in the Age of Blockchains. Ph. D. Dissertation","author":"Buchman Ethan","year":"2016","unstructured":"Ethan Buchman. 2016. Tendermint: Byzantine Fault Tolerance in the Age of Blockchains. Ph. D. Dissertation. University of Guelph."},{"volume-title":"Introduction to Reliable and Secure Distributed Programming","author":"Cachin Christian","key":"e_1_3_2_1_20_1","unstructured":"Christian Cachin, Rachid Guerraoui, and Lu\u00eds Rodrigues. 2011. Introduction to Reliable and Secure Distributed Programming. Springer Science & Business Media."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44647-8_31"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/571637.571640"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63513"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2022.14"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS51616.2021.00046"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS54860.2022.00013"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2301.04920"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3457588.3457600"},{"volume-title":"Essentials of Blockchain Technology","author":"Correia Miguel","key":"e_1_3_2_1_29_1","unstructured":"Miguel Correia. 2019. From Byzantine Consensus to Blockchain Consensus. In Essentials of Blockchain Technology. Chapman and Hall\/CRC, 41--80."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxh145"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/NCA.2018.8548057"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-21017-4_12"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-67087-0_12"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214112"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/277697.277772"},{"key":"e_1_3_2_1_36_1","volume-title":"Practical Signature-Free Asynchronous Common Subset in Constant Time. Cryptology ePrint Archive","author":"Duan Sisi","year":"2023","unstructured":"Sisi Duan, Xin Wang, and Haibin Zhang. 2023. Practical Signature-Free Asynchronous Common Subset in Constant Time. Cryptology ePrint Archive (2023)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_3_2_1_38_1","volume-title":"Randomized Multivalued Consensus. In Fourth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing. ISORC","author":"Ezhilchelvan Paul","year":"2001","unstructured":"Paul Ezhilchelvan, Achour Mostefaoui, and Michel Raynal. 2001. Randomized Multivalued Consensus. In Fourth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing. ISORC 2001. IEEE, 195--200."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872066"},{"key":"e_1_3_2_1_42_1","volume-title":"Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model. In Conference on the Theory and Application of Cryptographic Techniques. Springer, 135--155","author":"Galil Zvi","year":"1987","unstructured":"Zvi Galil, Stuart Haber, and Moti Yung. 1987. Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model. In Conference on the Theory and Application of Cryptographic Techniques. Springer, 135--155."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538442"},{"key":"e_1_3_2_1_44_1","volume-title":"Multidimensional Approximate Agreement with Asynchronous Fallback. Cryptology ePrint Archive","author":"Ghinea Diana","year":"2023","unstructured":"Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. 2023. Multidimensional Approximate Agreement with Asynchronous Fallback. Cryptology ePrint Archive (2023)."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132757"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0117-1"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.895986"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36108-1_22"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Maurice Herlihy Dmitry N. Kozlov and Sergio Rajsbaum. 2013. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann. https:\/\/store.elsevier.com\/product.jsp?isbn=9780124045781","DOI":"10.1016\/B978-0-12-404578-1.00003-6"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167125"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331529"},{"key":"e_1_3_2_1_52_1","volume-title":"Melliar-Smith","author":"Kihlstrom Kim P.","year":"2003","unstructured":"Kim P. Kihlstrom, Louise E. Moser, and Peter M. Melliar-Smith. 2003. Byzantine Fault Detectors for Solving Consensus. British Computer Society (2003)."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294267"},{"key":"e_1_3_2_1_54_1","volume-title":"High Throughput Byzantine Fault Tolerance. In International Conference on Dependable Systems and Networks","author":"Kotla Ramakrishna","year":"2004","unstructured":"Ramakrishna Kotla and Michael Dahlin. 2004. High Throughput Byzantine Fault Tolerance. In International Conference on Dependable Systems and Networks, 2004. IEEE, 575--584."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484271"},{"key":"e_1_3_2_1_56_1","first-page":"4","article-title":"Paxos Made Simple","volume":"32","author":"Lamport Leslie","year":"2001","unstructured":"Leslie Lamport. 2001. Paxos Made Simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) (2001), 51--58.","journal-title":"ACM SIGACT News (Distributed Computing Column)"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_3_2_1_58_1","unstructured":"Leslie Lamport Robert Shostak and Marshall Pease. 2019. The Byzantine Generals Problem. In Concurrency: the works of leslie lamport. 203--226."},{"key":"e_1_3_2_1_59_1","volume-title":"Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model. arXiv preprint arXiv:2201.01107","author":"Lewis-Pye Andrew","year":"2022","unstructured":"Andrew Lewis-Pye. 2022. Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model. arXiv preprint arXiv:2201.01107 (2022)."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405707"},{"key":"e_1_3_2_1_61_1","volume-title":"SCP: A Computationally-Scalable Byzantine Consensus Protocol For Blockchains. Cryptology ePrint Archive","author":"Luu Loi","year":"2015","unstructured":"Loi Luu, Viswesh Narayanan, Kunal Baweja, Chaodong Zheng, Seth Gilbert, and Prateek Saxena. 2015. SCP: A Computationally-Scalable Byzantine Consensus Protocol For Blockchains. Cryptology ePrint Archive (2015)."},{"volume-title":"Distributed Algorithms","author":"Lynch Nancy A","key":"e_1_3_2_1_62_1","unstructured":"Nancy A Lynch. 1996. Distributed Algorithms. Elsevier."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3354225"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2020.09.010"},{"key":"e_1_3_2_1_65_1","volume-title":"Byzantine Agreement with Interval Validity. In 2018 IEEE 37th Symposium on Reliable Distributed Systems (SRDS). IEEE, 251--260","author":"Melnyk Darya","year":"2018","unstructured":"Darya Melnyk and Roger Wattenhofer. 2018. Byzantine Agreement with Interval Validity. In 2018 IEEE 37th Symposium on Reliable Distributed Systems (SRDS). IEEE, 251--260."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488657"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591853"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484554"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2021.32"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90052-4"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950624"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39989-6_18"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.384006"},{"key":"e_1_3_2_1_74_1","volume-title":"Condition-Based Protocols for Set Agreement Problems. In International Symposium on Distributed Computing. Springer, 48--62","author":"Most\u00e9faoui Achour","year":"2002","unstructured":"Achour Most\u00e9faoui, Sergio Rajsbaum, Michel Raynal, and Matthieu Roy. 2002. Condition-Based Protocols for Set Agreement Problems. In International Symposium on Distributed Computing. Springer, 48--62."},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00027-2"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2005.153"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_3_2_1_78_1","volume-title":"Consensus in Synchronous Systems: A Concise Guided Tour. In 2002 Pacific Rim International Symposium on Dependable Computing, 2002. Proceedings. IEEE, 221--228","author":"Raynal Michel","year":"2002","unstructured":"Michel Raynal. 2002. Consensus in Synchronous Systems: A Concise Guided Tour. In 2002 Pacific Rim International Symposium on Dependable Computing, 2002. Proceedings. IEEE, 221--228."},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41468-018-0014-4"},{"key":"e_1_3_2_1_80_1","unstructured":"Ulrich Schmid and Bettina Weiss. 2004. Synchronous Byzantine Agreement under Hybrid Process and Link Failures. (2004)."},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45539-6_15"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(97)10054-8"},{"key":"e_1_3_2_1_83_1","volume-title":"Byzantine Agreement with Median Validity. In 19th International Conference on Principles of Distributed Systems (OPODIS","volume":"46","author":"Stolz David","year":"2016","unstructured":"David Stolz and Roger Wattenhofer. 2016. Byzantine Agreement with Median Validity. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015), Vol. 46. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik GmbH, 22."},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01407859"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484256"},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.221"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331591"},{"key":"e_1_3_2_1_88_1","volume-title":"Condition-Based Consensus in Synchronous Systems. In International Symposium on Distributed Computing. Springer, 239--248","author":"Zibin Yoav","year":"2003","unstructured":"Yoav Zibin. 2003. Condition-Based Consensus in Synchronous Systems. In International Symposium on Distributed Computing. Springer, 239--248."}],"event":{"name":"PODC '23: 2023 ACM Symposium on Principles of Distributed Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGOPS ACM Special Interest Group on Operating Systems"],"location":"Orlando FL USA","acronym":"PODC '23"},"container-title":["Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594567","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583668.3594567","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:54Z","timestamp":1750178274000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594567"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,16]]},"references-count":86,"alternative-id":["10.1145\/3583668.3594567","10.1145\/3583668"],"URL":"https:\/\/doi.org\/10.1145\/3583668.3594567","relation":{},"subject":[],"published":{"date-parts":[[2023,6,16]]},"assertion":[{"value":"2023-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}