Collision-Free Schedule Acquisition through Slotted ALOHA: Scaling Laws and Fluctuations
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≥ 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→∞, mean acquisition takes O(n2) slots when Γn=n and O(nlog n) slots when Γn∼(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(n2) 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.
Related
- Juggling skill acquisition through air-toss and ground-bounce practice in college students: A study protocol for the TuJuggling cluster-randomised trial
- Schedule optimization for tau-leaping in masked discrete diffusion
- Anytime Training with Schedule-Free Spectral Optimization
- Time-reliability optimization of multi-pass underfill dispensing sequences on printed circuit boards: a schedule-dependent reliability model solved by a multiset-permutation binary-addition-tree algorithm
- Watch Your Step: Adam's Margin Maximization Bias Depends on the Learning Rate Schedule
BibTeX
@misc{dester2026collisionfree,
title = {{Collision-Free Schedule Acquisition through Slotted ALOHA: Scaling Laws and Fluctuations}},
author = {Plínio Santini Dester},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.09934},
eprint = {2609.09934},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09934},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Collision-Free Schedule Acquisition through Slotted ALOHA: Scaling Laws and Fluctuations
AU - Plínio Santini Dester
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2609.09934
UR - https://arxiv.org/abs/2609.09934
AB - 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≥ 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→∞, mean acquisition takes O(n^2) slots when Γ_n=n and O(nlog n) slots when Γ_n∼(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.
ER -