{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:03:17Z","timestamp":1783576997943,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T00:00:00Z","timestamp":1596153600000},"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":["CCF-1150281, CCF-1514383, CCF-1637546, CCF-1815316"],"award-info":[{"award-number":["CCF-1150281, CCF-1514383, CCF-1637546, CCF-1815316"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,31]]},"DOI":"10.1145\/3382734.3405713","type":"proceedings-article","created":{"date-parts":[[2020,7,31]],"date-time":"2020-07-31T22:33:55Z","timestamp":1596234835000},"page":"273-282","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["The Energy Complexity of BFS in Radio Networks"],"prefix":"10.1145","author":[{"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Varsha","family":"Dani","sequence":"additional","affiliation":[{"name":"University of New Mexico"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas P.","family":"Hayes","sequence":"additional","affiliation":[{"name":"University of New Mexico"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,7,31]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"A. Abboud K. Censor-Hillel and S. Khoury. 2016. Near-Linear Lower Bounds for Distributed Distance Computations Even in Sparse Networks. In Distributed Computing (DISC) Cyril Gavoille and David Ilcinkas (Eds.). Springer Berlin Heidelberg 29--42.  A. Abboud K. Censor-Hillel and S. Khoury. 2016. Near-Linear Lower Bounds for Distributed Distance Computations Even in Sparse Networks. In Distributed Computing (DISC) Cyril Gavoille and David Ilcinkas (Eds.). Springer Berlin Heidelberg 29--42.","DOI":"10.1007\/978-3-662-53426-7_3"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90015-W"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02259748"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/171540.171571"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 5th International Conference on Systems and Networks Communications (ICSNC). 83--87","author":"Barnes M.","unstructured":"M. Barnes , C. Conway , J. Mathews , and D. K. Arvind . 2010. ENS: An Energy Harvesting Wireless Sensor Network Platform . In Proceedings of the 5th International Conference on Systems and Networks Communications (ICSNC). 83--87 . M. Barnes, C. Conway, J. Mathews, and D. K. Arvind. 2010. ENS: An Energy Harvesting Wireless Sensor Network Platform. In Proceedings of the 5th International Conference on Systems and Networks Communications (ICSNC). 83--87."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1158604"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540666.1541119"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). 95--104","author":"Chang Y.-J.","unstructured":"Y.-J. Chang , V. Dani , T. P. Hayes , Q. He , W. Li , and S. Pettie . 2018. The Energy Complexity of Broadcast . In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). 95--104 . Y.-J. Chang, V. Dani, T. P. Hayes, Q. He, W. Li, and S. Pettie. 2018. The Energy Complexity of Broadcast. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC). 95--104."},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC). 771--783","author":"Chang Y.-J.","unstructured":"Y.-J. Chang , T. Kopelowitz , S. Pettie , R. Wang , and W. Zhan . 2017. Exponential separations in the energy complexity of leader election . In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC). 771--783 . Y.-J. Chang, T. Kopelowitz, S. Pettie, R. Wang, and W. Zhan. 2017. Exponential separations in the energy complexity of leader election. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC). 771--783."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1985.1096245"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1987.1676861"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC). 3--12","author":"Czumaj A.","unstructured":"A. Czumaj and P. Davies . 2017. Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks . In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC). 3--12 . A. Czumaj and P. Davies. 2017. Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks. In Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC). 3--12."},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings 21st International Symposium on Distributed Computing (DISC). 253--267","author":"Gasieniec L.","unstructured":"L. Gasieniec , E. Kantor , D. R. Kowalski , D. Peleg , and C. Su . 2007. Energy and Time Efficient Broadcasting in Known Topology Radio Networks . In Proceedings 21st International Symposium on Distributed Computing (DISC). 253--267 . L. Gasieniec, E. Kantor, D. R. Kowalski, D. Peleg, and C. Su. 2007. Energy and Time Efficient Broadcasting in Known Topology Radio Networks. In Proceedings 21st International Symposium on Distributed Computing (DISC). 253--267."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCOMM.2016.2539940"},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 257--266","author":"Gilbert S.","unstructured":"S. Gilbert , V. King , S. Pettie , E. Porat , J. Saia , and M. Young . 2014. (Near) optimal resource-competitive broadcast with jamming . In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 257--266 . S. Gilbert, V. King, S. Pettie, E. Porat, J. Saia, and M. Young. 2014. (Near) optimal resource-competitive broadcast with jamming. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 257--266."},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings 35th ACM Symposium on Principles of Distributed Computing (PODC). ACM, 361--370","author":"Haeupler B.","unstructured":"B. Haeupler and D. Wajc . 2016. A faster distributed radio broadcast primitive . In Proceedings 35th ACM Symposium on Principles of Distributed Computing (PODC). ACM, 361--370 . B. Haeupler and D. Wajc. 2016. A faster distributed radio broadcast primitive. In Proceedings 35th ACM Symposium on Principles of Distributed Computing (PODC). ACM, 361--370."},{"key":"e_1_3_2_1_17_1","volume-title":"Proc. 28th International Symposium on Distributed Computing (DISC","author":"Holzer S.","year":"2014","unstructured":"S. Holzer , D. Peleg , L. Roditty , and R. Wattenhofer . 2014. Brief announcement: Distributed 3\/2-approximation of the diameter . In Proc. 28th International Symposium on Distributed Computing (DISC 2014 ). Springer, 562--564. S. Holzer, D. Peleg, L. Roditty, and R. Wattenhofer. 2014. Brief announcement: Distributed 3\/2-approximation of the diameter. In Proc. 28th International Symposium on Distributed Computing (DISC 2014). Springer, 562--564."},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC). 51--57","author":"Jurdzinski T.","unstructured":"T. Jurdzinski , M. Kutylowski , and J. Zatopianski . 2002. Efficient algorithms for leader election in radio networks . In Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC). 51--57 . T. Jurdzinski, M. Kutylowski, and J. Zatopianski. 2002. Efficient algorithms for leader election in radio networks. In Proceedings of the 21st Annual ACM Symposium on Principles of Distributed Computing (PODC). 51--57."},{"key":"e_1_3_2_1_19_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 . 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."},{"key":"e_1_3_2_1_20_1","volume-title":"Proceedings of the 8th International European Conference on Parallel Computing (Euro-Par). 965--972","author":"Jurdzinski T.","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--972 . 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--972."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.783"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC). 535--549","author":"Jurdzinski T.","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--549 . 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--549."},{"key":"e_1_3_2_1_23_1","volume-title":"Proceedings Third International Conference on Theory and Applications of Models of Computation (TAMC). 148--158","author":"Kabarowski J.","unstructured":"J. Kabarowski , M. Kutylowski , and W. Rutkowski . 2006. Adversary Immune Size Approximation of Single-Hop Radio Networks . In Proceedings Third International Conference on Theory and Applications of Models of Computation (TAMC). 148--158 . J. Kabarowski, M. Kutylowski, and W. Rutkowski. 2006. Adversary Immune Size Approximation of Single-Hop Radio Networks. In Proceedings Third International Conference on Theory and Applications of Models of Computation (TAMC). 148--158."},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings 42nd International Conference on Parallel Processing (ICPP). 399--408","author":"Kardas M.","unstructured":"M. Kardas , M. Klonowski , and D. Pajak . 2013. Energy-Efficient Leader Election Protocols for Single-Hop Radio Networks . In Proceedings 42nd International Conference on Parallel Processing (ICPP). 399--408 . M. Kardas, M. Klonowski, and D. Pajak. 2013. Energy-Efficient Leader Election Protocols for Single-Hop Radio Networks. In Proceedings 42nd International Conference on Parallel Processing (ICPP). 399--408."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-017-0313-3"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212786"},{"key":"e_1_3_2_1_27_1","first-page":"285","article-title":"Energy-optimal algorithms for computing aggregative functions in random networks","volume":"17","author":"Klonowski Marek","year":"2016","unstructured":"Marek Klonowski and Malgorzata Sulkowska . 2016 . Energy-optimal algorithms for computing aggregative functions in random networks . Discrete Mathematics & Theoretical Computer Science 17 , 3 (2016), 285 -- 306 . Marek Klonowski and Malgorzata Sulkowska. 2016. Energy-optimal algorithms for computing aggregative functions in random networks. Discrete Mathematics & Theoretical Computer Science 17, 3 (2016), 285--306.","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279109"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_37"},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA). 192--201","author":"Miller G. L.","unstructured":"G. L. Miller , R. Peng , A. Vladu , and S. C. Xu . 2015. Improved Parallel Algorithms for Spanners and Hopsets . In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA). 192--201 . G. L. Miller, R. Peng, A. Vladu, and S. C. Xu. 2015. Improved Parallel Algorithms for Spanners and Hopsets. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA). 192--201."},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 196--203","author":"Miller G. L.","unstructured":"G. L. Miller , R. Peng , and S. C. Xu . 2013. Parallel graph decompositions using random shifts . In Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 196--203 . G. L. Miller, R. Peng, and S. C. Xu. 2013. Parallel graph decompositions using random shifts. In Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 196--203."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.877942"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_18"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN). 364--369","author":"Polastre J.","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--369 . 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--369."},{"key":"e_1_3_2_1_35_1","volume-title":"Proceedings 45th ACM Symposium on Theory of Computing (STOC). 515--524","author":"Roditty L.","unstructured":"L. Roditty and V. Vassilevska Williams . 2013. Fast approximation algorithms for the diameter and radius of sparse graphs . In Proceedings 45th ACM Symposium on Theory of Computing (STOC). 515--524 . L. Roditty and V. Vassilevska Williams. 2013. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings 45th ACM Symposium on Theory of Computing (STOC). 515--524."}],"event":{"name":"PODC '20: ACM Symposium on Principles of Distributed Computing","location":"Virtual Event Italy","acronym":"PODC '20","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 39th Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382734.3405713","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382734.3405713","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382734.3405713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:49Z","timestamp":1750197769000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382734.3405713"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,31]]},"references-count":35,"alternative-id":["10.1145\/3382734.3405713","10.1145\/3382734"],"URL":"https:\/\/doi.org\/10.1145\/3382734.3405713","relation":{},"subject":[],"published":{"date-parts":[[2020,7,31]]},"assertion":[{"value":"2020-07-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}