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.

翻译：唤醒问题涉及对称性破缺的基本挑战。初始状态下，n个设备共享一个时隙多址信道，该信道用于建模无线通信。若某一时隙中仅有一个设备发送信号，则传输成功；若两个或更多设备同时发送，则发生碰撞且无任何传输成功。目标在于高效实现单次成功传输。现有关于唤醒问题的研究主要分析延迟——即首次成功传输前的时隙数量。然而，在许多现代系统中，每次碰撞都会产生不可忽略的延迟C，而先前分析忽略了这一因素。因此，尽管现有算法实现了n的多对数级延迟，它们仍会因碰撞导致Ω(C)的延迟。本文设计并分析了一种随机唤醒算法Aim-High。当C相对于n足够大时，Aim-High的期望延迟与期望碰撞总成本均接近O(√C)；否则，这两个量级均为O(poly{logn})。最后，针对一类已被深入研究的算法，我们建立了延迟与期望碰撞总成本之间的权衡关系。