{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,25]],"date-time":"2026-08-25T08:09:09Z","timestamp":1787645349713,"version":"build-2736575974"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T00:00:00Z","timestamp":1611792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Centre for Discrete Mathematics and its Applications"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>\n            We study two fundamental communication primitives:\n            <jats:italic>broadcasting<\/jats:italic>\n            and\n            <jats:italic>leader election<\/jats:italic>\n            in the classical model of multi-hop radio networks with unknown topology and without collision detection mechanisms. It has been known for almost 20 years that in undirected networks with\n            <jats:italic>n<\/jats:italic>\n            nodes and diameter\n            <jats:italic>D<\/jats:italic>\n            , randomized broadcasting requires \u03a9(\n            <jats:italic>D<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>D<\/jats:italic>\n            + log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) rounds, assuming that uninformed nodes are not allowed to communicate (until they are informed). Only very recently, Haeupler and Wajc (PODC'2016) showed that this bound can be improved for the model with spontaneous transmissions, providing an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\n            \/log\n            <jats:italic>D<\/jats:italic>\n            + log\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-time broadcasting algorithm. In this article, we give a new and faster algorithm that completes broadcasting in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            \/log\n            <jats:italic>D<\/jats:italic>\n            + log\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time, succeeding with high probability. This yields the first optimal\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            )-time broadcasting algorithm whenever\n            <jats:italic>n<\/jats:italic>\n            is polynomial in\n            <jats:italic>D<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Furthermore, our approach can be applied to design a new leader election algorithm that matches the performance of our broadcasting algorithm. Previously, all fast randomized leader election algorithms have used broadcasting as a subroutine and their complexity has been asymptotically strictly larger than the complexity of broadcasting. In particular, the fastest previously known randomized leader election algorithm of Ghaffari and Haeupler (SODA'2013) requires\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>D<\/jats:italic>\n            min {log log\n            <jats:italic>n<\/jats:italic>\n            , log\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>D<\/jats:italic>\n            } + log\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-time, succeeding with high probability. Our new algorithm again requires\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            \/log\n            <jats:italic>D<\/jats:italic>\n            + log\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time, also succeeding with high probability.\n          <\/jats:p>","DOI":"10.1145\/3446383","type":"journal-article","created":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T23:09:32Z","timestamp":1611875372000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks"],"prefix":"10.1145","volume":"68","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Davies","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,1,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90015-W"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02259748"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90042-H"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s446-002-8028-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35476-2_8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00851-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1111322"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.02.027"},{"key":"e_1_2_1_9_1","first-page":"2","article-title":"Broadcasting algorithms in radio networks with unknown topology","volume":"60","author":"Czumaj Artur","year":"2003","journal-title":"J. Algor."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.54"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0230-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933121"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073843"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0126-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279109"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77115-9_1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446383","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3446383","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:27Z","timestamp":1750191447000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446383"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,28]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3446383"],"URL":"https:\/\/doi.org\/10.1145\/3446383","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,28]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}