{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:53:49Z","timestamp":1782971629286,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":49,"publisher":"ACM","funder":[{"name":"National Science Center, Poland (NCN)","award":["2020\/39\/B\/ST6\/03288"],"award-info":[{"award-number":["2020\/39\/B\/ST6\/03288"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,16]]},"DOI":"10.1145\/3732772.3733528","type":"proceedings-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:23:34Z","timestamp":1749824614000},"page":"510-520","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Improving Efficiency in Near-State and State-Optimal Self-Stabilising Leader Election Population Protocols"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1809-9814","authenticated-orcid":false,"given":"Leszek","family":"Gasieniec","sequence":"first","affiliation":[{"name":"University of Liverpool, Liverpool, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-0440-2511","authenticated-orcid":false,"given":"Tytus","family":"Grodzicki","sequence":"additional","affiliation":[{"name":"University of Wroclaw, Wroclaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3128-4689","authenticated-orcid":false,"given":"Grzegorz","family":"Stachowiak","sequence":"additional","affiliation":[{"name":"University of Wroclaw, Wroclaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"PODC'99","author":"Afek Y.","unstructured":"Y. Afek and M. Merritt. 1999. Fast, Wait-Free (2k)-Renaming. In PODC'99. 105\u2013112."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597630"},{"key":"e_1_3_2_1_3_1","volume-title":"Proc. SODA'17","author":"Alistarh D.","unstructured":"D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, and R.L. Rivest. 2017. Time-Space Trade-offs in Population Protocols. In Proc. SODA'17. 2560\u20132579."},{"key":"e_1_3_2_1_4_1","volume-title":"Proc. SODA'18","author":"Alistarh D.","unstructured":"D. Alistarh, J. Aspnes, and R. Gelashvili. 2018. Space-Optimal Majority in Population Protocols. In Proc. SODA'18. 2221\u20132239."},{"key":"e_1_3_2_1_5_1","volume-title":"Proc. DNA'23","author":"Alistarh D.","unstructured":"D. Alistarh, B. Dudek, A. Kosowski, D. Soloveichik, and P. Uznanski. 2017. Robust Detection in Leak-Prone Population Protocols. In Proc. DNA'23. 155\u2013171."},{"key":"e_1_3_2_1_6_1","volume-title":"Proc. ICALP'15","author":"Alistarh D.","unstructured":"D. Alistarh and R. Gelashvili. 2015. Polylogarithmic-Time Leader Election in Population Protocols. In Proc. ICALP'15. 479\u2013491."},{"key":"e_1_3_2_1_7_1","volume-title":"Proc. PODC'04","author":"Angluin D.","unstructured":"D. Angluin, J. Aspnes, Z. Diamadi, M.J. Fischer, and R. Peralta. 2004. Computation in networks of passively mobile finite-state sensors. In Proc. PODC'04. 290\u2013299."},{"key":"e_1_3_2_1_8_1","volume-title":"Proc. OPODIS'05","author":"Angluin D.","unstructured":"D. Angluin, J. Aspnes, M.J. Fischer, and H. Jiang. 2005. Self-stabilizing Population Protocols. In Proc. OPODIS'05. 103\u2013117."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.79158"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700366000"},{"key":"e_1_3_2_1_11_1","volume-title":"Proc. OPODIS'13","author":"Beauquier J.","unstructured":"J. Beauquier, P. Blanchard, and J. Burman. 2013. Self-stabilizing Leader Election in Population Protocols over Arbitrary Communication Graphs. In Proc. OPODIS'13. 38\u201352."},{"key":"e_1_3_2_1_12_1","volume-title":"Non-deterministic Population Protocols. In OPODIS'12","author":"Beauquier J.","unstructured":"J. Beauquier, J. Burman, L. Rosaz, and B. Rozoy. 2012. Non-deterministic Population Protocols. In OPODIS'12. 61\u201375."},{"key":"e_1_3_2_1_13_1","volume-title":"Proc. SSS'06'. 95\u2013109","author":"Beauquier J.","unstructured":"J. Beauquier, S. Dela\u00ebt, and S. Haddad. 2006. A 1-Strong Self-stabilizing Transformer. In Proc. SSS'06'. 95\u2013109."},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. PODC'99","author":"Beauquier J.","unstructured":"J. Beauquier, C. Genolini, and S. Kutten. 1999. Optimal Reactive k-Stabilization: The Case of Mutual Exclusion. In Proc. PODC'99. 209\u2013218."},{"key":"e_1_3_2_1_15_1","volume-title":"Proc. SAND'22","author":"Berenbrink P.","unstructured":"P. Berenbrink, F. Biermeier, C. Hahn, and D. Kaaser. 2022. Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem. In Proc. SAND'22."},{"key":"e_1_3_2_1_16_1","unstructured":"P. Berenbrink R. Els\u00e4sser T. G\u00f6tte L. Hintze and D. Kaaser. 2025. Silent Self-Stabilizing Ranking: Time Optimal and Space Efficient. CoRR abs\/2504.10417 (2025). To appear at ICDCS 2025."},{"key":"e_1_3_2_1_17_1","volume-title":"Proc. STOC'20","author":"Berenbrink P.","unstructured":"P. Berenbrink, G. Giakkoupis, and P. Kling. 2020. Optimal time and space leader election in population protocols. In Proc. STOC'20. 119\u2013129."},{"key":"e_1_3_2_1_18_1","volume-title":"Proc. SOSA'18","author":"Berenbrink P.","unstructured":"P. Berenbrink, D. Kaaser, P. Kling, and L. Otterbach. 2018. Simple and Efficient Leader Election. In Proc. SOSA'18. 9:1\u20139:11."},{"key":"e_1_3_2_1_19_1","volume-title":"Proc. PODC'17","author":"Bilke A.","unstructured":"A. Bilke, C. Cooper, R. Els\u00e4sser, and T. Radzik. 2017. Brief Announcement: Population Protocols for Leader Election and Exact Majority with O(log2 n) States and O(log2 n) Convergence Time. In Proc. PODC'17. 451\u2013453."},{"key":"e_1_3_2_1_20_1","volume-title":"PODC'93","author":"Borowsky E.","unstructured":"E. Borowsky and E. Gafni. 1993. Immediate Atomic Snapshots and Fast Renaming (Extended Abstract). In PODC'93. 41\u201351."},{"key":"e_1_3_2_1_21_1","unstructured":"J. Burman J. Beauquier and D. Sohier. 2019. Space-Optimal Naming in Population Protocols. In DISC19. 9:1\u20139:16."},{"key":"e_1_3_2_1_22_1","volume-title":"Proc. PODC'21","author":"Burman J.","unstructured":"J. Burman, H.-L. Chen, H.-P. Chen, D. Doty, T. Nowak, E.E. Severson, and C. Xu. 2021. Time-Optimal Self-Stabilizing Leader Election in Population Protocols. In Proc. PODC'21. 33\u201344."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9313-z"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.07.001"},{"key":"e_1_3_2_1_25_1","volume-title":"Proc. DISC'14","author":"Chen H-L","unstructured":"H-L Chen, R. Cummings, D. Doty, and D. Soloveichik. 2014. Speed Faults in Computation by Chemical Reaction Networks. In Proc. DISC'14. 16\u201330."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331616"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405733"},{"key":"e_1_3_2_1_28_1","volume-title":"PODC'08","author":"Chlebus B.S.","unstructured":"B.S. Chlebus and D.R. Kowalski. 2008. Asynchronous exclusive selection. In PODC'08. 375\u2013384."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.57"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0281-z"},{"key":"e_1_3_2_1_31_1","volume-title":"Waitfree Renaming with Optimal Name Space and High Throughput. In DISC'98","author":"Eberly W.","year":"1998","unstructured":"W. Eberly, L. Higham, and J\/ Warpechowska-Gruca. 1998. Long-Lived, Fast, Waitfree Renaming with Optimal Name Space and High Throughput. In DISC'98. 149\u2013160."},{"key":"e_1_3_2_1_32_1","volume-title":"Proc. OPODIS'06","author":"Fischer M.J.","unstructured":"M.J. Fischer and H. Jiang. 2006. Self-stabilizing Leader Election in Networks of Finite-State Anonymous Agents. In Proc. OPODIS'06. 395\u2013409."},{"key":"e_1_3_2_1_33_1","unstructured":"L. G\u0105sieniec T. Grodzicki and G. Stachowiak. 2025. Near-State and State-Optimal Self-Stabilising Leader Election Population Protocols. CoRR abs\/2502.01227 (2025)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2025.105265"},{"key":"e_1_3_2_1_35_1","unstructured":"L. G\u0105sieniec L. Kuszner E. Latif R. Parasuraman P.G. Spirakis and G. Stachowiak. 2024. Anonymous Distributed Localisation via Spatial Population Protocols. CoRR abs\/2411.08434 (2024)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3424659"},{"key":"e_1_3_2_1_37_1","volume-title":"Proc. SPAA'19","author":"G\u0105sieniec L.","unstructured":"L. G\u0105sieniec, G. Stachowiak, and P. Uzna\u0144ski. 2019. Almost Logarithmic-Time Space Optimal Leader Election in Population Protocols. In Proc. SPAA'19. 93\u2013102."},{"key":"e_1_3_2_1_38_1","volume-title":"Proc. SRDS'02","author":"Genolini C.","unstructured":"C. Genolini and S. Tixeuil. 2002. A lower bound on dynamic k-stabilization in asynchronous systems. In Proc. SRDS'02. 212\u2013221."},{"key":"e_1_3_2_1_39_1","volume-title":"Proc. WSS'99","author":"Gosh S.","year":"1999","unstructured":"S. Gosh. 1999. Xee. Scalable Self-stabilization. In Proc. WSS'99. 18\u201324."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331529"},{"key":"e_1_3_2_1_41_1","volume-title":"Proc. PODC '97","author":"Kutten S.","unstructured":"S. Kutten and B. Patt-Shamir. 1997. Time-adaptive self stabilization. In Proc. PODC '97. 149\u2013158."},{"key":"e_1_3_2_1_42_1","volume-title":"Proc. PODC'95","author":"Kutten S.","unstructured":"S. Kutten and D. Peleg. 1995. Fault-local distributed mending. In Proc. PODC'95. 20\u201327."},{"key":"e_1_3_2_1_43_1","volume-title":"Naming and Counting in Anonymous Unknown Dynamic Networks. In SSS'13","author":"Michail O.","unstructured":"O. Michail, I. Chatzigiannakis, and P.G. Spirakis. 2013. Naming and Counting in Anonymous Unknown Dynamic Networks. In SSS'13. 281\u2013295."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0173-9"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050045"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.09.034"},{"key":"e_1_3_2_1_47_1","volume-title":"Proc. SSS'13","author":"Xu X.","unstructured":"X. Xu, Y. Yamauchi, S. Kijima, and M. Yamashita. 2013. Space Complexity of Self-Stabilizing Leader Election in Population Protocol Based on k-Interaction. In Proc. SSS'13. 86\u201397."},{"key":"e_1_3_2_1_48_1","volume-title":"Proc. SSS'20","author":"Yokota D.","unstructured":"D. Yokota, Y. Sudo, and T. Masuzawa. 2020. Time-Optimal Self-stabilizing Leader Election on Rings in Population Protocols. In Proc. SSS'20. 301\u2013316."},{"key":"e_1_3_2_1_49_1","volume-title":"Proc. PODC'23","author":"Yokota D.","unstructured":"D. Yokota, Y. Sudo, F. Ooshita, and T. Masuzawa. 2023. A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Polylogarithmic Number of States. In Proc. PODC'23. 2\u201312."}],"event":{"name":"PODC '25: ACM Symposium on Principles of Distributed Computing","location":"Hotel Las Brisas Huatulco Huatulco Mexico","acronym":"PODC '25","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\/3732772.3733528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:23:50Z","timestamp":1749824630000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732772.3733528"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,13]]},"references-count":49,"alternative-id":["10.1145\/3732772.3733528","10.1145\/3732772"],"URL":"https:\/\/doi.org\/10.1145\/3732772.3733528","relation":{},"subject":[],"published":{"date-parts":[[2025,6,13]]},"assertion":[{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}