{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:53:47Z","timestamp":1782971627378,"version":"3.54.5"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T00:00:00Z","timestamp":1605571200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["DEC-2012\/06\/M\/ST6\/00459"],"award-info":[{"award-number":["DEC-2012\/06\/M\/ST6\/00459"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,2,28]]},"abstract":"<jats:p>\n            The model of\n            <jats:italic>population protocols<\/jats:italic>\n            refers to the growing in popularity theoretical framework suitable for studying\n            <jats:italic>pairwise interactions<\/jats:italic>\n            within a large collection of simple indistinguishable entities, frequently called\n            <jats:italic>agents<\/jats:italic>\n            . In this article, the emphasis is on the space complexity of fast\n            <jats:italic>leader election<\/jats:italic>\n            in population protocols governed by the\n            <jats:italic>random scheduler<\/jats:italic>\n            , which uniformly at random selects pairwise interactions between\n            <jats:italic>n<\/jats:italic>\n            agents.\n          <\/jats:p>\n          <jats:p>\n            One of the main results of this article is the first fast space optimal\n            <jats:italic>leader election protocol<\/jats:italic>\n            , which works with high probability. The new protocol operates in\n            <jats:italic>parallel time<\/jats:italic>\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) equivalent to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) sequential\n            <jats:italic>pairwise interactions<\/jats:italic>\n            with each agent\u2019s memory space limited to\n            <jats:italic>O<\/jats:italic>\n            (log log\n            <jats:italic>n<\/jats:italic>\n            ) states. This double logarithmic space utilisation matches asymptotically the lower bound \u00bdlog log\n            <jats:italic>n<\/jats:italic>\n            on the number of states utilised by agents in any leader election algorithm with the running time\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \\polylog\n            <jats:italic>n<\/jats:italic>\n            ); see Reference [7].\n          <\/jats:p>\n          <jats:p>Our new solution expands also on the classical concept of phase clocks used to synchronise and to coordinate computations in distributed algorithms. In particular, we formalise the concept and provide a rigorous analysis of phase clocks operating in nested modes. Our arguments are also valid for phase clocks propelled by multiple leaders. The combination of the two results in the first time-space efficient leader election algorithm. We also provide a complete formal argumentation, indicating that our solution is always correct, fast, and it works with high probability.<\/jats:p>","DOI":"10.1145\/3424659","type":"journal-article","created":{"date-parts":[[2020,11,25]],"date-time":"2020-11-25T03:07:47Z","timestamp":1606273667000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election"],"prefix":"10.1145","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1809-9814","authenticated-orcid":false,"given":"Leszek","family":"G\u0105sieniec","sequence":"first","affiliation":[{"name":"University of Liverpool and Augusta University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3128-4689","authenticated-orcid":false,"given":"Grzegorz","family":"Stachowiak","sequence":"additional","affiliation":[{"name":"Uniwersytet Wroc\u0142awski"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,17]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"Tight lower bounds for data-dependent locality-sensitive hashing","volume":"9","author":"Andoni A.","year":"2016","unstructured":"A. Andoni and I. P. Razenshteyn . 2016 . Tight lower bounds for data-dependent locality-sensitive hashing . In Proceedings of the Symposium on Computational Geometry. 9 : 1 -- 9 :11. A. Andoni and I. P. Razenshteyn. 2016. Tight lower bounds for data-dependent locality-sensitive hashing. In Proceedings of the Symposium on Computational Geometry. 9:1--9:11.","journal-title":"Proceedings of the Symposium on Computational Geometry."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC\u201980)","author":"Angluin D.","year":"1980","unstructured":"D. Angluin . 1980 . Local and global properties in networks of processors . In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC\u201980) . 82--93. D. Angluin. 1980. Local and global properties in networks of processors. In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC\u201980). 82--93."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC\u201904)","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 Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC\u201904) . 290--299. D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. 2004. Computation in networks of passively mobile finite-state sensors. In Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC\u201904). 290--299."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0138-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0067-z"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-008-0059-z"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","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 Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917) . 2560--2579. D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, and R. L. Rivest. 2017. Time-space trade-offs in population protocols. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). 2560--2579."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Alistarh D.","unstructured":"D. Alistarh , J. Aspnes , and R. Gelashvili . 2018. Space-optimal majority in population protocols . In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918) . 2221--2239. D. Alistarh, J. Aspnes, and R. Gelashvili. 2018. Space-optimal majority in population protocols. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918). 2221--2239."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915)","author":"Alistarh D.","unstructured":"D. Alistarh and R. Gelashvili . 2015. Polylogarithmic-time leader election in population protocols . In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915) . 479--491. D. Alistarh and R. Gelashvili. 2015. Polylogarithmic-time leader election in population protocols. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP\u201915). 479--491."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289137.3289150"},{"key":"e_1_2_1_11_1","first-page":"71","article-title":"Maintaining digital clocks in step. In Proceedings of the 5th International Workshop on Distributed Algorithms","volume":"579","author":"Arora A.","year":"1991","unstructured":"A. Arora , S. Dolev , and M. G. Gouda . 1991 . Maintaining digital clocks in step. In Proceedings of the 5th International Workshop on Distributed Algorithms . LNCS 579 , 71 -- 79 . A. Arora, S. Dolev, and M. G. Gouda. 1991. Maintaining digital clocks in step. In Proceedings of the 5th International Workshop on Distributed Algorithms. LNCS 579, 71--79.","journal-title":"LNCS"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90002-G"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48247"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915)","author":"Becchetti L.","unstructured":"L. Becchetti , A. E. F. Clementi , E. Natale , F. Pasquale , and R. Silvestri . 2015. Plurality consensus in the gossip model . In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915) . 371--390. L. Becchetti, A. E. F. Clementi, E. Natale, F. Pasquale, and R. Silvestri. 2015. Plurality consensus in the gossip model. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201915). 371--390."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC\u201920)","author":"Ben Nun S.","unstructured":"S. Ben Nun , T. Kopelowitz , M. Kraus , and E. Porat . 2020. An O(log3\/2 n) parallel time population protocol for majority with O(log n) states . In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC\u201920) . 191--199. S. Ben Nun, T. Kopelowitz, M. Kraus, and E. Porat. 2020. An O(log3\/2 n) parallel time population protocol for majority with O(log n) states. In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC\u201920). 191--199."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing. DISC 2018, 10:1--10:18","author":"Berenbrink P.","unstructured":"P. Berenbrink , R. Els\u00e4sser , T. Friedetzky , D. Kaaser , P. Kling , and T. Radzik . 2018. A population protocol for exact majority with O(log5\/3 n) stabilization time and \u019f((log n) states . In Proceedings of the 32nd International Symposium on Distributed Computing. DISC 2018, 10:1--10:18 . P. Berenbrink, R. Els\u00e4sser, T. Friedetzky, D. Kaaser, P. Kling, and T. Radzik. 2018. A population protocol for exact majority with O(log5\/3 n) stabilization time and \u019f((log n) states. In Proceedings of the 32nd International Symposium on Distributed Computing. DISC 2018, 10:1--10:18."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Berenbrink P.","unstructured":"P. Berenbrink , T. Friedetzky , G. Giakkoupis , and P. Kling . 2016. Efficient plurality consensus, or: The benefits of cleaning up from time to time . In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916) . 1--14. P. Berenbrink, T. Friedetzky, G. Giakkoupis, and P. Kling. 2016. Efficient plurality consensus, or: The benefits of cleaning up from time to time. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916). 1--14."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the Symposium on Simplicity in Algorithms (SOSA\u201918)","author":"Berenbrink P.","unstructured":"P. Berenbrink , D. Kaaser , P. Kling , and L. Otterbach . 2018. Simple and efficient leader election . In Proceedings of the Symposium on Simplicity in Algorithms (SOSA\u201918) . 9:1--9:11. P. Berenbrink, D. Kaaser, P. Kling, and L. Otterbach. 2018. Simple and efficient leader election. In Proceedings of the Symposium on Simplicity in Algorithms (SOSA\u201918). 9:1--9:11."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC\u201920)","author":"Berenbrink P.","unstructured":"P. Berenbrink , G. Giakkoupis , and P. Kling . 2020. Optimal time and space leader election in population protocols . In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC\u201920) . 119--129. P. Berenbrink, G. Giakkoupis, and P. Kling. 2020. Optimal time and space leader election in population protocols. In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC\u201920). 119--129."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 36th ACM Symp. on Principles of Distributed Computing (PODC\u201917)","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 Proceedings of the 36th ACM Symp. on Principles of Distributed Computing (PODC\u201917) . 451--453. 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 Proceedings of the 36th ACM Symp. on Principles of Distributed Computing (PODC\u201917). 451--453."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 4th Israel Symposium on Theory of Computing and Systems (ISTCS\u201996)","author":"Boldi P.","unstructured":"P. Boldi , S. Shammah , S. Vigna , B. Codenotti , P. Gemmell , and J. Simon . 1996. Symmetry breaking in anonymous networks: Characterizations . In Proceedings of the 4th Israel Symposium on Theory of Computing and Systems (ISTCS\u201996) . 16--26. P. Boldi, S. Shammah, S. Vigna, B. Codenotti, P. Gemmell, and J. Simon. 1996. Symmetry breaking in anonymous networks: Characterizations. In Proceedings of the 4th Israel Symposium on Theory of Computing and Systems (ISTCS\u201996). 16--26."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 18th ACM Symposium on Principles of Distributed Computing (PODC\u201999)","author":"Boldi P.","unstructured":"P. Boldi and S. Vigna . 1999. Computing anonymously with arbitrary knowledge . In Proceedings of the 18th ACM Symposium on Principles of Distributed Computing (PODC\u201999) . 181--188. P. Boldi and S. Vigna. 1999. Computing anonymously with arbitrary knowledge. In Proceedings of the 18th ACM Symposium on Principles of Distributed Computing (PODC\u201999). 181--188."},{"key":"e_1_2_1_24_1","volume-title":"A Formal Model for Message Passing Systems","author":"Burns J. E.","unstructured":"J. E. Burns . 1980. A Formal Model for Message Passing Systems . Technical Report TR-91, Computer Science Department, Indiana University , Bloomington, IN. J. E. Burns. 1980. A Formal Model for Message Passing Systems. Technical Report TR-91, Computer Science Department, Indiana University, Bloomington, IN."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 22nd International Conference DNA Computing and Molecular Programming (DNA\u201916)","author":"Cardelli L.","unstructured":"L. Cardelli , M. Kwiatkowska , and L. Laurenti . 2016. Programming discrete distributions with chemical reaction networks . In Proceedings of the 22nd International Conference DNA Computing and Molecular Programming (DNA\u201916) . 35--51. L. Cardelli, M. Kwiatkowska, and L. Laurenti. 2016. Programming discrete distributions with chemical reaction networks. In Proceedings of the 22nd International Conference DNA Computing and Molecular Programming (DNA\u201916). 35--51."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 7th ACM ACM SIGACT\/SIGMOBILE International Workshop on Foundations of Mobile Computing. 6--15","author":"Chatzigiannakis I.","unstructured":"I. Chatzigiannakis , O. Michail , S. Nikolaou , A. Pavlogiannis , and P. G. Spirakis . 2011. Passively mobile communicating machines that use restricted space . In Proceedings of the 7th ACM ACM SIGACT\/SIGMOBILE International Workshop on Foundations of Mobile Computing. 6--15 . I. Chatzigiannakis, O. Michail, S. Nikolaou, A. Pavlogiannis, and P. G. Spirakis. 2011. Passively mobile communicating machines that use restricted space. In Proceedings of the 7th ACM ACM SIGACT\/SIGMOBILE International Workshop on Foundations of Mobile Computing. 6--15."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"H.-L. Chen R. Cummings D. Doty and D. Soloveichik. 2014. Speed faults in computation by chemical reaction networks. In Distributed Computing. Springer 16--30.  H.-L. Chen R. Cummings D. Doty and D. Soloveichik. 2014. Speed faults in computation by chemical reaction networks. In Distributed Computing. Springer 16--30.","DOI":"10.1007\/978-3-662-45174-8_2"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0196-x"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2371077.2371079"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017460.1017463"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.57"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the Conference on Self-Stabilizing Systems (SSS\u201903)","author":"Daliot A.","unstructured":"A. Daliot , D. Dolev , and H. Parnas . 2003 Self-stabilizing pulse synchronization inspired by biological pacemaker networks . In Proceedings of the Conference on Self-Stabilizing Systems (SSS\u201903) . 32--48. A. Daliot, D. Dolev, and H. Parnas. 2003 Self-stabilizing pulse synchronization inspired by biological pacemaker networks. In Proceedings of the Conference on Self-Stabilizing Systems (SSS\u201903). 32--48."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 29th International Symposium on Distributed Computing. DISC 2015, 602--616","author":"Doty D.","unstructured":"D. Doty and D. Soloveichik . 2015. Stable leader election in population protocols requires linear time . In Proceedings of the 29th International Symposium on Distributed Computing. DISC 2015, 602--616 . D. Doty and D. Soloveichik. 2015. Stable leader election in population protocols requires linear time. In Proceedings of the 29th International Symposium on Distributed Computing. DISC 2015, 602--616."},{"key":"e_1_2_1_34_1","unstructured":"R. Els\u00e4sser and T. Radzik. 2018. Recent results in population protocols for exact majority and leader election. EATCS Bull. 126 (2018).  R. Els\u00e4sser and T. Radzik. 2018. Recent results in population protocols for exact majority and leader election. EATCS Bull. 126 (2018)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2003.11.007"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7919"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 20th Annual European Symposium on Algorithms (ESA\u201912)","author":"Fusco E.","unstructured":"E. Fusco and A. Pelc . 2012. Knowledge, level of symmetry, and time of leader election . In Proceedings of the 20th Annual European Symposium on Algorithms (ESA\u201912) . 479--490. E. Fusco and A. Pelc. 2012. Knowledge, level of symmetry, and time of leader election. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA\u201912). 479--490."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118756.3119007"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems. SSS 2015, 67--80","author":"G\u0105sieniec L.","unstructured":"L. G\u0105sieniec , D. D. Hamilton , R. Martin , and P. G. Spirakis . 2015. The match-maker: Constant space distributed majority via random walks . In Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems. SSS 2015, 67--80 . L. G\u0105sieniec, D. D. Hamilton, R. Martin, and P. G. Spirakis. 2015. The match-maker: Constant space distributed majority via random walks. In Proceedings of the 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems. SSS 2015, 67--80."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the International Conference on Principles of Distributed Systems (OPODIS\u201916)","author":"G\u0105sieniec L.","unstructured":"L. G\u0105sieniec , D. Hamilton , R. Martin1, P. G. Spirakis , and G. Stachowiak . 2016. Deterministic population protocols for exact majority and plurality . In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS\u201916) . 14:1--14:14. L. G\u0105sieniec, D. Hamilton, R. Martin1, P. G. Spirakis, and G. Stachowiak. 2016. Deterministic population protocols for exact majority and plurality. In Proceedings of the International Conference on Principles of Distributed Systems (OPODIS\u201916). 14:1--14:14."},{"key":"e_1_2_1_41_1","unstructured":"L. G\u0105sieniec G. Stachowiak and Przemys\u0142aw Uzna\u0144ski. [n.d.]. Almost logarithmic-time space optimal leader election in population protocols. Retrieved from https:\\\\arXiv:1802.06867.  L. G\u0105sieniec G. Stachowiak and Przemys\u0142aw Uzna\u0144ski. [n.d.]. Almost logarithmic-time space optimal leader election in population protocols. Retrieved from https:\\\\arXiv:1802.06867."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 34th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201916)","author":"Ghaffari M.","unstructured":"M. Ghaffari and M. Parter . 2016. A polylogarithmic gossip algorithm for plurality consensus . In Proceedings of the 34th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201916) . 117--126. M. Ghaffari and M. Parter. 2016. A polylogarithmic gossip algorithm for plurality consensus. In Proceedings of the 34th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201916). 117--126."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Glacet Ch.","unstructured":"Ch. Glacet , A. Miller , and A. Pelc . 2016. Time vs. information tradeoffs for leader election in anonymous trees . In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916) . 600--609 Ch. Glacet, A. Miller, and A. Pelc. 2016. Time vs. information tradeoffs for leader election in anonymous trees. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). 600--609"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 6th ACS\/IEEE International Conference on Computer Systems and Applications (AICCSA\u201908)","author":"Haddar M. A.","unstructured":"M. A. Haddar , A. H. Kacem , Y. M\u00e9tivier , M. Mosbah , and M. Jmaiel . 2008. Electing a leader in the local computation model using mobile agents . In Proceedings of the 6th ACS\/IEEE International Conference on Computer Systems and Applications (AICCSA\u201908) . 473--480. M. A. Haddar, A. H. Kacem, Y. M\u00e9tivier, M. Mosbah, and M. Jmaiel. 2008. Electing a leader in the local computation model using mobile agents. In Proceedings of the 6th ACS\/IEEE International Conference on Computer Systems and Applications (AICCSA\u201908). 473--480."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.888644"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/359024.359029"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the IFIP Congress. 155--160","author":"Le Lann G.","year":"1977","unstructured":"G. Le Lann . 1977 . Distributed systems\u2014Towards a formal approach . In Proceedings of the IFIP Congress. 155--160 . G. Le Lann. 1977. Distributed systems\u2014Towards a formal approach. In Proceedings of the IFIP Congress. 155--160."},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the IEEE 14th International Symposium on Network Computing and Applications (NCA\u201915)","author":"Mocquard Y.","unstructured":"Y. Mocquard , E. Anceaume , J. Aspnes , Y. Busnel , and B. Sericola . 2015. Counting with population protocols . Proceedings of the IEEE 14th International Symposium on Network Computing and Applications (NCA\u201915) . 35--42. Y. Mocquard, E. Anceaume, J. Aspnes, Y. Busnel, and B. Sericola. 2015. Counting with population protocols. Proceedings of the IEEE 14th International Symposium on Network Computing and Applications (NCA\u201915). 35--42."},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914)","author":"Mertzios G. B.","unstructured":"G. B. Mertzios , S. E. Nikoletseas , C. Raptopoulos , and P. G. Spirakis . 2014. Determining majority in networks with local interactions and very small local memory . In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914) . 871--882. G. B. Mertzios, S. E. Nikoletseas, C. Raptopoulos, and P. G. Spirakis. 2014. Determining majority in networks with local interactions and very small local memory. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914). 871--882."},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 32nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201914)","author":"Michail O.","unstructured":"O. Michail and P. G. Spirakis . 2014. Simple and efficient local codes for distributed stable network construction . In Proceedings of the 32nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201914) . 76--85. O. Michail and P. G. Spirakis. 2014. Simple and efficient local codes for distributed stable network construction. In Proceedings of the 32nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201914). 76--85."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/69622.357194"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the 3rd Workshop on Distributed Algorithms (WDAG\u201989)","author":"Yamashita M.","unstructured":"M. Yamashita and T. Kameda . 1989. Electing a leader when procesor identity numbers are not distinct . In Proceedings of the 3rd Workshop on Distributed Algorithms (WDAG\u201989) . 303--314. M. Yamashita and T. Kameda. 1989. Electing a leader when procesor identity numbers are not distinct. In Proceedings of the 3rd Workshop on Distributed Algorithms (WDAG\u201989). 303--314."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.481599"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3424659","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3424659","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:31Z","timestamp":1750202611000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3424659"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,17]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2,28]]}},"alternative-id":["10.1145\/3424659"],"URL":"https:\/\/doi.org\/10.1145\/3424659","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,17]]},"assertion":[{"value":"2018-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}