CS Paper Radar

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

Plínio Santini Dester

cs.IT ·submitted 2026-09-09 09:26 UTC · v3

Abstract

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.

Comment
Submitted to Wireless Networks

Closest papers

Nearest neighbours by meaning across the whole index.

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

Fundamental limits to identifying node and tie memory in temporal networks: marginal artefacts and spreading dynamics

cs.SI physics.soc-ph ·2026-09-09 ·Michele Tizzani
published similarity 0.58
Abstract · 24 pages, 8 figures; 43 pages Supplementary Material

Temporal-network models place the memory seen in contact data either on nodes, through self-excitation (branching ratio n_node), or on ties, through reinforcement (kappa). The two choices reproduce the same coarse statistics but predict different epidemics. We ask whether contact data can tell them apart and find two limits. The first is attribution. When the initiator of every event is recorded, the likelihood factorises into a timing block containing n_node and a selection block containing kappa, so the two are estimated independently. When it is not, as in proximity data, a missing-information term couples them, with a size set by the entropy of the initiator posterior. The second issue is interpretation. Even where the mechanisms separate, the fitted n_node might not accurately measure memory and it may be set by the distribution of waiting times between events. Shuffling each node's inter-event order, which keeps that distribution, typically changes the estimated n_node by less than 10%; this is a bias that longer records and a flexible scale-free kernel do not remove. Whether node memory is present must therefore be decided by model-free statistics, which find only weak order memory in the proximity records, far less than the fitted n_node around 0.9 would imply. Tie reinforcement remains recoverable, although a latent initiator inflates it by 28%-45%. The two limits lead to two recommendations: record who initiates each contact, and test a fitted node memory against shuffled and model-free benchmarks before interpreting it. On a high-school record, simulating from the fitted node memory under-predicts outbreak sizes by up to a factor of 2, whereas keeping tie reinforcement alone is closer at low transmissibility but overshoots at high.

0.38

Self-Adaptive Threshold ALOHA

cs.NI ·2026-09-13 ·Ahsen Topbas, Aimin Li, Elif Tugce Ceran
benchmark similarity 0.58
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

Counting in Population Protocols on Graphs

cs.DC ·2026-08-18 ·Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Thorsten Götte, Lukas Hintze +1 more
published similarity 0.58
Abstract · Accepted to DISC 2026

We consider the problem of counting the number of agents in a population protocol where the agents are connected by an underlying graph $G=(V,E)$ with $|V|=n$ nodes. In each step, a random scheduler selects an edge uniformly at random, and the incident nodes make a state transition. As per standard assumptions, agents are identical and anonymous, that is, have no identifiers. To break symmetry, in each interaction one of the agents is declared as the initiator uniformly at random. Our size counting protocol uses $\tilde O(n)$ states and stabilizes in $O( B(G) \cdot \log^2(n) + L(G) \cdot \log(n))$ interactions with high probability, where $B(G)$ is the broadcast time and $L(G)$ is the load balancing time. Our protocol is based on novel protocols for sampling independent random bits (given that the scheduler determines an initiator and responder) and approximating $\log n$ up to an additive error of $O(\log \log n)$ with high probability. The latter uses $O(poly\log(n))$ states and $O(B(G)\cdot\log^2 n)$ interactions. Both results may be of independent interest. The main protocol for exact counting requires the presence of a unique leader, the other two do not. None of the protocols requires any knowledge about the graph $G$. We conclude with impossibility results for terminating uniform population protocols that compute graph-size properties (like counting nodes or determining parity) with and without a leader.

0.46

Online Network Design with Maximum Delay and Stochastic Arrivals

cs.DS ·2026-11-10 ·Tianhang Lu
theory similarity 0.58
Abstract

We study online network services that combine pending requests into batches. Each batch pays for its spatial service and for the waiting time of its oldest request. The objective is the sum of these costs over all batches. Thus requests can share both a spatial purchase and one maximum-delay charge. We assume independent Poisson arrivals of known rates, while actual requests are revealed only upon arrival. For stateless services, suppose that each type has an attainable minimum cost when served alone, that every batch costs at least the stand-alone minimum of each type it contains, and that one finite-cost action can serve any batch, regardless of its request multiplicities. We give a deterministic algorithm with long-run ratio of expectations $e/(e-1)$ against an unrestricted offline optimum. This factor is optimal, even allowing randomization, already at one request location. The key comparison measures the union of time intervals associated with requests. The theorem applies directly to multi-root and pair aggregation on trees. We also study facility location, where each request pays its own connection distance and the bounded-action assumption can fail. A deterministic policy gives a ratio $3$ for arbitrary nonnegative opening costs. It immediately serves a finite initial set of requests, computes an assignment from their observed arrival gaps, and then keeps that assignment fixed. Its analysis combines Poisson insertion with a time-slice packing bound on the offline optimum. Every guarantee includes the full cost of completing finite inputs without an end-of-input signal.

0.15

Locality Meets Interference: Structure and Scheduling in Radio Multicasting

cs.DC cs.DS ·2026-11-12 ·Qin Xin
theory similarity 0.57
Abstract · 21 pages

We study multipoint-to-multipoint multicasting in synchronous radio networks with unknown participant locations and unrestricted message aggregation. Let $n$ be the network size, $k$ the number of participants, and $d$ their hop diameter. A supplied distance-two coloring with $C$ colors yields completion within $(C-1)d+1$ slots and at most $nk$ transmissions. In unit disk graphs, coordinates, one-hop neighbor data, and a common degree bound $Δ_0$ suffice for a $15(Δ_0+1)$-color schedule. A known fixed separation bound permits optimal deterministic $Θ(d)$ completion from coordinates alone. Without geometric data, strong selectivity gives $O(d\min\{n,(Δ_0+1)^2\log n\})$ slots when $n$ is known. Independent random transmission gives $O((Δ_0+1)(d+\log(k/η)))$ slots with failure probability at most $η$; for fixed $Δ_0$, this simplifies to $O(d+\log(1/η))$. A star construction shows that the logarithmic term is necessary for this random rule when the degree grows. We extend color schedules to fixed deletions and subgraphs connected over bounded windows of cycles. Separate conditional reductions preserve additive costs under diameter guessing and control parameter-table and cluster preprocessing. Finally, a counterexample shows that pruning and reranking a breadth-first tree can destroy interference-free delivery. For one-hop designated delivery with receiver degree at most $b$, we prove that the optimal schedule length equals the chromatic number of an associated conflict graph and is at most $2b-1$, with matching examples.

0.29

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

Tight Lower Bounds for Distributional Paging

cs.DS ·2026-10-29 ·Ali Vakilian
similarity 0.57
Abstract

Distributional paging seeks a polynomial-time eviction rule that competes with the optimal \emph{online} policy $\mathrm{OPT}$ when requests come from a known stochastic source. Two algorithms by Lund, Phillips, and Reingold [FOCS, 1994] are canonical. Their randomized \emph{dominating distribution} algorithm, for Markov sources, evicts a page drawn from a distribution over the cache satisfying pairwise linear inequalities; their deterministic \emph{median} algorithm, for sources with independent inter-arrival times across pages, evicts the cached page with the largest lower median of its conditional next-request time. Their original guarantees of $4$ and $5$ were recently improved to $2$ and $4$ by Pabbaraju and Vakilian [ICALP 2025]. We show that neither improved constant can be reduced in its respective source model. For Markov paging, we give two complementary factor-$2$ lower-bound constructions, each with an explicit polynomial-time dominating selector. A directed-cycle family has ratio $2k/(k+1)$, while a recurrent four-page family with cache size three has ratio $2-4\varepsilon/3$. For the independent inter-arrival model, we show that the median algorithm is not $c$-competitive for any $c<4$. These are separate results for distinct stochastic models. Matching the known upper bounds, they establish tight competitive ratios of $2$ and $4$, respectively, improving on previous lower bounds of $1.5907$ and $1.511$.

0.10