Stability of a standard decentralised medium access

Seva Shneer, Alexander Stolyar

Research output: Contribution to journalConference article


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.

Original languageEnglish (US)
Pages (from-to)33-35
Number of pages3
JournalPerformance Evaluation Review
Issue number2
StatePublished - Jan 17 2019
Event2018 Workshop on MAthematical Performance Modeling and Analysis, MAMA 2018 and Workshop on Critical Infrastructure Network Security, CINS 2018 - Irvine, United States
Duration: Jun 1 2018 → …


  • Carrier-Sense Multiple Access
  • Discrete parking process
  • Medium access protocols
  • Non-monotone process
  • Queueing networks
  • Stochastic stability
  • Wireless systems

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Stability of a standard decentralised medium access'. Together they form a unique fingerprint.

  • Cite this