{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T18:45:49Z","timestamp":1783536349529,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,7,6]],"date-time":"2026-07-06T00:00:00Z","timestamp":1783296000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2402836"],"award-info":[{"award-number":["2402836"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2348346"],"award-info":[{"award-number":["2348346"]}],"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":[[2026,7,6]]},"DOI":"10.1145\/3816782.3819199","type":"proceedings-article","created":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:28:33Z","timestamp":1783531713000},"page":"355-365","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Near-Optimal Bounds for Adversarial Wake-up in Distributed Networks"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7442-7002","authenticated-orcid":false,"given":"Peter","family":"Robinson","sequence":"first","affiliation":[{"name":"Department of Computer Science, Augusta University, Augusta, Georgia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5279-5314","authenticated-orcid":false,"given":"Ming Ming","family":"Tan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Augusta University, Augusta, Georgia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"[Adv95] Advanced Micro Devices Inc. (AMD). Magic packet technology. Technical report 1995. https:\/\/www.amd.com\/content\/dam\/amd\/en\/documents\/archived-tech-docs\/white-papers\/20213.pdf. Accessed: 2024-10-11."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220023"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77618"},{"key":"e_1_3_2_1_5_1","first-page":"146","volume-title":"Online Algorithms: The State of the Art","author":"Aspnes James","year":"2005","unstructured":"[Asp05] James Aspnes. Competitive analysis of distributed algorithms. Online Algorithms: The State of the Art, pages 118\u2013146, 2005."},{"key":"e_1_3_2_1_6_1","first-page":"970","volume-title":"Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012","author":"Censor-Hillel Keren","year":"2012","unstructured":"[CHKM12] Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, and Petar Maymounkov. Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 \u2013 22, 2012, pages 961\u2013970. ACM, 2012."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_3_2_1_8_1","volume-title":"36th International Symposium on Distributed Computing","author":"Dufoulon Fabien","year":"2022","unstructured":"[DKMJ+ 22] Fabien Dufoulon, Shay Kutten, William K Moses Jr, Gopal Pandurangan, and David Peleg. An almost singularly optimal asynchronous distributed mst algorithm. In 36th International Symposium on Distributed Computing, 2022."},{"key":"e_1_3_2_1_9_1","first-page":"26","volume-title":"15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to","volume":"287","author":"Dufoulon Fabien","year":"2024","unstructured":"[DPP+ 24] Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, and Peter Robinson. The message complexity of distributed graph optimization. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 of LIPIcs, pages 41:1\u201341:26. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2024."},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 28th International Conference on Principles of Distributed Systems (OPODIS). LIPIcs, (to appear)","author":"Dufoulon Fabien","year":"2024","unstructured":"[DPRS24] Fabien Dufoulon, Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. The singular optimality of distributed computation in LOCAL. In Proceedings of the 28th International Conference on Principles of Distributed Systems (OPODIS). LIPIcs, (to appear), 2024."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.07.002"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146410"},{"key":"e_1_3_2_1_13_1","volume-title":"IEEE","author":"Gandhi Anshul","year":"2012","unstructured":"[GHBK12] Anshul Gandhi, Mor Harchol-Balter, and Michael A Kozuch. Are sleep states effective in data centers? In 2012 international green computing conference (IGCC), pages 1\u201310. IEEE, 2012."},{"key":"e_1_3_2_1_14_1","volume-title":"A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and systems (TOPLAS), 5(1):66\u201377","author":"Gallager Robert G.","year":"1983","unstructured":"[GHS83] Robert G. Gallager, Pierre A. Humblet, and Philip M. Spira. A distributed algorithm for minimum-weight spanning trees. ACM Transactions on Programming Languages and systems (TOPLAS), 5(1):66\u201377, 1983."},{"key":"e_1_3_2_1_15_1","volume-title":"fast and deterministic gossip and rumor spreading. Journal of the ACM (JACM), 62(6):1\u201318","author":"Haeupler Bernhard","year":"2015","unstructured":"[Hae15] Bernhard Haeupler. Simple, fast and deterministic gossip and rumor spreading. Journal of the ACM (JACM), 62(6):1\u201318, 2015."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767434"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0157-9"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.81"},{"key":"e_1_3_2_1_19_1","first-page":"80","volume-title":"Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti\u00e1n, Spain, July 21 \u2013 23","author":"King Valerie","year":"2015","unstructured":"[KKT15] Valerie King, Shay Kutten, and Mikkel Thorup. Construction and impromptu repair of an MST in a distributed network with o(m) communication. In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti\u00e1n, Spain, July 21 \u2013 23, 2015, pages 71\u201380. ACM, 2015."},{"key":"e_1_3_2_1_20_1","volume-title":"34th International Symposium on Distributed Computing (DISC 2020","author":"Kutten Shay","year":"2020","unstructured":"[KMJPP20] Shay Kutten, William K Moses Jr, Gopal Pandurangan, and David Peleg. Singularly optimal randomized leader election. In 34th International Symposium on Distributed Computing (DISC 2020). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik, 2020."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699440"},{"key":"e_1_3_2_1_22_1","unstructured":"[KPRR19] Christian Konrad Sriram V. Pemmaraju Talal Riaz and Peter Robinson. The complexity of symmetry breaking in massive graphs. In Jukka Suomela editor 33rd International Symposium on Distributed Computing DISC 2019 Budapest Hungary October 14\u201318 2019 volume 146 of LIPIcs pages 26:1\u201326:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik 2019."},{"key":"e_1_3_2_1_23_1","volume-title":"Tight bounds on the message complexity of distributed tree verification. arXiv preprint arXiv:2401.11991","author":"Kutten Shay","year":"2024","unstructured":"[KRT24] Shay Kutten, Peter Robinson, and Ming Ming Tan. Tight bounds on the message complexity of distributed tree verification. arXiv preprint arXiv:2401.11991, 2024."},{"key":"e_1_3_2_1_24_1","first-page":"365","volume-title":"Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023","author":"Kutten Shay","year":"2023","unstructured":"[KRTZ23] Shay Kutten, Peter Robinson, Ming Ming Tan, and Xianbin Zhu. Improved tradeoffs for leader election. In Rotem Oshman, Alexandre Nolin, Magn\u00fas M. Halld\u00f3rsson, and Alkida Balliu, editors, Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19\u201323, 2023, pages 355\u2013365. ACM, 2023."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892324"},{"key":"e_1_3_2_1_26_1","volume-title":"A new series of dense graphs of high girth. Bulletin of the American mathematical society, 32(1):73\u201379","author":"Lazebnik Felix","year":"1995","unstructured":"[LUW95] Felix Lazebnik, Vasiliy A Ustimenko, and Andrew J Woldar. A new series of dense graphs of high girth. Bulletin of the American mathematical society, 32(1):73\u201379, 1995."},{"key":"e_1_3_2_1_27_1","volume-title":"33rd International Symposium on Distributed Computing (DISC 2019","author":"Mashreghi Ali","year":"2019","unstructured":"[MK19] Ali Mashreghi and Valerie King. Brief announcement: Faster asynchronous mst and low diameter tree construction with sublinear communication. In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik, 2019."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00387-y"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467909"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.11.017"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055449"},{"key":"e_1_3_2_1_33_1","first-page":"2120","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \u2013 13","author":"Robinson Peter","year":"2021","unstructured":"[Rob21] Peter Robinson. Being fast means being chatty: The local information cost of graph spanners. In D\u00e1niel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \u2013 13, 2021, pages 2105\u20132120. SIAM, 2021."},{"key":"e_1_3_2_1_34_1","volume-title":"Rise and shine efficiently! the complexity of adversarial wake-up in asynchronous networks. CoRR, abs\/2410.09980","author":"Robinson Peter","year":"2024","unstructured":"[RT24] Peter Robinson and Ming Ming Tan. Rise and shine efficiently! the complexity of adversarial wake-up in asynchronous networks. CoRR, abs\/2410.09980, 2024."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/135419.135457"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.37"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431223"},{"key":"e_1_3_2_1_39_1","volume-title":"the free encyclopedia","author":"LAN","year":"2024","unstructured":"[wik24] Wake-on-LAN \u2014 wikipedia, the free encyclopedia, 2024. https:\/\/en.wikipedia.org\/wiki\/Wake-on-LAN. Accessed: 2024-10-11."}],"event":{"name":"SPAA '26: 38th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Royal Holloway, University of London London United Kingdom","acronym":"SPAA '26","sponsor":["SIGARCH ACM Special Interest Group on Computer Architecture","SIGACT ACM Special Interest Group on Algorithms and Computation Theory","EATCS"]},"container-title":["Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3816782.3819199","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3816782.3819199","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T17:30:34Z","timestamp":1783531834000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3816782.3819199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,6]]},"references-count":39,"alternative-id":["10.1145\/3816782.3819199","10.1145\/3816782"],"URL":"https:\/\/doi.org\/10.1145\/3816782.3819199","relation":{},"subject":[],"published":{"date-parts":[[2026,7,6]]},"assertion":[{"value":"2026-07-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}