Metraipolis › archive › dc_278e680e75eb
Dynamic Wakeup under Costly Collisions — arXiv:2609.35662
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35662
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T22:12:17.088Z
- SHA-256 of the archived text
4426162cba563baa21010ce87fbcb419b7e99ed17d2e0e73d14bbba0b0f1cec0- Stable URL of this page
https://metraipolis.com/documento/dc_278e680e75eb
How to cite
Dynamic Wakeup under Costly Collisions — arXiv:2609.35662 — arXiv (en), https://arxiv.org/abs/2609.35662 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_278e680e75eb (Metraipolis archive dc_278e680e75eb, sha256 4426162cba563baa21010ce87fbcb419b7e99ed17d2e0e73d14bbba0b0f1cec0)
BibTeX
@misc{dc278e680e75eb,
title = {Dynamic Wakeup under Costly Collisions — arXiv:2609.35662},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35662},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_278e680e75eb; sha256 4426162cba563baa21010ce87fbcb419b7e99ed17d2e0e73d14bbba0b0f1cec0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35662. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The wakeup problem captures a fundamental symmetry-breaking challenge among devices sharing a communication channel. We study the dynamic setting, where packets become active at arbitrary times on a time-slotted multiple access channel. In each slot, a transmission succeeds if and only if exactly one packet transmits; two or more simultaneous transmissions cause a collision. The goal is to obtain a successful transmission quickly. Prior work on wakeup has largely focused on the number of slots until the first success, referred to as the latency. However, a collision may incur substantial additional delay, represented by a per-collision cost $C$. We therefore seek to control both latency and the collision cost of an execution, defined as $C$ times its number of collisions. We design and analyze a randomized algorithm for dynamic wakeup, Lowball, without collision detection or knowledge of the number of packets, $n$. Fix a constant $0<\epsilon\le 1/2$. There is a constant $K>0$ such that, when $C\ge K\lg^{1/\epsilon} n$, Lowball has expected latency $O(C^{1/2+\epsilon}\ln C)$ and expected collision cost $O(\sqrt{C})$. Below this threshold, both expectations are $O(n\log^{\Theta(1/\epsilon)} n)$. These guarantees hold against an adaptive, non-anticipating adversary, and the algorithm succeeds with probability 1. For algorithms in which each packet's transmission probability depends only on $C$ and the packet's local age, with packets activated together using the same probability schedule, we prove that the maximum of expected latency and expected collision cost is $\Omega(\sqrt{C})$.
Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-29 in cs.DC).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2609.35662 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T21:53:13.732Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).