跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.12843 · v1

Contention Resolution with a Fast-but-Fickle Channel

快速但不稳定信道下的争用解决

首次提交 2026-11-10 02:39
版本更新 2026-11-10 02:39
雷达观测 2026-11-10 15:22
arXiv ↗PDF ↗

摘要

The contention-resolution problem studies how nn 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 ρ∈[Ω(log⁡n),O(n)]ρ\in \bigl[Ω(\log n), O(\sqrt n)\bigr] and a sufficiently large constant-factor resource augmentation, RACE achieves an O(1)O(1) competitive ratio for expected latency. RACE's expected switching-cost competitive ratio relative to any optimal-latency offline algorithm OPT is O(ρ+n/m)O(ρ+\sqrt{n/m}), where m≥1m \geq 1 is the number of fast-channel availability intervals used by OPT. We also prove a worst-case Ω(n)Ω(\sqrt n) switching-cost competitive ratio for latency-competitive randomized algorithms, and a separate Ω(ρ)Ω(ρ) switching-cost competitive-ratio lower bound. These lower bounds hold even with fixed constant-factor augmentation on both channels.

AI 论文解读

基于摘要 · 非全文审阅

研究在一条可靠慢信道与一条可被不可预测驱逐的快速信道之间调度数据包,提出随机算法 RACE,在保持渐近最优延迟的同时控制切换开销。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-10 02:39 · 最新观测版本

Contention Resolution with a Fast-but-Fickle Channel

The contention-resolution problem studies how nn 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 ρ∈[Ω(log⁡n),O(n)]ρ\in \bigl[Ω(\log n), O(\sqrt n)\bigr] and a sufficiently large constant-factor resource augmentation, RACE achieves an O(1)O(1) competitive ratio for expected latency. RACE's expected switching-cost competitive ratio relative to any optimal-latency offline algorithm OPT is O(ρ+n/m)O(ρ+\sqrt{n/m}), where m≥1m \geq 1 is the number of fast-channel availability intervals used by OPT. We also prove a worst-case Ω(n)Ω(\sqrt n) switching-cost competitive ratio for latency-competitive randomized algorithms, and a separate Ω(ρ)Ω(ρ) switching-cost competitive-ratio lower bound. These lower bounds hold even with fixed constant-factor augmentation on both channels.

查看此版本解读 →查看此版本原文 ↗