{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T20:04:47Z","timestamp":1776888287426,"version":"3.51.2"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T00:00:00Z","timestamp":1659225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["RGPIN\u20132017\u201305936, RGPIN\u20132018\u201303899"],"award-info":[{"award-number":["RGPIN\u20132017\u201305936, RGPIN\u20132018\u201303899"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Research Chair in Distributed Computing of the Universit\u00e9 du Qu\u00e9bec en Outaouais"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>\n            Leader election is a fundamental task in distributed computing. It is a symmetry breaking problem, calling for one node of the network to become the\n            <jats:italic>leader<\/jats:italic>\n            , and for all other nodes to become\n            <jats:italic>non-leaders<\/jats:italic>\n            . We consider leader election in anonymous radio networks modeled as simple undirected connected graphs. Nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbours, or stay silent and listen. A node\n            <jats:italic>v<\/jats:italic>\n            hears a message from a neighbour\n            <jats:italic>w<\/jats:italic>\n            in a given round if\n            <jats:italic>v<\/jats:italic>\n            listens in this round and if\n            <jats:italic>w<\/jats:italic>\n            is its only neighbour transmitting in this round. If\n            <jats:italic>v<\/jats:italic>\n            listens in a round in which more than one neighbour transmits, then\n            <jats:italic>v<\/jats:italic>\n            hears noise that is different from any message and different from silence.\n          <\/jats:p>\n          <jats:p>\n            We assume that nodes are identical (anonymous) and execute the same deterministic algorithm. Under this scenario, symmetry can be broken only in one way: by different wake-up times of the nodes. In which situations is it possible to break symmetry and elect a leader using time as symmetry breaker? In order to answer this question, we consider\n            <jats:italic>configurations<\/jats:italic>\n            . A configuration is the underlying graph with nodes tagged by non-negative integers with the following meaning. A node can either wake up spontaneously in the round shown on its tag, according to some global clock, or can be woken up hearing a message sent by one of its already awoken neighbours. The local clock of a node starts at its wakeup and nodes do not have access to the global clock determining their tags. A configuration is\n            <jats:italic>feasible<\/jats:italic>\n            if there exists a distributed algorithm that elects a leader for this configuration.\n          <\/jats:p>\n          <jats:p>\n            Our main result is a complete algorithmic characterization of feasible configurations. More precisely, we design a centralized decision algorithm, working in polynomial time, whose input is a configuration and which decides if the configuration is feasible. Using this algorithm we also provide a dedicated deterministic distributed leader election algorithm for each feasible configuration that elects a leader for this configuration in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \u03c3, where\n            <jats:italic>n<\/jats:italic>\n            is the number of nodes and \u03c3 is the difference between the largest and smallest tag of the configuration. We then ask the question whether there exists a universal deterministic distributed algorithm electing a leader for all feasible configurations. The answer turns out to be no, and we show that such a universal algorithm cannot exist even for the class of 4-node feasible configurations. We also prove that a distributed version of our decision algorithm cannot exist.\n          <\/jats:p>","DOI":"10.1145\/3527171","type":"journal-article","created":{"date-parts":[[2022,3,26]],"date-time":"2022-03-26T11:15:55Z","timestamp":1648293355000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Deterministic Leader Election in Anonymous Radio Networks"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8231-3697","authenticated-orcid":false,"given":"Avery","family":"Miller","sequence":"first","affiliation":[{"name":"University of Manitoba, Manitoba, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[{"name":"Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau, Quebec, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ram Narayan","family":"Yadav","sequence":"additional","affiliation":[{"name":"Institute of Infrastructure Technology Research and Management, Ahmedabad, Gujarat, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804655"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90002-G"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48247"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90042-H"},{"key":"e_1_3_1_6_2","first-page":"16","volume-title":"Fourth Israel Symposium on Theory of Computing and Systems, ISTCS 1996, Jerusalem, Israel, June 10\u201312, 1996, Proceedings","author":"Boldi Paolo","year":"1996","unstructured":"Paolo Boldi, Shella Shammah, Sebastiano Vigna, Bruno Codenotti, Peter Gemmell, and Janos Simon. 1996. Symmetry breaking in anonymous networks: Characterizations. In Fourth Israel Symposium on Theory of Computing and Systems, ISTCS 1996, Jerusalem, Israel, June 10\u201312, 1996, Proceedings. IEEE Computer Society, 16\u201326."},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/301308.301355"},{"key":"e_1_3_1_8_2","volume-title":"A Formal Model for Message Passing Systems","author":"Burns J. E.","year":"1980","unstructured":"J. E. Burns. 1980. A Formal Model for Message Passing Systems. Technical Report TR-91. Computer Science Department, Indiana University."},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1056093"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0517-3"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45022-X_60"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35476-2_8"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00004-4"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00851-4"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087825"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1111322"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0196-x"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.70792"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-9982-0"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/2371077.2371079"},{"key":"e_1_3_1_21_2","series-title":"LIPIcs","first-page":"20:1\u201320:17","volume-title":"32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15\u201319, 2018","author":"Dufoulon Fabien","year":"2018","unstructured":"Fabien Dufoulon, Janna Burman, and Joffroy Beauquier. 2018. Beeping a deterministic time-optimal leader election. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15\u201319, 2018(LIPIcs, Vol. 121), Ulrich Schmid and Josef Widder (Eds.). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 20:1\u201320:17."},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1219944.1219954"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2003.11.007"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7919"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0131-y"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00292-4"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0011-z"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3039870"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.214125"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1978.1094204"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/359024.359029"},{"key":"e_1_3_1_32_2","first-page":"697","volume-title":"Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6\u20138, 2002, San Francisco, CA, USA","author":"Indyk Piotr","year":"2002","unstructured":"Piotr Indyk. 2002. Explicit constructions of selectors and related combinatorial structures, with applications. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6\u20138, 2002, San Francisco, CA, USA, David Eppstein (Ed.). ACM\/SIAM, 697\u2013704. http:\/\/dl.acm.org\/citation.cfm?id=545381.545475."},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0184-1"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571833"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.04.003"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279109"},{"key":"e_1_3_1_37_2","first-page":"155","volume-title":"Information Processing, Proceedings of the 7th IFIP Congress 1977, Toronto, Canada, August 8\u201312, 1977","author":"Lann G\u00e9rard Le","year":"1977","unstructured":"G\u00e9rard Le Lann. 1977. Distributed systems - towards a formal approach. In Information Processing, Proceedings of the 7th IFIP Congress 1977, Toronto, Canada, August 8\u201312, 1977, Bruce Gilchrist (Ed.). North-Holland, 155\u2013160."},{"key":"e_1_3_1_38_2","volume-title":"Distributed Algorithms","author":"Lynch Nancy A.","year":"1996","unstructured":"Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann."},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/69622.357194"},{"issue":"4","key":"e_1_3_1_40_2","first-page":"32","article-title":"Free synchronous packet access in a broadcast channel with feedback","volume":"14","author":"Tsybakov Boris Solomonovich","year":"1978","unstructured":"Boris Solomonovich Tsybakov and Viktor Alexandrovich Mikhailov. 1978. Free synchronous packet access in a broadcast channel with feedback. Problemy Peredachi Informatsii 14, 4 (1978), 32\u201359.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215032"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51687-5_52"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/71.481599"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3527171","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3527171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:01Z","timestamp":1750182661000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3527171"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,31]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3527171"],"URL":"https:\/\/doi.org\/10.1145\/3527171","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,31]]},"assertion":[{"value":"2020-07-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-15","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}