Metraipolis › archive › dc_2f9440294aa5

Contention Resolution with a Fast-but-Fickle Channel — arXiv:2611.12843

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.12843
License (as archived)
CC0-1.0
Archived
2026-11-10T18:45:52.684Z
SHA-256 of the archived text
df3eb0609ae2565d4a69c3271fd11628cfea43b317d093a206e04dd9187b6981
Stable URL of this page
https://metraipolis.com/documento/dc_2f9440294aa5

How to cite

Contention Resolution with a Fast-but-Fickle Channel — arXiv:2611.12843 — arXiv (en), https://arxiv.org/abs/2611.12843 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2f9440294aa5 (Metraipolis archive dc_2f9440294aa5, sha256 df3eb0609ae2565d4a69c3271fd11628cfea43b317d093a206e04dd9187b6981)
BibTeX
@misc{dc2f9440294aa5,
  title = {Contention Resolution with a Fast-but-Fickle Channel — arXiv:2611.12843},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.12843},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2f9440294aa5; sha256 df3eb0609ae2565d4a69c3271fd11628cfea43b317d093a206e04dd9187b6981},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.12843. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The contention-resolution problem studies how $n$ devices share a communication channel without centralized coordination. Classical models typically assume a single continuously available channel and focus on minimizing total completion time. However, modern wireless systems increasingly rely on shared spectrum, where access may be abruptly revoked by incumbent users. Motivated by this setting, we study contention resolution with two channels: a reliable slow channel and a faster channel that can be intermittently disabled by unpredictable eviction periods. Moving a batch of packets from the slow channel to the fast channel incurs a unit cost, while evictions from the fast channel impose a larger per-packet penalty. Our goal is to achieve asymptotically optimal latency while minimizing switching overhead relative to an optimal offline algorithm that knows the eviction schedule. We present Randomized Adaptive Channel Exploitation (RACE), a randomized algorithm that exploits the fast channel when available while maintaining progress on the slow channel during disruptions. When the fast channel has rate $\rho \in \bigl[\Omega(\log n), O(\sqrt n)\bigr]$ and a sufficiently large constant-factor resource augmentation, RACE achieves an $O(1)$ competitive ratio for expected latency. RACE's expected switching-cost competitive ratio relative to any optimal-latency offline algorithm OPT is $O(\rho+\sqrt{n/m})$, where $m \geq 1$ is the number of fast-channel availability intervals used by OPT. We also prove a worst-case $\Omega(\sqrt n)$ switching-cost competitive ratio for latency-competitive randomized algorithms, and a separate $\Omega(\rho)$ switching-cost competitive-ratio lower bound. These lower bounds hold even with fixed constant-factor augmentation on both channels.

Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC).
Pagina del lavoro: https://arxiv.org/abs/2611.12843 — 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-11-10T18:38:07.448Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).