{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:39:17Z","timestamp":1773931157389,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T00:00:00Z","timestamp":1686873600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1540512"],"award-info":[{"award-number":["CCF-1540512"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["IIS-1633720"],"award-info":[{"award-number":["IIS-1633720"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1717075"],"award-info":[{"award-number":["CCF-1717075"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"BSF","award":["2016419"],"award-info":[{"award-number":["2016419"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,19]]},"DOI":"10.1145\/3583668.3594574","type":"proceedings-article","created":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T22:28:38Z","timestamp":1686954518000},"page":"135-145","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Distributed MIS in O(log log n) Awake Complexity"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2977-4109","authenticated-orcid":false,"given":"Fabien","family":"Dufoulon","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Houston, Houston, Texas, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4533-7593","authenticated-orcid":false,"suffix":"Jr.","given":"William K.","family":"Moses","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Durham University, Durham, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5833-6592","authenticated-orcid":false,"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Houston, Houston, Texas, United States of America"}]}],"member":"320","published-online":{"date-parts":[[2023,6,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538459"},{"key":"e_1_3_2_1_3_1","volume-title":"Lower Bounds for Maximal Matchings and Maximal Independent Sets","author":"Balliu Alkida","unstructured":"Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mika\u00ebl Rabie, and Jukka Suomela. 2019. Lower Bounds for Maximal Matchings and Maximal Independent Sets. In IEEE FOCS. 481--497."},{"key":"e_1_3_2_1_4_1","volume-title":"Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. In PODC '21: ACM Symposium on Principles of Distributed Computing. ACM, 283--293","author":"Balliu Alkida","year":"2021","unstructured":"Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. 2021. Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees. In PODC '21: ACM Symposium on Principles of Distributed Computing. ACM, 283--293."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_1_6_1","volume-title":"Conference version: IEEE FOCS","author":"Barenboim Leonid","year":"2016","unstructured":"Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. 2016. The Locality of Distributed Symmetry Breaking. Journal of the ACM 63, 3, Article 20 (June 2016), 45 pages. Conference version: IEEE FOCS 2012."},{"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","volume":"209","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, Vol. 209. 10:1--10:19."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818936.2818949"},{"key":"e_1_3_2_1_9_1","volume-title":"Greedy Sequential Maximal Independent Set and Matching Are Parallel on Average. In ACM Symposiumon Parallelism in Algorithms and Architectures (SPAA). 308--317","author":"Blelloch Guy E.","year":"2012","unstructured":"Guy E. Blelloch, Jeremy T. Fineman, and Julian Shun. 2012. Greedy Sequential Maximal Independent Set and Matching Are Parallel on Average. In ACM Symposiumon Parallelism in Algorithms and Architectures (SPAA). 308--317."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Yi-Jun Chang Varsha Dani Thomas P. Hayes Qizheng He Wenzheng Li and Seth Pettie. 2018. The Energy Complexity of Broadcast. In ACM PODC. 95--104.","DOI":"10.1145\/3212734.3212774"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Yi-Jun Chang Varsha Dani Thomas P. Hayes and Seth Pettie. 2020. The Energy Complexity of BFS in Radio Networks. In ACM PODC. 273--282.","DOI":"10.1145\/3382734.3405713"},{"key":"e_1_3_2_1_12_1","volume-title":"Conference version: ACM STOC","author":"Chang Yi-Jun","year":"2019","unstructured":"Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan. 2019. Exponential Separations in the Energy Complexity of Leader Election. ACM Trans. Algorithms 15, 4 (2019), 49:1--49:31. Conference version: ACM STOC 2017.."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405718"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90035-7"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467950"},{"key":"e_1_3_2_1_16_1","volume-title":"36th International Symposium on Distributed Computing, DISC 2022","volume":"22","author":"Dani Varsha","year":"2022","unstructured":"Varsha Dani and Thomas P. Hayes. 2022. How to Wake up Your Neighbors: Safe and Nearly Optimal Generic Energy Conservation in Radio Networks. In 36th International Symposium on Distributed Computing, DISC 2022, October 25--27, 2022, Augusta, Georgia, USA (LIPIcs, Vol. 246), Christian Scheideler (Ed.). 16:1--16:22."},{"key":"e_1_3_2_1_17_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)."},{"key":"e_1_3_2_1_18_1","first-page":"1548","article-title":"Investigating the energy consumption of a wireless network interface in an ad hoc networking environment","volume":"3","author":"Feeney Laura Marie","year":"2001","unstructured":"Laura Marie Feeney and Martin Nilsson. 2001. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment. In IEEE INFOCOM, Vol. 3. 1548--1557.","journal-title":"IEEE INFOCOM"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Manuela Fischer and Andreas Noever. 2018. Tight Analysis of Parallel Randomized Greedy MIS. In SODA. 2152--2160.","DOI":"10.1137\/1.9781611975031.140"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Mohsen Ghaffari. 2016. An Improved Distributed Algorithm for Maximal Independent Set. In SODA. 270--277.","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.173"},{"key":"e_1_3_2_1_22_1","volume-title":"Average Awake Complexity of MIS and Matching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 45--55","author":"Ghaffari Mohsen","year":"2022","unstructured":"Mohsen Ghaffari and Julian Portmann. 2022. Average Awake Complexity of MIS and Matching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 45--55."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612679"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332461"},{"key":"e_1_3_2_1_25_1","volume-title":"Awake-Efficient Distributed Algorithms for Maximal Independent Set. In IEEE Conference on Distributed Computing Systems (ICDCS). 1338--1339","author":"Hourani Khalid","year":"2022","unstructured":"Khalid Hourani, Gopal Pandurangan, and Peter Robinson. 2022. Awake-Efficient Distributed Algorithms for Maximal Independent Set. In IEEE Conference on Distributed Computing Systems (ICDCS). 1338--1339."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571833"},{"key":"e_1_3_2_1_27_1","volume-title":"Energy-Efficient Leader Election Protocols for Single-Hop Radio Networks. In 42nd International Conference on Parallel Processing, ICPP 2013","author":"Kardas Marcin","year":"2013","unstructured":"Marcin Kardas, Marek Klonowski, and Dominik Pajak. 2013. Energy-Efficient Leader Election Protocols for Single-Hop Radio Networks. In 42nd International Conference on Parallel Processing, ICPP 2013, Lyon, France, October 1--4, 2013. IEEE Computer Society, 399--408."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9422-0"},{"key":"e_1_3_2_1_29_1","volume-title":"MIS in the Congested Clique Model in O(log log \u0394) Rounds. arXiv preprint arXiv:1802.07647","author":"Konrad Christian","year":"2018","unstructured":"Christian Konrad. 2018. MIS in the Congested Clique Model in O(log log \u0394) Rounds. arXiv preprint arXiv:1802.07647 (2018)."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.08.037"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Christoph Lenzen and Roger Wattenhofer. 2011. MIS on trees. In ACM PODC. 41--48.","DOI":"10.1145\/1993806.1993813"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_34_1","volume-title":"Sleeping Model: Local and Dynamic Algorithms. arXiv:2112.05344","author":"Maimon Tzalik","year":"2021","unstructured":"Tzalik Maimon. 2021. Sleeping Model: Local and Dynamic Algorithms. arXiv:2112.05344"},{"key":"e_1_3_2_1_35_1","volume-title":"Probability and computing: randomization and probabilistic techniques in algorithms and data analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal. 2017. Probability and computing: randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press."},{"key":"e_1_3_2_1_36_1","volume-title":"Ad Hoc Wireless Networks: Architectures and Protocols","author":"Ram Murthy Chebiyyam Siva","unstructured":"Chebiyyam Siva Ram Murthy and Balakrishnan Manoj. 2004. Ad Hoc Wireless Networks: Architectures and Protocols. Prentice Hall PTR, USA."},{"key":"e_1_3_2_1_37_1","volume-title":"11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18--20, 2000, Proceedings (Lecture Notes in Computer Science","volume":"373","author":"Nakano Koji","year":"2000","unstructured":"Koji Nakano and Stephan Olariu. 2000. Randomized Leader Election Protocols in Radio Networks with No Collision Detection. In Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18--20, 2000, Proceedings (Lecture Notes in Computer Science, Vol. 1969), D. T. Lee and Shang-Hua Teng (Eds.). Springer, 362--373."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAHCN.2006.288433"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529977"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.adhoc.2003.09.008"}],"event":{"name":"PODC '23: 2023 ACM Symposium on Principles of Distributed Computing","location":"Orlando FL USA","acronym":"PODC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGOPS ACM Special Interest Group on Operating Systems"]},"container-title":["Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594574","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583668.3594574","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583668.3594574","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:55Z","timestamp":1750178275000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594574"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,16]]},"references-count":42,"alternative-id":["10.1145\/3583668.3594574","10.1145\/3583668"],"URL":"https:\/\/doi.org\/10.1145\/3583668.3594574","relation":{},"subject":[],"published":{"date-parts":[[2023,6,16]]},"assertion":[{"value":"2023-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}