A Gentle Wakeup Call
ORCID
Biswas: https://orcid.org/0009-0000-2842-5527; Young: https://orcid.org/0000-0002-5251-8595
MSU Affiliation
James Worth Bagley College of Engineering; Department of Computer Science and Engineering
Creation Date
2026-03-30
Abstract
The wakeup problem addresses the fundamental challenge of symmetry breaking. Initially, n devices share a time-slotted multiple access channel, which models wireless communication. A transmission succeeds if exactly one device sends in a slot; if two or more transmit, a collision occurs and none succeed. The goal is to achieve a single successful transmission efficiently. Prior work primarily analyzes latency—the number of slots until the first success. However, in many modern systems, each collision incurs a nontrivial delay, , which prior analyses neglect. Consequently, although existing algorithms achieve polylogarithmic-in-n latency, they still suffer a delay of due to collisions. Here, we design and analyze a randomized wakeup algorithm, Aim-High. When is sufficiently large with respect to n, Aim-High has expected latency and expected total cost of collisions that are nearly ; otherwise, both quantities are . Finally, for a well-studied class of algorithms, we establish a trade-off between latency and expected total cost of collisions.
Publication Date
1-4-2026
Publication Title
ICDCN Companion '26: Companion Proceedings of the 27th International Conference on Distributed Computing and Networking
Publisher
ACM
First Page
96
Last Page
101
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Recommended Citation
Biswas, U., & Young, M. (2026). A Gentle Wakeup Call. Companion Proceedings of the 27th International Conference on Distributed Computing and Networking, 96-101. https://doi.org/10.1145/3737611.3776617
