{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T16:32:53Z","timestamp":1756571573717,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["805223"],"award-info":[{"award-number":["805223"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538435","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"246-256","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Near-Optimal Leader Election in Population Protocols on Graphs"],"prefix":"10.1145","author":[{"given":"Dan","family":"Alistarh","sequence":"first","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joel","family":"Rybicki","sequence":"additional","affiliation":[{"name":"IST Austria, Klosterneuburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sasha","family":"Voitovych","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1033113"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039855"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_38"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289137.3289150"},{"key":"e_1_3_2_1_6_1","volume-title":"Proc. 25th International Conference on Principles of Distributed Systems (OPODIS). https:\/\/arxiv.org\/abs\/2102","author":"Alistarh Dan","year":"2021","unstructured":"Dan Alistarh , Rati Gelashvili , and Joel Rybicki . 2021 . Fast graphical population protocols . In Proc. 25th International Conference on Principles of Distributed Systems (OPODIS). https:\/\/arxiv.org\/abs\/2102 .08808 Dan Alistarh, Rati Gelashvili, and Joel Rybicki. 2021. Fast graphical population protocols. In Proc. 25th International Conference on Principles of Distributed Systems (OPODIS). https:\/\/arxiv.org\/abs\/2102.08808"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Dan Alistarh Joel Rybicki and Sasha Voitovych. 2022. Near-Optimal Leader Election in Population Protocols on Graphs (Full Online Version). https:\/\/arxiv.org\/abs\/2205.12597  Dan Alistarh Joel Rybicki and Sasha Voitovych. 2022. Near-Optimal Leader Election in Population Protocols on Graphs (Full Online Version). https:\/\/arxiv.org\/abs\/2205.12597","DOI":"10.1145\/3519270.3538435"},{"key":"e_1_3_2_1_8_1","volume-title":"Proc. of the 12th Annual ACM Symposium on Theory of Computing (STOC). 82--93","author":"Angluin Dana","year":"1980","unstructured":"Dana Angluin . 1980 . Local and global properties in networks of processors . In Proc. of the 12th Annual ACM Symposium on Theory of Computing (STOC). 82--93 . Dana Angluin. 1980. Local and global properties in networks of processors. In Proc. of the 12th Annual ACM Symposium on Theory of Computing (STOC). 82--93."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11502593_8"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0138-3"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0067-z"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452001.1452003"},{"volume-title":"Middleware for Network Eccentric and Mobile Applications","author":"Aspnes James","key":"e_1_3_2_1_13_1","unstructured":"James Aspnes and Eric Ruppert . 2009. An introduction to population protocols . In Middleware for Network Eccentric and Mobile Applications . Springer , 97--120. James Aspnes and Eric Ruppert. 2009. An introduction to population protocols. In Middleware for Network Eccentric and Mobile Applications. Springer, 97--120."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03850-6_4"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384312"},{"key":"e_1_3_2_1_16_1","volume-title":"Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018","volume":"61","author":"Berenbrink Petra","year":"2018","unstructured":"Petra Berenbrink , Dominik Kaaser , Peter Kling , and Lena Otterbach . 2018 . Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018 ), Vol. 61 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 9:1--9:11. https:\/\/doi.org\/10.4230\/OASIcs.SOSA. 2018.9 10.4230\/OASIcs.SOSA.2018.9 Petra Berenbrink, Dominik Kaaser, Peter Kling, and Lena Otterbach. 2018. Simple and Efficient Leader Election. In 1st Symposium on Simplicity in Algorithms (SOSA 2018), Vol. 61. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 9:1--9:11. https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2018.9"},{"key":"e_1_3_2_1_17_1","volume-title":"Bounds on the cover time. Journal of Theoretical Probability 2 (06","author":"Broder Andrei","year":"1989","unstructured":"Andrei Broder and Anna Karlin . 1989. Bounds on the cover time. Journal of Theoretical Probability 2 (06 1989 ), 101--120. https:\/\/doi.org\/10.1007\/BF01048273 10.1007\/BF01048273 Andrei Broder and Anna Karlin. 1989. Bounds on the cover time. Journal of Theoretical Probability 2 (06 1989), 101--120. https:\/\/doi.org\/10.1007\/BF01048273"},{"key":"e_1_3_2_1_18_1","unstructured":"Cl\u00e9ment Canonne. 2019. A short note on Poisson tail bounds. http:\/\/www.cs.columbia.edu\/~ccanonne\/files\/misc\/2017-poissonconcentration.pdf Accessed January 27 2022.  Cl\u00e9ment Canonne. 2019. A short note on Poisson tail bounds. http:\/\/www.cs.columbia.edu\/~ccanonne\/files\/misc\/2017-poissonconcentration.pdf Accessed January 27 2022."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331616"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405733"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806745"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.135"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0281-z"},{"key":"e_1_3_2_1_25_1","volume-title":"Recent Results in Population Protocols for Exact Majority and Leader Election. Bulletin of the EATCS 126","author":"Els\u00e4sser Robert","year":"2018","unstructured":"Robert Els\u00e4sser and Tomasz Radzik . 2018. Recent Results in Population Protocols for Exact Majority and Leader Election. Bulletin of the EATCS 126 ( 2018 ). http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/549\/546 Robert Els\u00e4sser and Tomasz Radzik. 2018. Recent Results in Population Protocols for Exact Majority and Leader Election. Bulletin of the EATCS 126 (2018). http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/549\/546"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79992-4_24"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3424659"},{"key":"e_1_3_2_1_28_1","volume-title":"28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"68","author":"Giakkoupis George","year":"2011","unstructured":"George Giakkoupis . 2011 . Tight bounds for rumor spreading in graphs of a given conductance . In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 9), Thomas Schwentick and Christoph D\u00fcrr (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 57-- 68 . https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2011.57 10.4230\/LIPIcs.STACS.2011.57 George Giakkoupis. 2011. Tight bounds for rumor spreading in graphs of a given conductance. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 9), Thomas Schwentick and Christoph D\u00fcrr (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 57--68. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2011.57"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933117"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.169"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3323165.3323178"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2017.11.017"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01048274"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892324"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699440"},{"volume-title":"Interacting Particle Systems","author":"Liggett Thomas M.","key":"e_1_3_2_1_36_1","unstructured":"Thomas M. Liggett . 2005. Interacting Particle Systems . Springer-Verlag , Berlin, Heidelberg . https:\/\/doi.org\/10.1007\/b138374 10.1007\/b138374 Thomas M. Liggett. 2005. Interacting Particle Systems. Springer-Verlag, Berlin, Heidelberg. https:\/\/doi.org\/10.1007\/b138374"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.96.012313"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9245-4"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1142\/S012962642050005X"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2016.82"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331585"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2020.2991771"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1587\/transinf.2019FCP0003"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3076769"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64348-5_24"}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Salerno Italy","acronym":"PODC '22"},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538435","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538435","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538435"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":46,"alternative-id":["10.1145\/3519270.3538435","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538435","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}