Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.11006 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918214242402304 |
|---|---|
| author | Biswas, Umesh Young, Maxwell |
| author_facet | Biswas, Umesh Young, Maxwell |
| contents | 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 on wakeup primarily analyzes latency -- the number of slots until the first success. However, in many modern systems, each collision incurs a nontrivial delay, C, which prior analyses neglect. Consequently, although existing algorithms achieve polylogarithmic-in-n latency, they still suffer a delay of Ω(C) due to collisions.
Here, we design and analyze a randomized wakeup algorithm, Aim-High. When C is sufficiently large with respect to n, Aim-High has expected latency and expected total cost of collisions that are nearly O(\sqrt{C}); otherwise, both quantities are O(poly{\log n}). Finally, for a well-studied class of algorithms, we establish a trade-off between latency and expected total cost of collisions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_11006 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Gentle Wakeup Call: Symmetry Breaking with Less Collision Cost Biswas, Umesh Young, Maxwell Data Structures and Algorithms 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 on wakeup primarily analyzes latency -- the number of slots until the first success. However, in many modern systems, each collision incurs a nontrivial delay, C, which prior analyses neglect. Consequently, although existing algorithms achieve polylogarithmic-in-n latency, they still suffer a delay of Ω(C) due to collisions. Here, we design and analyze a randomized wakeup algorithm, Aim-High. When C is sufficiently large with respect to n, Aim-High has expected latency and expected total cost of collisions that are nearly O(\sqrt{C}); otherwise, both quantities are O(poly{\log n}). Finally, for a well-studied class of algorithms, we establish a trade-off between latency and expected total cost of collisions. |
| title | A Gentle Wakeup Call: Symmetry Breaking with Less Collision Cost |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.11006 |