{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T17:44:36Z","timestamp":1782927876021,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62572224"],"award-info":[{"award-number":["62572224"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62332009"],"award-info":[{"award-number":["62332009"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China","award":["JYB2025XDXM118"],"award-info":[{"award-number":["JYB2025XDXM118"]}]},{"name":"111 Center","award":["B26023"],"award-info":[{"award-number":["B26023"]}]},{"name":"Natural Science Foundation of Hunan Province (China)","award":["2024JJ5128"],"award-info":[{"award-number":["2024JJ5128"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,7,6]]},"DOI":"10.1145\/3796701.3815915","type":"proceedings-article","created":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T16:40:43Z","timestamp":1782924043000},"page":"516-526","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Distributed Renaming with Subquadratic Bits via Scalable Committee Election"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-3923-8464","authenticated-orcid":false,"given":"Sirui","family":"Bai","sequence":"first","affiliation":[{"name":"State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1233-8546","authenticated-orcid":false,"given":"Xinyu","family":"Fu","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7273-9873","authenticated-orcid":false,"given":"Yuyi","family":"Wang","sequence":"additional","affiliation":[{"name":"CRRC Zhuzhou Institute, Zhuzhou, China and Tengen Intelligence Institute, Zhuzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-2618-687X","authenticated-orcid":false,"given":"Chaodong","family":"Zheng","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China and University of Chinese Academy of Sciences (Nanjing), Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3732772.3733533"},{"key":"e_1_3_2_1_2_1","unstructured":"Dan Alistarh. 2015. The Renaming Problem: Recent Developments and Open Questions. http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/381\/361."},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC '13)","author":"Alistarh Dan","year":"2013","unstructured":"Dan Alistarh, James Aspnes, George Giakkoupis, and Philipp Woelfel. 2013. Randomized loose renaming in o(log log n) time. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC '13). ACM, 200\u2013209."},{"key":"e_1_3_2_1_4_1","volume-title":"The Complexity of Renaming. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS '11)","author":"Alistarh Dan","year":"2011","unstructured":"Dan Alistarh, James Aspnes, Seth Gilbert, and Rachid Guerraoui. 2011. The Complexity of Renaming. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS '11). IEEE, 718\u2013727."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611499"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767420"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79158"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 34th International Symposium on Distributed Computing (DISC '20)","author":"Augustine John","year":"2020","unstructured":"John Augustine, Valerie King, Anisur Rahaman Molla, Gopal Pandurangan, and Jared Saia. 2020. Scalable and Secure Computation Among Strangers: Message-Competitive Byzantine Protocols. In Proceedings of the 34th International Symposium on Distributed Computing (DISC '20). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 31:1\u201331:19."},{"key":"e_1_3_2_1_9_1","volume-title":"William K Moses Jr, and Gopal Pandurangan","author":"Augustine John","year":"2024","unstructured":"John Augustine, William K Moses Jr, and Gopal Pandurangan. 2024. Awake complexity of distributed minimum spanning tree. In International Colloquium on Structural Information and Communication Complexity (SIROCCO '24). Springer, 45\u201363."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3732772.3733561"},{"key":"e_1_3_2_1_11_1","unstructured":"Sirui Bai Xinyu Fu Yuyi Wang and Chaodong Zheng. 2026. Distributed Renaming with Subquadratic Bits via Scalable Committee Election. arXiv:2605.18086 https:\/\/arxiv.org\/abs\/2605.18086"},{"key":"e_1_3_2_1_12_1","volume-title":"Distributed graph coloring: Fundamentals and recent developments","author":"Barenboim Leonid","unstructured":"Leonid Barenboim and Michael Elkin. 2013. Distributed graph coloring: Fundamentals and recent developments. Morgan & Claypool Publishers."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3732772.3733518"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818936.2818949"},{"key":"e_1_3_2_1_15_1","unstructured":"Sharon Boeyen Stefan Santesson Tim Polk Russ Housley Stephen Farrell and David Cooper. 2008. Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile. RFC 5280. https:\/\/www.rfc-editor.org\/info\/rfc5280"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.14"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.42229"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.214134"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2011.04.001"},{"key":"e_1_3_2_1_20_1","volume-title":"Proceedings of the 25th Annual ACM symposium on Theory of Computing (STOC '93)","author":"Cooper Jason","year":"1993","unstructured":"Jason Cooper and Nathan Linial. 1993. Fast perfect-information leader-election protocol with linear immunity. In Proceedings of the 25th Annual ACM symposium on Theory of Computing (STOC '93). ACM, 662\u2013671."},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 2013 ACM symposium on Principles of distributed computing (PODC 13)","author":"Denysyuk Oksana","year":"2013","unstructured":"Oksana Denysyuk and Lu\u00eds Rodrigues. 2013. Byzantine renaming in synchronous systems with t < N. In Proceedings of the 2013 ACM symposium on Principles of distributed computing (PODC 13). ACM, 210\u2013219."},{"key":"e_1_3_2_1_22_1","volume-title":"Order-Preserving Renaming in Synchronous Systems with Byzantine Faults. In IEEE 33rd International Conference on Distributed Computing Systems (ICDCS '13)","author":"Denysyuk Oksana","year":"2013","unstructured":"Oksana Denysyuk and Lu\u00eds Rodrigues. 2013. Order-Preserving Renaming in Synchronous Systems with Byzantine Faults. In IEEE 33rd International Conference on Distributed Computing Systems (ICDCS '13). IEEE, 276\u2013285."},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings of the fourteenth annual ACM symposium on theory of computing (STOC '82)","author":"Dolev Danny","unstructured":"Danny Dolev and H. Raymond Strong. 1982. Polynomial algorithms for multiple processor agreement. In Proceedings of the fourteenth annual ACM symposium on theory of computing (STOC '82). ACM, 401\u2013407."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212045"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3732772.3733553"},{"key":"e_1_3_2_1_26_1","volume-title":"On the Number of Synchronous Rounds Sufficient for Authenticated Byzantine Agreement. In International Symposium on Distributed Computing (DISC '09)","author":"Fitzi Matthias","year":"2009","unstructured":"Matthias Fitzi and Jesper Buus Nielsen. 2009. On the Number of Synchronous Rounds Sufficient for Authenticated Byzantine Agreement. In International Symposium on Distributed Computing (DISC '09). Springer Berlin Heidelberg, 449\u2013463."},{"key":"e_1_3_2_1_27_1","volume-title":"Subconsensus Tasks: Renaming Is Weaker Than Set Agreement. In International Symposium on Distributed Computing (DISC '06)","author":"Gafni Eli","year":"2006","unstructured":"Eli Gafni, Sergio Rajsbaum, and Maurice Herlihy. 2006. Subconsensus Tasks: Renaming Is Weaker Than Set Agreement. In International Symposium on Distributed Computing (DISC '06). Springer Berlin Heidelberg, 329\u2013338."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.173"},{"key":"e_1_3_2_1_29_1","volume-title":"Kowalski","author":"Gilbert Seth","year":"2010","unstructured":"Seth Gilbert and Dariusz R. Kowalski. 2010. Distributed Agreement with Optimal Communication Complexity. In Proceedings of the 2010 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). SIAM, 965\u2013977."},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA '06)","author":"King Valerie","year":"2006","unstructured":"Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. 2006. Scalable leader election. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA '06). SIAM, 990\u2013999."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.77"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3631461.3631548"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538425"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_2"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-007-0045-x"},{"key":"e_1_3_2_1_37_1","volume-title":"Proceedings of the 26th Annual ACM symposium on Theory of Computing (STOC '94)","author":"Ostrovsky Rafail","year":"1994","unstructured":"Rafail Ostrovsky, Sridhar Rajagopalan, and Umesh Vazirani. 1994. Simple and efficient leader election in the full information model. In Proceedings of the 26th Annual ACM symposium on Theory of Computing (STOC '94). ACM, 234\u2013242."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1776"}],"event":{"name":"PODC '26: ACM Symposium on Principles of Distributed Computing","location":"Egham United Kingdom","acronym":"PODC '26","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3796701.3815915","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T16:49:27Z","timestamp":1782924567000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3796701.3815915"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7]]},"references-count":38,"alternative-id":["10.1145\/3796701.3815915","10.1145\/3796701"],"URL":"https:\/\/doi.org\/10.1145\/3796701.3815915","relation":{},"subject":[],"published":{"date-parts":[[2026,7]]},"assertion":[{"value":"2026-07-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}