← 研踪 PaperTrailarXiv: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
摘要
The contention-resolution problem studies how 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 and a sufficiently large constant-factor resource augmentation, RACE achieves an competitive ratio for expected latency. RACE's expected switching-cost competitive ratio relative to any optimal-latency offline algorithm OPT is , where is the number of fast-channel availability intervals used by OPT. We also prove a worst-case 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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-10 02:39 · 最新观测版本
Contention Resolution with a Fast-but-Fickle Channel
The contention-resolution problem studies how 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 and a sufficiently large constant-factor resource augmentation, RACE achieves an competitive ratio for expected latency. RACE's expected switching-cost competitive ratio relative to any optimal-latency offline algorithm OPT is , where is the number of fast-channel availability intervals used by OPT. We also prove a worst-case 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.
查看此版本解读 →查看此版本原文 ↗