paper

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

arXiv:2609.09934

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 nodes and a period of slots. Initially, each node attempts independently in each slot with probability proportional to . A success reserves a slot that the node reuses every 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 , mean acquisition takes slots when and slots when , for fixed . With a fixed number of spare slots, the standard deviation of acquisition time has the same asymptotic order as its mean. If that number diverges while remains bounded, the ratio of standard deviation to mean tends to zero. A diverging sublinear number of spare slots yields mean acquisition while long-run utilization, the fraction of slots with successful transmissions, tends to one. Simulations validate these laws and compare acquisition and delivered packets per slot with existing access protocols.

arXiv commentSubmitted to Wireless Networks