Stability conditions for a discrete-time decentralised medium access algorithm

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 of .packets per time slot.Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously.The algorithm we study is standard in the following sense: a node with an 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 nonzero.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 the condition .<2/5.This result is intuitive for the circle topology as the throughput each node receives in the 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 us to prove the result.)The result is not intuitive for the line topology as in the saturated system some nodes receive a throughput lower than 2/5.