We will present the paper: Shneer, S., & Stolyar, A. (2018). Stability conditions for a discrete-time decentralised medium access algorithm. The Annals of Applied Probability, 28(6), 3600-3628.
We consider a stochastic queueing system modelling the behaviour of a wireless network with nodes employing a discrete-time version of the standard decentralised medium access algorithm. The system is unsaturated – each node receives an exogenous flow of packets at the rate ? packets per time slot. Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously. The algorithm we study is standard in that: a node with empty queue does not compete for medium access; the access procedure by a node does not depend on its queue length, as long as it is non-zero. Two system topologies are considered, with nodes arranged in a circle and in a line. We prove that, for either topology, the system is stochastically stable under condition λ < 2/5. This result is intuitive for the circle topology as the throughput each node receives in a saturated system (with infinite queues) is equal to the so-called parking constant, which is larger than 2/5. (This fact, however, does not help to prove our result.) The result is not intuitive at all for the line topology as in a saturated system some nodes receive a throughput lower than 2/5.