{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:38:46Z","timestamp":1773931126714,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NUS ODPRT","award":["R-252-000-C04-133"],"award-info":[{"award-number":["R-252-000-C04-133"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,11]]},"DOI":"10.1145\/3490148.3538586","type":"proceedings-article","created":{"date-parts":[[2022,7,10]],"date-time":"2022-07-10T22:10:15Z","timestamp":1657491015000},"page":"75-86","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["The Energy Complexity of Las Vegas Leader Election"],"prefix":"10.1145","author":[{"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]},{"given":"Shunhua","family":"Jiang","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90015-W"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.132"},{"key":"e_1_3_2_1_3_1","volume-title":"International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Amb\u00fchl Christoph","unstructured":"Christoph Amb\u00fchl . 2005. An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks . In International Colloquium on Automata, Languages, and Programming (ICALP) . Springer , 1139--1150. Christoph Amb\u00fchl. 2005. An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks. In International Colloquium on Automata, Languages, and Programming (ICALP). Springer, 1139--1150."},{"key":"e_1_3_2_1_4_1","volume-title":"Encyclopedia of Algorithms, Ming-Yang Kao (Ed.)","author":"Amb\u00fchl Christoph","unstructured":"Christoph Amb\u00fchl . 2008. Minimum Energy Broadcasting in Wireless Geometric Networks . In Encyclopedia of Algorithms, Ming-Yang Kao (Ed.) . Springer US , Boston, MA , 526--528. https:\/\/doi.org\/10.1007\/978-0--387--30162--4_233 10.1007\/978-0--387--30162--4_233 Christoph Amb\u00fchl. 2008. Minimum Energy Broadcasting in Wireless Geometric Networks. In Encyclopedia of Algorithms, Ming-Yang Kao (Ed.). Springer US, Boston, MA, 526--528. https:\/\/doi.org\/10.1007\/978-0--387--30162--4_233"},{"key":"e_1_3_2_1_5_1","volume-title":"William K Moses Jr, and Gopal Pandurangan","author":"Augustine John","year":"2022","unstructured":"John Augustine , William K Moses Jr, and Gopal Pandurangan . 2022 . Distributed MST Computation in the Sleeping Model : Awake-Optimal Algorithms and Lower Bounds . arXiv preprint arXiv:2204.08385 (2022). John Augustine, William K Moses Jr, and Gopal Pandurangan. 2022. Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds. arXiv preprint arXiv:2204.08385 (2022)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/171540.171571"},{"key":"e_1_3_2_1_7_1","volume-title":"Deterministic Logarithmic Completeness in the Distributed Sleeping Model. In 35th International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"19","author":"Barenboim Leonid","year":"2021","unstructured":"Leonid Barenboim and Tzalik Maimon . 2021 . Deterministic Logarithmic Completeness in the Distributed Sleeping Model. In 35th International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 209), Seth Gilbert (Ed.). Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 10:1--10: 19 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.10 10.4230\/LIPIcs.DISC.2021.10 Leonid Barenboim and Tzalik Maimon. 2021. Deterministic Logarithmic Completeness in the Distributed Sleeping Model. In 35th International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 209), Seth Gilbert (Ed.). Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 10:1--10:19. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.10"},{"key":"e_1_3_2_1_8_1","article-title":"Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel- Access Attempts, and Robustness","volume":"66","author":"Bender Michael A.","year":"2018","unstructured":"Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , and Maxwell Young . 2018 . Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel- Access Attempts, and Robustness . J. ACM 66 , 1, Article 6 (dec 2018). https:\/\/doi.org\/10.1145\/3276769 10.1145\/3276769 Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Maxwell Young. 2018. Scaling Exponential Backoff: Constant Throughput, Polylogarithmic Channel- Access Attempts, and Robustness. J. ACM 66, 1, Article 6 (dec 2018). https:\/\/doi.org\/10.1145\/3276769","journal-title":"J. ACM"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1158604"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.02.002"},{"key":"e_1_3_2_1_11_1","volume-title":"International Symposium on Algorithms and Computation. Springer, 533--542","author":"Caragiannis I.","unstructured":"I. Caragiannis , C. Galdi , and C. Kaklamanis . 2005. Basic computations in wireless networks . In International Symposium on Algorithms and Computation. Springer, 533--542 . I. Caragiannis, C. Galdi, and C. Kaklamanis. 2005. Basic computations in wireless networks. In International Symposium on Algorithms and Computation. Springer, 533--542."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341111"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212774"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405713"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461830"},{"key":"e_1_3_2_1_16_1","volume-title":"The Energy Complexity of Las Vegas Leader Election. arXiv preprint arXiv:2205.08642","author":"Chang Yi-Jun","year":"2022","unstructured":"Yi-Jun Chang and Shunhua Jiang . 2022. The Energy Complexity of Las Vegas Leader Election. arXiv preprint arXiv:2205.08642 ( 2022 ). Yi-Jun Chang and Shunhua Jiang. 2022. The Energy Complexity of Las Vegas Leader Election. arXiv preprint arXiv:2205.08642 (2022)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405718"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00851-4"},{"key":"e_1_3_2_1_19_1","volume-title":"Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks. arXiv preprint arXiv:2104.09096","author":"Dani Varsha","year":"2021","unstructured":"Varsha Dani , Aayush Gupta , Thomas P. Hayes , and Seth Pettie . 2021. Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks. arXiv preprint arXiv:2104.09096 ( 2021 ). Varsha Dani, Aayush Gupta, Thomas P. Hayes, and Seth Pettie. 2021. Wake Up and Join Me! An Energy-Efficient Algorithm for Maximal Matching in Radio Networks. arXiv preprint arXiv:2104.09096 (2021)."},{"key":"e_1_3_2_1_20_1","volume-title":"William K Moses Jr, and Gopal Pandurangan","author":"Dufoulon Fabien","year":"2022","unstructured":"Fabien Dufoulon , William K Moses Jr, and Gopal Pandurangan . 2022 . Sleeping is Superefficient : MIS in Exponentially Better Awake Complexity . arXiv preprint arXiv:2204.08359 (2022). Fabien Dufoulon, William K Moses Jr, and Gopal Pandurangan. 2022. Sleeping is Superefficient: MIS in Exponentially Better Awake Complexity. arXiv preprint arXiv:2204.08359 (2022)."},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN). 447--454","author":"Farach-Colton Mart\u00edn","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). 447--454 . https:\/\/doi.org\/10.1007\/11682462_42 10.1007\/11682462_42 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). 447--454. https:\/\/doi.org\/10.1007\/11682462_42"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75142-7_21"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376022"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467911"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571833"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the 8th Annual International Conference on Computing and Combinatorics (COCOON). 279--289","author":"Jurdzinski T.","unstructured":"T. Jurdzinski , M. Kutylowski , and J. Zatopianski . 2002. Energy-Efficient Size Approximation of Radio Networks with No Collision Detection . In Proceedings of the 8th Annual International Conference on Computing and Combinatorics (COCOON). 279--289 . https:\/\/doi.org\/10.1007\/3--540--45655--4_31 10.1007\/3--540--45655--4_31 T. Jurdzinski, M. Kutylowski, and J. Zatopianski. 2002. Energy-Efficient Size Approximation of Radio Networks with No Collision Detection. In Proceedings of the 8th Annual International Conference on Computing and Combinatorics (COCOON). 279--289. https:\/\/doi.org\/10.1007\/3--540--45655--4_31"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1144-3"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00223-0"},{"key":"e_1_3_2_1_29_1","volume-title":"Energy Tradeoffs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PDOC). Association for Computing Machinery","author":"Klonowski Marek","year":"2018","unstructured":"Marek Klonowski and Dominik Pajak . 2018 . Brief Announcement: Broadcast in Radio Networks, Time vs . Energy Tradeoffs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PDOC). Association for Computing Machinery , New York, NY, USA, 115--117. https:\/\/doi.org\/10.1145\/3212734.3212786 10.1145\/3212734.3212786 Marek Klonowski and Dominik Pajak. 2018. Brief Announcement: Broadcast in Radio Networks, Time vs. Energy Tradeoffs. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PDOC). Association for Computing Machinery, New York, NY, USA, 115--117. https:\/\/doi.org\/10.1145\/3212734.3212786"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.10.001"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2005.31"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-40996-3_31"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2002.1003864"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_18"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/MAES.2005.1499273"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCOSS.2016.40"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2710150.2710510"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215032"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2012.112"}],"event":{"name":"SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Philadelphia PA USA","acronym":"SPAA '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538586","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490148.3538586","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:10Z","timestamp":1750186930000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490148.3538586"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":39,"alternative-id":["10.1145\/3490148.3538586","10.1145\/3490148"],"URL":"https:\/\/doi.org\/10.1145\/3490148.3538586","relation":{},"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"2022-07-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}