CS Paper Radar

Dynamic Wakeup under Costly Collisions

Umesh Biswas, Maxwell Young

cs.DC ·submitted 2026-09-28 17:22 UTC · v1
theory

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})$.

Closest papers

Nearest neighbours by meaning across the whole index.

Contention Resolution with a Fast-but-Fickle Channel

cs.DC ·2026-11-09 ·Umesh Biswas, Vini Chaudhary, Shafqat Hasan, Maxwell Young
theory similarity 0.63
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.

0.27

Approximating Minimum Dominating Set with Few Awake Rounds

cs.DC ·2026-08-19 ·Hongyan Ji, Shreyas Pai, Sriram V. Pemmaraju
top venue similarity 0.60
Abstract · Full version of the conference paper published in the proceedings of the 40th International Symposium on Distributed Computing (DISC 2026)

We study the Minimum Dominating Set (MDS) problem in the sleeping CONGEST model (Chatterjee, Gmyr, and Pandurangan, PODC 2020), a generalization of the standard CONGEST model, in which a node may sleep in some rounds and can only compute, send messages, or receive messages when it is awake. The awake complexity of an algorithm in this model is the worst case number (over all inputs and all nodes) of rounds a node is awake for during the execution of the algorithm. While there are several $O(\log Δ)$-approximation algorithms (in expectation) for MDS that run in $O(\log^2 Δ)$ rounds, all of these have $Ω(\log^2 Δ)$ awake complexity. Whether this awake complexity can be improved is the question that drives our work. We present the first $O(\log Δ)$-approximation algorithm for MDS with $O(\log Δ)$ awake complexity. The approximation guarantee holds in expectation, and the algorithm runs in $O(\log^2Δ)$ rounds. We can reduce the awake complexity further, but at the cost of approximation: we present, for any $1<α\le\min\{Δ,\log n\}$, an algorithm in the sleeping CONGEST model that computes an $\tilde{O}(α\log_αΔ)$-approximate dominating set in expectation in $\tilde{O}(\logΔ\cdot \log_α Δ)$ rounds with $\tilde{O}(\log_α Δ)$ awake complexity. Our results depend on a generalization of the CONGEST model Set Cover algorithm of Grunau, Mitrović, Rubinfeld, and Vakilian (SODA 2020) that we develop. This generalization computes an $O(p\cdot q\cdot\log_pΔ)$-approximate dominating set in $O(\log_pΔ\cdot\log_qΔ)$ rounds for parameters $1<p,q\leΔ$. Our sleeping CONGEST algorithms apply a variety of techniques including sampling-based estimation and scheduling using virtual binary trees to the aforementioned 2-parameter Set Cover algorithm.

0.48

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.58
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

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.57
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

Collision-Free Schedule Acquisition through Slotted ALOHA: Scaling Laws and Fluctuations

cs.IT ·2026-09-09 ·Plínio Santini Dester
similarity 0.55
Abstract · Submitted to Wireless Networks

Decentralized networks can learn collision-free periodic transmission schedules, but acquisition can consume much of a finite operating horizon. We characterize acquisition in a reservation protocol for a fixed population of $n$ nodes and a period of $Γ_n\ge n$ slots. Initially, each node attempts independently in each slot with probability proportional to $1/n$. A success reserves a slot that the node reuses every $Γ_n$ slots, retaining it after collisions. Nodes use only their own acknowledgments and small local memory. An exact finite-population Markov reduction, independent of the arrangement of reserved slots, characterizes the time until every node has a distinct reservation. As $n\to\infty$, mean acquisition takes $O(n^2)$ slots when $Γ_n=n$ and $O(n\log n)$ slots when $Γ_n\sim(1+θ)n$, for fixed $θ>0$. With a fixed number $Γ_n-n$ of spare slots, the standard deviation of acquisition time has the same asymptotic order as its mean. If that number diverges while $Γ_n/n$ remains bounded, the ratio of standard deviation to mean tends to zero. A diverging sublinear number of spare slots yields $o(n^2)$ mean acquisition while long-run utilization, the fraction $n/Γ_n$ of slots with successful transmissions, tends to one. Simulations validate these laws and compare acquisition and delivered packets per slot with existing access protocols.

0.31

Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment

cs.LG cs.DS ·2026-10-09 ·Tsubasa Harada, Yasushi Kawase, Hanna Sumita
hot direction similarity 0.55
Abstract · 20 pages

We study simultaneous competitive and regret guarantees for TCP acknowledgment. Each acknowledgment serves all pending packets, and the objective is to minimize the total acknowledgment and waiting costs. It is well known that no deterministic online algorithm achieves a competitive ratio better than $2$. Given $k$ randomized online experts and $0<\varepsilon<1$, we construct a randomized online algorithm whose realized total cost is always at most $(2+\varepsilon)$ times the offline optimal cost $\mathrm{OPT}$ and whose expected regret against the expert with the smallest realized cost is $O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon))$. The algorithm requires no advance knowledge of the number of packets or $\mathrm{OPT}$. Our algorithm controls switching costs between experts and uses the gap between the permitted competitive bound and its current cost to determine when to learn. We also prove lower bounds showing that, for $k\ge 2$, this regret bound is asymptotically optimal in $\mathrm{OPT}$, $k$, and $\varepsilon$, and that $\varepsilon>0$ is necessary for sublinear regret.

0.57

List Update with Time Windows and Delays without Batch-Serving

cs.DS ·2026-11-12 ·Icey Siyi Ai, Jingwei Li, Clifford Stein
theory similarity 0.55
Abstract

We study list update with time windows and delays when every request requires a separate access. Unlike batch-serving models, serving several requests to one element still incurs one access per request, and each access may change the list for subsequent requests. For time windows of overlap at most $k\ge2$, our deterministic First-Element Removal algorithm is $(3-2/k)$-competitive, hence $3$-competitive in general. Against an oblivious adversary, a randomized adaptation of BIT is $7/4$-competitive on arbitrary $2$-overlap inputs. More generally, on inputs without self-overlap, it is $\left(13/4-9/[2(k+1)]\right)$-competitive for every $k\ge2$. For delays, we give a deterministic $5$-competitive algorithm and a lower bound of $2+\sqrt3$ for deterministic delay-unaware algorithms. Our analyses extend inversion potentials with per-request credits that reconcile different service times and orders.

0.21

Is Collision-Free Backoff Worth It in Wi-Fi?

cs.NI ·2026-09-03 ·Mohammad Yousefi, Francesc Wilhelmi, Boris Bellalta
similarity 0.54
Abstract · 8 pages, 5 figures, 3 tables. Submitted to the 17th IFIP Wireless and Mobile Networking Conference (WMNC 2026)

The Distributed Coordination Function (DCF)---the underlying channel access protocol in Wi-Fi, based on Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) and Binary Exponential Backoff (BEB)---is simple and effective, but its performance can degrade with increasing contention due to collisions. Collision-free backoff algorithms replace randomization with deterministic channel access, potentially improving efficiency and predictability. But are collision-free methods, with all their implications in terms of protocol design, sufficient to improve Wi-Fi performance under realistic non-full-buffer traffic with both uplink and downlink transmissions? We investigate this question by comparing three collision-free algorithms, CSMA/ECA (ECA), CSMA/E2CA (E2CA), and deterministic backoff (DetBO), with standard and single-stage BEB. Using system-level simulations, we evaluate full-buffer traffic, non-full-buffer ON/OFF traffic with both uplink and downlink transmissions, and coexistence with legacy BEB stations. Under full-buffer traffic, collision-free operation provides only modest throughput gains, up to 6.3\%. With non-full-buffer traffic, delay is governed primarily by the contention window (CW) rather than by collision avoidance, and collision-free access can even degrade performance under downlink-heavy traffic. Stations fall back to a random backoff at least 93\% of the time, so a collision-free schedule rarely forms outside the AP.

0.27