{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T21:01:57Z","timestamp":1762808517281,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,19]],"date-time":"2017-06-19T00:00:00Z","timestamp":1497830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1318294, CCF-1514383, CCF-1637546"],"award-info":[{"award-number":["CNS-1318294, CCF-1514383, CCF-1637546"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Basic Research Program of China","award":["2015CB358700, 2011CBA00300, 2011CBA00301"],"award-info":[{"award-number":["2015CB358700, 2011CBA00300, 2011CBA00301"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61202009, 61033001, 61361136003"],"award-info":[{"award-number":["61202009, 61033001, 61361136003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2017,6,19]]},"DOI":"10.1145\/3055399.3055481","type":"proceedings-article","created":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T20:27:45Z","timestamp":1497558465000},"page":"771-783","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Exponential separations in the energy complexity of leader election"],"prefix":"10.1145","author":[{"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsvi","family":"Kopelowitz","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruosong","family":"Wang","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Zhan","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,6,19]]},"reference":[{"key":"e_1_3_2_2_1_1","unstructured":"N. Alon A. Bar-Noy N. Linial and D. Peleg. 1991.  N. Alon A. Bar-Noy N. Linial and D. Peleg. 1991."},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90015-W"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02259748"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90042-H"},{"key":"e_1_3_2_2_5_1","unstructured":"M. Barnes C. Conway J. Mathews and D. K. Arvind. 2010.  M. Barnes C. Conway J. Mathews and D. K. Arvind. 2010."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSNC.2010.18"},{"volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 636\u2013654","author":"Bender M. A.","key":"e_1_3_2_2_7_1","unstructured":"M. A. Bender , J. T. Fineman , S. Gilbert , and M. Young . 2016. How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness . In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 636\u2013654 . DOI:http:\/\/dx. M. A. Bender, J. T. Fineman, S. Gilbert, and M. Young. 2016. How to Scale Exponential Backoff: Constant Throughput, Polylog Access Attempts, and Robustness. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 636\u2013654. DOI:http:\/\/dx."},{"key":"e_1_3_2_2_8_1","unstructured":"M. A. Bender J. T. Fineman M. Movahedi J. Saia V. Dani S. Gilbert S. Pettie and M. Young. 2015.  M. A. Bender J. T. Fineman M. Movahedi J. Saia V. Dani S. Gilbert S. Pettie and M. Young. 2015."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818936.2818949"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897655"},{"volume-title":"Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO).","author":"Brandes P.","key":"e_1_3_2_2_11_1","unstructured":"P. Brandes , M. Kardas , M. Klonowski , D. Pajak , and R. Wattenhofer . 2016. Approximating the Size of a Radio Network in Beeping Model . In Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO). P. Brandes, M. Kardas, M. Klonowski, D. Pajak, and R. Wattenhofer. 2016. Approximating the Size of a Radio Network in Beeping Model. In Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO)."},{"key":"e_1_3_2_2_12_1","unstructured":"Yi-Jun Chang Tsvi Kopelowitz Seth Pettie Ruosong Wang and Wei Zhan. 2016.  Yi-Jun Chang Tsvi Kopelowitz Seth Pettie Ruosong Wang and Wei Zhan. 2016."},{"key":"e_1_3_2_2_13_1","volume-title":"CoRR abs\/1609.08486","author":"Energy Exponential Separations","year":"2016","unstructured":"Exponential Separations in the Energy Complexity of Leader Election . CoRR abs\/1609.08486 ( 2016 ). http:\/\/arxiv.org\/abs\/1609.08486 Exponential Separations in the Energy Complexity of Leader Election. CoRR abs\/1609.08486 (2016). http:\/\/arxiv.org\/abs\/1609.08486"},{"volume-title":"The 16th International Conference On Principles Of Distributed Systems (OPODIS). Springer, 106\u2013120","author":"Chlebus B. S.","key":"e_1_3_2_2_14_1","unstructured":"B. S. Chlebus , D. R. Kowalski , and A. Pelc . 2012. Electing a leader in multi-hop radio networks . In The 16th International Conference On Principles Of Distributed Systems (OPODIS). Springer, 106\u2013120 . B. S. Chlebus, D. R. Kowalski, and A. Pelc. 2012. Electing a leader in multi-hop radio networks. In The 16th International Conference On Principles Of Distributed Systems (OPODIS). Springer, 106\u2013120."},{"key":"e_1_3_2_2_15_1","unstructured":"A. E. F. Clementi A. Monti and R. Silvestri. 2003.  A. E. F. Clementi A. Monti and R. Silvestri. 2003."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00851-4"},{"key":"e_1_3_2_2_17_1","unstructured":"A. Cornejo and F. Kuhn. 2010.  A. Cornejo and F. Kuhn. 2010."},{"volume-title":"Proceedings of The 24th International Symposium on Distributed Computing (DISC)","author":"Deploying","key":"e_1_3_2_2_18_1","unstructured":"Deploying wireless networks with beeps. In Proceedings of The 24th International Symposium on Distributed Computing (DISC) . Springer , 148\u2013162. Deploying wireless networks with beeps. In Proceedings of The 24th International Symposium on Distributed Computing (DISC). Springer, 148\u2013162."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933076"},{"key":"e_1_3_2_2_20_1","unstructured":"2933076  2933076"},{"key":"e_1_3_2_2_21_1","unstructured":"A. Czumaj and W. Rytter. 2003.  A. Czumaj and W. Rytter. 2003."},{"volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 492\u2013501","author":"Broadcasting","key":"e_1_3_2_2_22_1","unstructured":"Broadcasting algorithms in radio networks with unknown topology . In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 492\u2013501 . Broadcasting algorithms in radio networks with unknown topology. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 492\u2013501."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332470"},{"key":"e_1_3_2_2_24_1","first-page":"215","article-title":"On a problem of graph theory. Studia Sci","volume":"1","author":"Erd\u0151s P.","year":"1966","unstructured":"P. Erd\u0151s , A. R\u00e9nyi , and V. T. S\u00f3s . 1966 . On a problem of graph theory. Studia Sci . Math. Hung. 1 (1966), 215 \u2013 235 . P. Erd\u0151s, A. R\u00e9nyi, and V. T. S\u00f3s. 1966. On a problem of graph theory. Studia Sci. Math. Hung. 1 (1966), 215\u2013235.","journal-title":"Math. Hung."},{"key":"e_1_3_2_2_25_1","unstructured":"M. Farach-Colton R. J. Fernandes and M. A. Mosteiro. 2006.  M. Farach-Colton R. J. Fernandes and M. A. Mosteiro. 2006."},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_42"},{"volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (PODC). 748\u2013766","author":"Ghaffari M.","key":"e_1_3_2_2_27_1","unstructured":"M. Ghaffari and B. Haeupler . 2013. Near optimal leader election in multi-hop radio networks . In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (PODC). 748\u2013766 . M. Ghaffari and B. Haeupler. 2013. Near optimal leader election in multi-hop radio networks. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (PODC). 748\u2013766."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612679"},{"key":"e_1_3_2_2_29_1","unstructured":"S. Gilbert and C. Newport. 2015.  S. Gilbert and C. Newport. 2015."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48653-5_3"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.214125"},{"key":"e_1_3_2_2_32_1","unstructured":"T. Jurdzinski M. Kutylowski and J. Zatopianski. 2002.  T. Jurdzinski M. Kutylowski and J. Zatopianski. 2002."},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571833"},{"key":"e_1_3_2_2_34_1","unstructured":"T. Jurdzinski M. Kutylowski and J. Zatopianski. 2002.  T. Jurdzinski M. Kutylowski and J. Zatopianski. 2002."},{"volume-title":"Size Approximation of Radio Networks with No Collision Detection. In Proceedings of the 8th Annual International Conference on Computing and Combinatorics (COCOON). 279\u2013289","author":"Energy-Efficient","key":"e_1_3_2_2_35_1","unstructured":"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\u2013289 . DOI:http:\/\/dx. 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\u2013289. DOI:http:\/\/dx."},{"volume-title":"Proceedings of the 8th International European Conference on Parallel Computing (Euro-Par). 965\u2013972","author":"Jurdzinski T.","key":"e_1_3_2_2_36_1","unstructured":"T. Jurdzinski , M. Kutylowski , and J. Zatopianski . 2002. Weak Communication in Radio Networks . In Proceedings of the 8th International European Conference on Parallel Computing (Euro-Par). 965\u2013972 . DOI:http:\/\/dx. T. Jurdzinski, M. Kutylowski, and J. Zatopianski. 2002. Weak Communication in Radio Networks. In Proceedings of the 8th International European Conference on Parallel Computing (Euro-Par). 965\u2013972. DOI:http:\/\/dx."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.783"},{"volume-title":"Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC). 535\u2013549","author":"Jurdzinski T.","key":"e_1_3_2_2_38_1","unstructured":"T. Jurdzinski and G. Stachowiak . 2002. Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks . In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC). 535\u2013549 . DOI:http:\/\/dx. T. Jurdzinski and G. Stachowiak. 2002. Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks. In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC). 535\u2013549. DOI:http:\/\/dx."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2013.49"},{"key":"e_1_3_2_2_40_1","unstructured":"G. Katona and E. Szemer\u00e9di. 1967.  G. Katona and E. Szemer\u00e9di. 1967."},{"key":"e_1_3_2_2_41_1","volume-title":"Studia Scientiarum Mathematicarum Hungarica 2","author":"On","year":"1967","unstructured":"On a problem of graph theory. Studia Scientiarum Mathematicarum Hungarica 2 ( 1967 ), 23\u201328. On a problem of graph theory. Studia Scientiarum Mathematicarum Hungarica 2 (1967), 23\u201328."},{"key":"e_1_3_2_2_42_1","unstructured":"V. King J. Saia and M. Young. 2011.  V. King J. Saia and M. Young. 2011."},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993855"},{"key":"e_1_3_2_2_44_1","unstructured":"D. R. Kowalski and A. Pelc. 2005.  D. R. Kowalski and A. Pelc. 2005."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0126-7"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_43"},{"key":"e_1_3_2_2_47_1","unstructured":"E. Kushilevitz and Y. Mansour. 1998.  E. Kushilevitz and Y. Mansour. 1998."},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279109"},{"key":"e_1_3_2_2_49_1","unstructured":"M. Kuty\u0142owski and W. Rutkowski. 2003.  M. Kuty\u0142owski and W. Rutkowski. 2003."},{"volume-title":"Proceedings of the 11th European Symposium on Algorithms (ESA)","author":"Adversary","key":"e_1_3_2_2_50_1","unstructured":"Adversary immune leader election in ad hoc radio networks. In Proceedings of the 11th European Symposium on Algorithms (ESA) . Springer , 397\u2013408. Adversary immune leader election in ad hoc radio networks. In Proceedings of the 11th European Symposium on Algorithms (ESA). Springer, 397\u2013408."},{"key":"e_1_3_2_2_51_1","unstructured":"Y. Lee S. Bang I. Lee Y. Kim G. Kim M. H. Ghaed P. Pannuto P. Dutta D. Sylvester and D. Blaauw. 2013.  Y. Lee S. Bang I. Lee Y. Kim G. Kim M. H. Ghaed P. Pannuto P. Dutta D. Sylvester and D. Blaauw. 2013."},{"key":"e_1_3_2_2_52_1","volume-title":"IEEE Journal of Solid-State Circuits 48, 1","author":"Die-Stacked Sensing A Modular","year":"2013","unstructured":"A Modular 1 mm 3 Die-Stacked Sensing Platform With Low Power I 2 C Inter-Die Communication and Multi-Modal Energy Harvesting . IEEE Journal of Solid-State Circuits 48, 1 ( 2013 ), 229\u2013243. A Modular 1 mm 3 Die-Stacked Sensing Platform With Low Power I 2 C Inter-Die Communication and Multi-Modal Energy Harvesting. IEEE Journal of Solid-State Circuits 48, 1 (2013), 229\u2013243."},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.877942"},{"key":"e_1_3_2_2_54_1","unstructured":"K. Nakano and S. Olariu. 2000.  K. Nakano and S. Olariu. 2000."},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.877833"},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_18"},{"volume-title":"Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN). 364\u2013369","author":"Polastre J.","key":"e_1_3_2_2_57_1","unstructured":"J. Polastre , R. Szewczyk , and D. Culler . 2005. Telos: enabling ultra-low power wireless research . In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN). 364\u2013369 . DOI:http:\/\/dx. J. Polastre, R. Szewczyk, and D. Culler. 2005. Telos: enabling ultra-low power wireless research. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN). 364\u2013369. DOI:http:\/\/dx."},{"volume-title":"Proceedings 24th International Symposium on Distributed Computing (DISC). 133\u2013147","author":"Schneider J.","key":"e_1_3_2_2_58_1","unstructured":"J. Schneider and R. Wattenhofer . 2010. What Is the Use of Collision Detection (in Wireless Networks)? . In Proceedings 24th International Symposium on Distributed Computing (DISC). 133\u2013147 . DOI:http:\/\/dx. J. Schneider and R. Wattenhofer. 2010. What Is the Use of Collision Detection (in Wireless Networks)?. In Proceedings 24th International Symposium on Distributed Computing (DISC). 133\u2013147. DOI:http:\/\/dx."},{"key":"e_1_3_2_2_59_1","unstructured":"K. M. Sivalingam M. B. Srivastava and P. Agrawal. 1997.  K. M. Sivalingam M. B. Srivastava and P. Agrawal. 1997."},{"key":"e_1_3_2_2_60_1","volume-title":"Proceedings of the 47th IEEE Conference on Vehicular Technology","volume":"3","author":"Low","unstructured":"Low power link and access protocols for wireless multimedia networks . In Proceedings of the 47th IEEE Conference on Vehicular Technology , Vol. 3 . 1331\u20131335. DOI:http: \/\/dx. Low power link and access protocols for wireless multimedia networks. In Proceedings of the 47th IEEE Conference on Vehicular Technology, Vol. 3. 1331\u20131335. DOI:http: \/\/dx."}],"event":{"name":"STOC '17: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Montreal Canada","acronym":"STOC '17"},"container-title":["Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055481","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055481","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3055399.3055481","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:36:19Z","timestamp":1750217779000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3055399.3055481"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,19]]},"references-count":60,"alternative-id":["10.1145\/3055399.3055481","10.1145\/3055399"],"URL":"https:\/\/doi.org\/10.1145\/3055399.3055481","relation":{},"subject":[],"published":{"date-parts":[[2017,6,19]]},"assertion":[{"value":"2017-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}