CS Paper Radar

Contention Resolution with a Fast-but-Fickle Channel

Umesh Biswas, Vini Chaudhary, Shafqat Hasan, Maxwell Young

cs.DC ·submitted 2026-11-09 18:39 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Contention Resolution Against an Adversarial Scheduler

cs.DS ·2026-11-06 ·Michael A. Bender, Martín Farach-Colton, Andrew Krapivin, Pritom Kundu, John Kuszmaul +3 more
theory similarity 0.68
Abstract · 15 pages

In the classical contention-resolution problem, a set of players share a broadcast channel, and a player succeeds in a given time step if it is the only player to broadcast during that step. Implicit in the classical problem is the assumption that every player is free to act on every step: once a player arrives, it participates until it succeeds. We study what happens when that assumption is removed. In our model, an adversarial \emph{scheduler} decides, on each step, which subset of the players gets scheduled to participate in the step. An unscheduled player simply sleeps through the step. We measure a protocol by its \emph{efficiency}: the number of players divided by the expected number of steps in which at least one player was active. Our first result says that, so long as the players are given access to a global clock and to shared randomness, they can achieve efficiency $Ω(1/\log n)$. The players are able to achieve this bound without requiring any channel feedback, and even if the adversarial scheduler is adaptive. We also give a matching lower bound of $O(1 / \log n)$, which holds even with channel feedback, and even for an oblivious scheduler. Our upper bounds all require the players to have access to a shared global clock and to shared randomness. Our final result says that this type of implicit shared state is necessary. If the players have neither a global clock nor shared randomness, then no protocol can achieve efficiency better than $O(\log n / n)$; and this holds even if the other aspects of the problem are designed to be as favorable for the players as possible (the channel gives ternary feedback and the adversary is oblivious).

0.26

Dynamic Wakeup under Costly Collisions

cs.DC ·2026-09-28 ·Umesh Biswas, Maxwell Young
theory similarity 0.63
Abstract

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<ε\le 1/2$. There is a constant $K>0$ such that, when $C\ge K\lg^{1/ε} n$, Lowball has expected latency $O(C^{1/2+ε}\ln C)$ and expected collision cost $O(\sqrt{C})$. Below this threshold, both expectations are $O(n\log^{Θ(1/ε)} 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 $Ω(\sqrt{C})$.

0.23

A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

cs.LG ·2026-11-02 ·Jongyeong Lee, Chansoo Kim
theory similarity 0.60
Abstract · Preprint

We study online channel scheduling for a single queue served by $K$ channels under bandit feedback. We propose a simple best-of-both-worlds policy that explores when the queue is empty. During busy periods, it selects the empirical best channel while the prescribed conditions hold and, if any condition is violated, switches to a robust bandit policy to clear the queue. For arbitrary arrivals and services determined by an oblivious adversary, our policy achieves $\tilde{\mathcal{O}}(\sqrt{K L_T})$ worst-case queue length regret with high probability, where $L_T$ is the longest busy-period length. This result improves the previous $T^{3/4}$ dependence and matches the worst-case lower bound up to logarithmic factors. Under bounded i.i.d. stochastic models with a unique best stabilizing channel, we show that the cumulative queue length regret converges to a finite problem-dependent constant, and further establish the logarithmic expected worst-case queue length regret bound.

0.19

Efficient User Association and Wireless Scheduling with Shorter Time-Scale Rate Adaptation

cs.NI ·2026-09-08 ·Xiaoyi Wu, Huacheng Zeng, Bin Li
top venue similarity 0.58
Abstract

Rate adaptation is a crucial mechanism in IEEE 802.11 networks and next-generation cellular systems. Since the time scale for rate adaptation is typically much shorter than that for user association and scheduling, we investigate a joint design of wireless user association and scheduling and rate adaptation across different time scales to maximize cumulative network throughput while ensuring desired fairness among users. We develop a MaxWeight-type user association and scheduling algorithm that integrates virtual queues -- tracking each user's scheduling debt to maintain fairness -- and Upper Confidence Bound (UCB) estimates in its weight measure. Each selected user then employs the UCB algorithm for rate adaptation on a short time scale. Our theoretical findings reveal that the proposed algorithm achieves cumulative regret that grows with the square root of the time horizon up to a logarithmic factor and results in zero cumulative fairness violation after a certain number of time frames. Furthermore, since the MaxWeight-type algorithm involves evaluating all the feasible schedules that can be exponential to the number of users due to the interference constraints, leading to high computational complexity, we introduce a low-complexity alternative utilizing the so-called pick-and-compare (PC) approach. We demonstrate the effectiveness of both algorithms through simulations based on real-world data traces.

0.42

Tight Bounds on the Cost of Adaptivity for the Meyerson Sketch

cs.DS ·2026-09-06 ·Edith Cohen, Elena Gribelyuk, Pasin Manurangsi, Uri Stemmer
similarity 0.58
Abstract

In online facility location, points arrive one at a time, and the algorithm must either open a facility at the arriving point or route the point to an existing facility. The Meyerson sketch opens a facility at each arriving point with probability proportional to the point's distance to the closest open facility, and requires no state beyond the set of open centers. Due to its simplicity, space efficiency, and strong guarantees against the offline optimum, the Meyerson sketch has become a workhorse of streaming and online clustering. In many such applications, however, the set of open facilities are visible to the process that generates the stream, which can adaptively select future points based on the algorithm's past random choices, voiding its classical guarantees. In this work, we quantify the effect of such adaptivity. We compare an adaptively generated run of the sketch against an \emph{oblivious replay}, an independent execution, with fresh coins, on the very same generated sequence, and study the \emph{adaptivity ratio} of expected adaptive cost to expected replay cost. We determine the worst-case ratio in both directions: adaptivity can neither inflate nor deflate the expected cost, or the number of open facilities, by more than an $O(\logΔ/\log\logΔ)$ factor, where $Δ$ is the aspect ratio of the input points (the ratio of the largest to the smallest pairwise distance). This is asymptotically tight as there are deterministic generators on the real line that inflate or deflate the cost by an $Ω(\logΔ/\log\logΔ)$ factor. We show that these robustness guarantees carry over to Meyerson-based sketches for approximate $k$ clustering with sketch size $O(k\,\mathrm{polylog}(n))$.

0.19

Multi-connectivity in Wireless Access

cs.NI ·2026-11-17 ·Danny De Vleeschauwer, Chia-Yu Chang, Koen De Schepper, Lutz Ewe, Simone Bolettieri
similarity 0.58
Abstract

This paper investigates whether or not multi-connectivity, in which a User Equipment (UE) can simultaneously connect to multiple Access Points (APs), can offer a better Quality of Experience (QoE) to the users. Intuitively, multi-connectivity should offer a smoother bit rate (possibly at the expense of the average bit rate being slightly lower), so that adaptive applications can better determine at which throughput to send without introducing queueing latency. We mainly concentrate on how to share the resources of the APs amongst the UEs, modelling the lower layers via spectral efficiency and the higher layers via utility and its fluctuation. We explore various policies for resource allocation. Our results demonstrate that from the application point of view multi-connectivity is beneficial and show how to tune the parameters of the policies to obtain the best trade-off between average utility and its fluctuation.

0.27

A Tight Linear Deterministic Competitive Ratio for Fully Online KV-Cache Scheduling

cs.DS ·2026-08-14 ·Ian D'Ambrosio
theory similarity 0.57
Abstract · 6 pages. The exact fully online model, fixed-memory-before-scheduler quantifier order, serial upper bound, and wide-short lower bound are ch…

Jaillet et al. introduced a fully online model for batching nonpreemptive LLM requests under a growing KV-cache memory constraint. For total end-to-end latency they proved that every deterministic algorithm has competitive ratio Omega(sqrt(n)), while the elementary sequential upper bound is n. We close this gap. Let R_det(n,M) be the optimal deterministic ratio for exactly n requests at memory M, and let R_det(n)=sup_M R_det(n,M). For every n >= 2 we prove (n-1)/12 <= R_det(n) <= n, so R_det(n)=Theta(n). The lower bound releases one memory-filling long request, observes its deterministic start time, and then releases n-1 wide one-token requests halfway through the long run. No short request can overlap the long one, whereas a hindsight schedule runs the two groups in the opposite order when useful. The hard instance uses the explicit fixed memory M=2(n-1)n. The upper bound is achieved by a uniform causal serial policy. The exact model, causality argument, both comparator branches, and quantifier order are machine-checked in Lean 4. Exact finite controls and replay commands accompany the proof.

0.07

Self-Adaptive Threshold ALOHA

cs.NI ·2026-09-13 ·Ahsen Topbas, Aimin Li, Elif Tugce Ceran
benchmark similarity 0.57
Abstract · 5 pages, 3 figures

We propose Self-Adaptive Threshold ALOHA (SATA), a distributed random-access policy to minimize the Age of Information (AoI). SATA uses 1-bit broadcast feedback and requires no explicit coordination or message passing among nodes. {We show that this minimal feedback is sufficient for each node to perfectly track the number of active users and adjust its access probabilities accordingly.} For any initial network state, SATA converges to a collision-free TDMA steady state in finite time whenever the age threshold satisfies $Γ\geq n$, where $n$ is the network size. We derive closed-form expressions for the long-term average AoI and throughput in steady state, and establish that, for $Γ=n$, the expected transient duration scales as $O(n\log n)$. Simulation results confirm that SATA closely approaches TDMA performance across a wide range of network sizes, significantly outperforming Slotted ALOHA, Threshold ALOHA, and 1-persistent Threshold Slotted ALOHA. Notably, the performance gap between SATA and the benchmark random-access policies becomes more pronounced as network size grows.

0.34