{"ID":2882500,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.11006","arxiv_id":"2508.11006","title":"A Gentle Wakeup Call: Symmetry Breaking with Less Collision Cost","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 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.","short_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...","url_abs":"https://arxiv.org/abs/2508.11006","url_pdf":"https://arxiv.org/pdf/2508.11006v3","authors":"[\"Umesh Biswas\",\"Maxwell Young\"]","published":"2025-08-14T18:15:32Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}