Contention resolution improves latency with dual fast and slow channels
Contention Resolution with a Fast-but-Fickle Channel
Distributed, Parallel, and Cluster Computing
Summary
This paper looks at how many devices can share two communication channels, one slow and reliable and one fast but often interrupted. The authors created an algorithm called RACE that smartly switches packets between these channels to keep communication quick even when the fast channel is suddenly disabled. They show that their method performs close to the best possible strategy that already knows when interruptions will happen. They also prove limits on how good any method can be in this setting when costs of switching channels are considered.
What this means in practice
- •For network schedulers: Optimize device scheduling in wireless networks with intermittent fast channels to minimize latency under unpredictable channel availability.
- •For wireless infrastructure operators: Manage spectrum sharing efficiently when fast channels are intermittently revoked, reducing packet delays and switching overhead in multi-channel systems.
Authors
Umesh Biswas, Vini Chaudhary, Shafqat Hasan, Maxwell Young
Abstract
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 $ρ\in \bigl[Ω(\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(ρ+\sqrt{n/m})$, where $m \geq 1$ is the number of fast-channel availability intervals used by OPT. We also prove a worst-case $Ω(\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.