{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:38:38Z","timestamp":1773931118297,"version":"3.50.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T00:00:00Z","timestamp":1695686400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Walter Haefner Foundation, ETH Z\u00fcrich Foundation"},{"name":"Zhongguancun Haihua Institute for Frontier Information Technology"},{"name":"NSF CAREER","award":["CCF-1844887"],"award-info":[{"award-number":["CCF-1844887"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,10,31]]},"abstract":"<jats:p>\n            We consider the energy complexity of the leader election problem in the single-hop radio network model, where each device\n            <jats:italic>v<\/jats:italic>\n            has a unique identifier\n            <jats:sans-serif>ID<\/jats:sans-serif>\n            (\n            <jats:italic>v<\/jats:italic>\n            ) \u2208{ 1, 2, \u22d6 ,\n            <jats:italic>N<\/jats:italic>\n            } . Energy is a scarce resource for small battery-powered devices. For such devices, most of the energy is often spent on communication, not on computation. To approximate the actual energy cost, the energy complexity of an algorithm is defined as the maximum over all devices of the number of time slots where the device transmits or listens.\n          <\/jats:p>\n          <jats:p>\n            Much progress has been made in understanding the energy complexity of leader election in radio networks, but very little is known about the tradeoff between time and energy. Chang\u00a0et\u00a0al.\u00a0[STOC 2017] showed that the optimal deterministic energy complexity of leader election is \u0398 (log log\n            <jats:italic>N<\/jats:italic>\n            ) if each device can simultaneously transmit and listen but still leaving the problem of determining the optimal time complexity under any given energy constraint.\n            <jats:list list-type=\"none\">\n              <jats:list-item>\n                <jats:p>\n                  <jats:bold>Time\u2013energy tradeoff:<\/jats:bold>\n                  For any\n                  <jats:italic>k<\/jats:italic>\n                  \u2265 log log\n                  <jats:italic>N<\/jats:italic>\n                  , we show that a leader among at most\n                  <jats:italic>n<\/jats:italic>\n                  devices can be elected deterministically in\n                  <jats:italic>O<\/jats:italic>\n                  (\n                  <jats:italic>k<\/jats:italic>\n                  \u010b\n                  <jats:italic>n<\/jats:italic>\n                  <jats:sup>1+\u03b5<\/jats:sup>\n                  ) +\n                  <jats:italic>O<\/jats:italic>\n                  (\n                  <jats:italic>k<\/jats:italic>\n                  \u010b\n                  <jats:italic>N<\/jats:italic>\n                  <jats:sup>1\/k<\/jats:sup>\n                  ) time and\n                  <jats:italic>O<\/jats:italic>\n                  (\n                  <jats:italic>k<\/jats:italic>\n                  ) energy if each device can simultaneously transmit and listen, where \u03b5 &gt; 0 is any small constant. This improves upon the previous\n                  <jats:italic>O<\/jats:italic>\n                  (\n                  <jats:italic>N<\/jats:italic>\n                  )-time\n                  <jats:italic>O<\/jats:italic>\n                  (log log\n                  <jats:italic>N<\/jats:italic>\n                  )-energy algorithm by Chang\u00a0et\u00a0al.\u00a0[STOC 2017]. We provide lower bounds to show that the time\u2013energy tradeoff of our algorithm is near-optimal.\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:p>\n                  <jats:bold>Dense instances:<\/jats:bold>\n                  For the dense instances where the number of devices is\n                  <jats:italic>n<\/jats:italic>\n                  = \u0398 (\n                  <jats:italic>N<\/jats:italic>\n                  ), we design a deterministic leader election algorithm using only\n                  <jats:italic>O<\/jats:italic>\n                  (1) energy. This improves upon the\n                  <jats:italic>O<\/jats:italic>\n                  (log*\n                  <jats:italic>N<\/jats:italic>\n                  )-energy algorithm by Jurdzi\u0144ski, Kuty\u0142owski, and Zatopia\u0144ski\u00a0[PODC 2002] and the\n                  <jats:italic>O<\/jats:italic>\n                  (\u03b1 (\n                  <jats:italic>N<\/jats:italic>\n                  ))-energy algorithm by Chang et\u00a0al.\u00a0[STOC 2017]. More specifically, we show that the optimal deterministic energy complexity of leader election is\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Theta (\\max \\lbrace 1, \\log \\tfrac{N}{n}\\rbrace)\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  if each device cannot simultaneously transmit and listen, and it is\n                  <jats:inline-formula content-type=\"math\/tex\">\n                    <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(&amp;#x0398; (\\max \\lbrace 1, \\log \\log \\tfrac{N}{n}\\rbrace)\\)<\/jats:tex-math>\n                  <\/jats:inline-formula>\n                  if each device can simultaneously transmit and listen.\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>","DOI":"10.1145\/3614429","type":"journal-article","created":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T11:48:52Z","timestamp":1691668132000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Near-Optimal Time\u2013Energy Tradeoffs for Deterministic Leader Election"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0109-2432","authenticated-orcid":false,"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0934-0684","authenticated-orcid":false,"given":"Ran","family":"Duan","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2226-7980","authenticated-orcid":false,"given":"Shunhua","family":"Jiang","sequence":"additional","affiliation":[{"name":"Columbia University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,9,26]]},"reference":[{"issue":"2","key":"e_1_3_1_2_2","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1016\/0022-0000(91)90015-W","article-title":"A lower bound for radio broadcast","volume":"43","author":"Alon Noga","year":"1991","unstructured":"Noga Alon, Amotz Bar-Noy, Nathan Linial, and David Peleg. 1991. A lower bound for radio broadcast. J. Comput. Syst. Sci. 43, 2 (1991), 290\u2013298.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_1_3_2","first-page":"439","volume-title":"Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920)","author":"Andriambolamalala Ny Aina","year":"2020","unstructured":"Ny Aina Andriambolamalala and Vlady Ravelomanana. 2020. Transmitting once to elect a leader on wireless networks. In Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN\u201920). Springer International Publishing, Cham, 439\u2013450."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538459"},{"issue":"2","key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02259748","article-title":"Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection","volume":"5","author":"Bar-Yehuda Reuven","year":"1991","unstructured":"Reuven Bar-Yehuda, Oded Goldreich, and Alon Itai. 1991. Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection. Distrib. Comput. 5, 2 (1991), 67\u201371.","journal-title":"Distrib. Comput."},{"issue":"1","key":"e_1_3_1_6_2","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/0022-0000(92)90042-H","article-title":"On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization","volume":"45","author":"Bar-Yehuda Reuven","year":"1992","unstructured":"Reuven Bar-Yehuda, Oded Goldreich, and Alon Itai. 1992. On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. J. Comput. Syst. Sci. 45, 1 (1992), 104\u2013126.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_3_1_7_2","series-title":"Proceedings of the 35th International Symposium on Distributed Computing (DISC\u201921),","first-page":"10:1\u201310:19","volume":"209","author":"Barenboim Leonid","year":"2021","unstructured":"Leonid Barenboim and Tzalik Maimon. 2021. Deterministic logarithmic completeness in the distributed sleeping model. In Proceedings of the 35th International Symposium on Distributed Computing (DISC\u201921),Leibniz International Proceedings in Informatics (LIPIcs), Seth Gilbert (Ed.), Vol. 209. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 10:1\u201310:19. DOI:10.4230\/LIPIcs.DISC.2021.10"},{"key":"e_1_3_1_8_2","first-page":"325","volume-title":"Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201905)","author":"Bender Michael A.","year":"2005","unstructured":"Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, and Charles E. Leiserson. 2005. Adversarial contention resolution for simple channels. In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201905). Association for Computing Machinery, New York, NY, 325\u2013332. DOI:10.1145\/1073970.1074023"},{"key":"e_1_3_1_9_2","first-page":"499","volume-title":"Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC\u201916)","author":"Bender Michael A.","year":"2016","unstructured":"Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young. 2016. Contention resolution with log-logstar channel accesses. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC\u201916). Association for Computing Machinery, New York, NY, 499\u2013508. DOI:10.1145\/2897518.2897655"},{"issue":"5","key":"e_1_3_1_10_2","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1109\/TIT.1979.1056093","article-title":"Tree algorithms for packet broadcast channels","volume":"25","author":"Capetanakis J.","year":"1979","unstructured":"J. Capetanakis. 1979. Tree algorithms for packet broadcast channels. IEEE Trans. Inf. Theory 25, 5 (1979), 505\u2013515.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1145\/3212734.3212774","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201918)","author":"Chang Yi-Jun","year":"2018","unstructured":"Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, and Seth Pettie. 2018. The energy complexity of broadcast. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201918). ACM, 95\u2013104. DOI:10.1145\/3212734.3212774"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341111"},{"key":"e_1_3_1_13_2","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1145\/3382734.3405713","volume-title":"Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC\u201920)","author":"Chang Yi-Jun","year":"2020","unstructured":"Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, and Seth Pettie. 2020. The energy complexity of BFS in radio networks. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC\u201920). ACM, 273\u2013282. DOI:10.1145\/3382734.3405713"},{"key":"e_1_3_1_14_2","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1145\/3490148.3538586","volume-title":"Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures","author":"Chang Yi-Jun","year":"2022","unstructured":"Yi-Jun Chang and Shunhua Jiang. 2022. The energy complexity of las vegas leader election. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures. 75\u201386."},{"key":"e_1_3_1_15_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1145\/3382734.3405718","volume-title":"Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC\u201920)","author":"Chatterjee Soumyottam","year":"2020","unstructured":"Soumyottam Chatterjee, Robert Gmyr, and Gopal Pandurangan. 2020. Sleeping is efficient: MIS in \\(O(1)\\) -rounds node-averaged awake complexity. In Proceedings of the 39th Symposium on Principles of Distributed Computing (PODC\u201920). ACM, 99\u2013108. DOI:10.1145\/3382734.3405718"},{"issue":"1","key":"e_1_3_1_16_2","first-page":"401","article-title":"Randomized communication in radio networks","volume":"9","author":"Chlebus Bogdan S.","year":"2001","unstructured":"Bogdan S. Chlebus. 2001. Randomized communication in radio networks. Combin. Optim. Dordrecht 9, 1 (2001), 401\u2013456.","journal-title":"Combin. Optim. Dordrecht"},{"issue":"1","key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2071379.2071384","article-title":"Adversarial queuing on the multiple access channel","volume":"8","author":"Chlebus Bogdan S.","year":"2012","unstructured":"Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. 2012. Adversarial queuing on the multiple access channel. ACM Trans. Algor. 8, 1 (2012), 1\u201331.","journal-title":"ACM Trans. Algor."},{"issue":"1","key":"e_1_3_1_18_2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0304-3975(02)00851-4","article-title":"Distributed broadcast in radio networks of unknown topology","volume":"302","author":"Clementi A. E. F.","year":"2003","unstructured":"A. E. F. Clementi, A. Monti, and R. Silvestri. 2003. Distributed broadcast in radio networks of unknown topology. Theor. Comput. Sci. 302, 1 (2003), 337\u2013364.","journal-title":"Theor. Comput. Sci."},{"key":"e_1_3_1_19_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/3087801.3087825","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201917)","author":"Czumaj Artur","year":"2017","unstructured":"Artur Czumaj and Peter Davies. 2017. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201917). 3\u201312. DOI:10.1145\/3087801.3087825"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.08.001"},{"key":"e_1_3_1_21_2","doi-asserted-by":"crossref","unstructured":"Varsha Dani Aayush Gupta Thomas P. Hayes and Seth Pettie. 2023. Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks. Distributed Computing 36 3 (2023) 373\u2013384. 10.1007\/s00446-022-00426-w","DOI":"10.1007\/s00446-022-00426-w"},{"issue":"3","key":"e_1_3_1_22_2","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1137\/140982763","article-title":"Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel","volume":"44","author":"Marco Gianluca De","year":"2015","unstructured":"Gianluca De Marco and Dariusz R. Kowalski. 2015. Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel. SIAM J. Comput. 44, 3 (2015), 868\u2013888.","journal-title":"SIAM J. Comput."},{"key":"e_1_3_1_23_2","first-page":"472","volume-title":"Proceedings of the IEEE 39th International Conference on Distributed Computing Systems (ICDCS\u201919)","author":"Marco Gianluca De","year":"2019","unstructured":"Gianluca De Marco, Dariusz R. Kowalski, and Grzegorz Stachowiak. 2019. Deterministic contention resolution on a shared channel. In Proceedings of the IEEE 39th International Conference on Distributed Computing Systems (ICDCS\u201919). IEEE, 472\u2013482."},{"key":"e_1_3_1_24_2","first-page":"1009","volume-title":"Proceedings of the IEEE 41st International Conference on Distributed Computing Systems (ICDCS\u201921)","author":"Marco Gianluca De","year":"2021","unstructured":"Gianluca De Marco, Dariusz R Kowalski, and Grzegorz Stachowiak. 2021. Deterministic contention resolution without collision detection: Throughput vs energy. In Proceedings of the IEEE 41st International Conference on Distributed Computing Systems (ICDCS\u201921). IEEE, 1009\u20131019."},{"key":"e_1_3_1_25_2","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1145\/3087801.3087831","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing","author":"Marco Gianluca De","year":"2017","unstructured":"Gianluca De Marco and Grzegorz Stachowiak. 2017. Asynchronous shared channel. In Proceedings of the ACM Symposium on Principles of Distributed Computing. 391\u2013400."},{"key":"e_1_3_1_26_2","doi-asserted-by":"crossref","unstructured":"Fabien Dufoulon William K. Moses Jr and Gopal Pandurangan. 2023. Distributed MIS in O(Log Log n) awake complexity. Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC\u201923 Orlando FL USA) Association for Computing Machinery New York NY 135\u2013145. 10.1145\/3583668.3594574","DOI":"10.1145\/3583668.3594574"},{"key":"e_1_3_1_27_2","first-page":"447","volume-title":"Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN\u201906)","author":"Farach-Colton Mart\u00edn","year":"2006","unstructured":"Mart\u00edn Farach-Colton, Rohan J. Fernandes, and Miguel A. Mosteiro. 2006. Lower bounds for clear transmissions in radio networks. In Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN\u201906). 447\u2013454. DOI:10.1007\/11682462_42"},{"issue":"2","key":"e_1_3_1_28_2","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1109\/TIT.1985.1057022","article-title":"A perspective on multiaccess channels","volume":"31","author":"Gallager Robert","year":"1985","unstructured":"Robert Gallager. 1985. A perspective on multiaccess channels. IEEE Trans. Inf. Theory 31, 2 (1985), 124\u2013142.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"e_1_3_1_29_2","first-page":"748","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913)","author":"Ghaffari Mohsen","year":"2013","unstructured":"Mohsen Ghaffari and Bernhard Haeupler. 2013. Near optimal leader election in multi-hop radio networks. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913). 748\u2013766."},{"key":"e_1_3_1_30_2","first-page":"45","volume-title":"Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201922)","author":"Ghaffari Mohsen","year":"2022","unstructured":"Mohsen Ghaffari and Julian Portmann. 2022. Average awake complexity of MIS and matching. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201922). 45\u201355."},{"issue":"6","key":"e_1_3_1_31_2","doi-asserted-by":"crossref","first-page":"1048","DOI":"10.1145\/355541.355567","article-title":"Contention resolution with constant expected delay","volume":"47","author":"Goldberg Leslie Ann","year":"2000","unstructured":"Leslie Ann Goldberg, Philip D Mackenzie, Mike Paterson, and Aravind Srinivasan. 2000. Contention resolution with constant expected delay. J. ACM 47, 6 (2000), 1048\u20131096.","journal-title":"J. ACM"},{"issue":"2","key":"e_1_3_1_32_2","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1145\/23005.23006","article-title":"Estimating the multiplicities of conflicts to speed their resolution in multiple access channels","volume":"34","author":"Greenberg Albert G.","year":"1987","unstructured":"Albert G. Greenberg, Philippe Flajolet, and Richard E. Ladner. 1987. Estimating the multiplicities of conflicts to speed their resolution in multiple access channels. J. ACM 34, 2 (1987), 289\u2013325.","journal-title":"J. ACM"},{"key":"e_1_3_1_33_2","first-page":"383","volume-title":"Proceedings of the 24th Annual Symposium on Foundations of Computer Science (SFCS\u201983)","author":"Greenberg Albert G.","year":"1983","unstructured":"Albert G. Greenberg and Richard E. Landner. 1983. Estimating the multiplicities of conflicts in multiple access channels. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science (SFCS\u201983). IEEE, 383\u2013392."},{"issue":"3","key":"e_1_3_1_34_2","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1145\/3828.214125","article-title":"A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels","volume":"32","author":"Greenberg A. G.","year":"1985","unstructured":"A. G. Greenberg and S. Winograd. 1985. A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. J. ACM 32, 3 (1985), 589\u2013596.","journal-title":"J. ACM"},{"key":"e_1_3_1_35_2","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/2933057.2933121","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916)","author":"Haeupler Bernhard","year":"2016","unstructured":"Bernhard Haeupler and David Wajc. 2016. A faster distributed radio broadcast primitive. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916). ACM, 361\u2013370."},{"key":"e_1_3_1_36_2","first-page":"241","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing","author":"Hastad Johan","year":"1987","unstructured":"Johan Hastad, Tom Leighton, and Brian Rogoff. 1987. Analysis of backoff protocols for multiple access channels. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing. 241\u2013253."},{"issue":"8","key":"e_1_3_1_37_2","doi-asserted-by":"crossref","first-page":"1178","DOI":"10.1109\/TCOM.1978.1094204","article-title":"An adaptive technique for local distribution","volume":"26","author":"Hayes J. F.","year":"1978","unstructured":"J. F. Hayes. 1978. An adaptive technique for local distribution. IEEE Trans. Commun. 26, 8 (1978), 1178\u20131186.","journal-title":"IEEE Trans. Commun."},{"key":"e_1_3_1_38_2","first-page":"51","volume-title":"Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC\u201902)","author":"Jurdzi\u0144ski Tomasz","year":"2002","unstructured":"Tomasz Jurdzi\u0144ski, Miros\u0142aw Kuty\u0142owski, and Jan Zatopia\u0144ski. 2002. Efficient algorithms for leader election in radio networks. In Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC\u201902). 51\u201357. DOI:10.1145\/571825.571833"},{"issue":"11","key":"e_1_3_1_39_2","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1002\/cpe.783","article-title":"Weak communication in single-hop radio networks: Adjusting algorithms to industrial standards","volume":"15","author":"Jurdzi\u0144ski Tomasz","year":"2003","unstructured":"Tomasz Jurdzi\u0144ski, Miros\u0142aw Kuty\u0142owski, and Jan Zatopia\u0144ski. 2003. Weak communication in single-hop radio networks: Adjusting algorithms to industrial standards. Concurr. Comput.: Pract. Exp. 15, 11\u201312 (2003), 1117\u20131131.","journal-title":"Concurr. Comput.: Pract. Exp."},{"issue":"3","key":"e_1_3_1_40_2","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s00224-005-1144-3","article-title":"Probabilistic algorithms for the wake-up problem in single-hop radio networks","volume":"38","author":"Jurdzi\u0144ski Tomasz","year":"2005","unstructured":"Tomasz Jurdzi\u0144ski and Grzegorz Stachowiak. 2005. Probabilistic algorithms for the wake-up problem in single-hop radio networks. Theory Comput. Syst. 38, 3 (2005), 347\u2013367.","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"e_1_3_1_41_2","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1109\/TIT.1985.1057020","article-title":"An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels","volume":"31","author":"Koml\u00f3s J\u00e1nos","year":"1985","unstructured":"J\u00e1nos Koml\u00f3s and Albert Greenberg. 1985. An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Trans. Inf. Theory 31, 2 (1985), 302\u2013306.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"e_1_3_1_42_2","first-page":"158","volume-title":"Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing","author":"Kowalski Dariusz R.","year":"2005","unstructured":"Dariusz R. Kowalski. 2005. On selection problem in radio networks. In Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing. 158\u2013166."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0126-7"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279109"},{"issue":"7","key":"e_1_3_1_45_2","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1145\/360248.360253","article-title":"Ethernet: Distributed packet switching for local computer networks","volume":"19","author":"Metcalfe R. M.","year":"1976","unstructured":"R. M. Metcalfe and D. R. Boggs. 1976. Ethernet: Distributed packet switching for local computer networks. Commun. ACM 19, 7 (1976), 395\u2013404.","journal-title":"Commun. ACM"},{"key":"e_1_3_1_46_2","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1145\/1993806.1993838","volume-title":"Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing","author":"Mosteiro Miguel A","year":"2011","unstructured":"Miguel A Mosteiro, Antonio Fernandez Anta, and Jorge Ramon Munoz. 2011. Unbounded contention resolution in multiple-access channels. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. 211\u2013212."},{"key":"e_1_3_1_47_2","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1007\/3-540-40996-3_31","volume-title":"International Symposium on Algorithms and Computation (ISAAC\u201900)","author":"Nakano Koji","year":"2000","unstructured":"Koji Nakano and Stephan Olariu. 2000. Randomized leader election protocols in radio networks with no collision detection. In International Symposium on Algorithms and Computation (ISAAC\u201900). Springer, 362\u2013373."},{"issue":"5","key":"e_1_3_1_48_2","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1109\/TPDS.2002.1003864","article-title":"Uniform leader election protocols for radio networks","volume":"13","author":"Nakano Koji","year":"2002","unstructured":"Koji Nakano and Stephan Olariu. 2002. Uniform leader election protocols for radio networks. IEEE Trans. Parallel Distrib. Syst. 13, 5 (2002), 516\u2013526.","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"e_1_3_1_49_2","first-page":"258","volume-title":"Proceedings of the 28th International Symposium on Distributed Computing (DISC\u201914)","author":"Newport Calvin","year":"2014","unstructured":"Calvin Newport. 2014. Radio network lower bounds made easy. In Proceedings of the 28th International Symposium on Distributed Computing (DISC\u201914). 258\u2013272. DOI:10.1007\/978-3-662-45174-8_18"},{"key":"e_1_3_1_50_2","first-page":"229","volume-title":"Proceedings of the 27th Annual ACM Symposium on Theory of Computing","author":"Raghavan Prabhakar","year":"1995","unstructured":"Prabhakar Raghavan and Eli Upfal. 1995. Stochastic contention resolution with short delays. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing. 229\u2013237."},{"issue":"4","key":"e_1_3_1_51_2","first-page":"32","article-title":"Free synchronous packet access in a broadcast channel with feedback","volume":"14","author":"Tsybakov B. S.","year":"1978","unstructured":"B. S. Tsybakov and V. A. Mikhailov. 1978. Free synchronous packet access in a broadcast channel with feedback. Probl. Peredachi Inf. 14, 4 (1978), 32\u201359.","journal-title":"Probl. Peredachi Inf."},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215032"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3614429","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3614429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:30Z","timestamp":1750287030000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3614429"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,26]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,10,31]]}},"alternative-id":["10.1145\/3614429"],"URL":"https:\/\/doi.org\/10.1145\/3614429","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,26]]},"assertion":[{"value":"2022-02-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}