Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms

Eyal Castiel (Corresponding author), Sem Borst, Laurent Miclo, Florian Simatos, Phil Whiting

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

We examine a queue-based random-access algorithm where activation and deactivation rates are adapted as functions of queue lengths. We establish its heavy traffic behavior on a complete interference graph, which turns out to be nonstandard in two respects: (1) the scaling depends on some parameter of the algorithm and is not the N/N2 scaling usually found in functional central limit theorems; (2) the heavy traffic limit is deterministic. We discuss how this nonstandard behavior arises from the idleness induced by the distributed nature of the algorithm. In order to prove our main result, we develop a new method for obtaining a fully coupled stochastic averaging principle.

Original languageEnglish
Pages (from-to)941-971
Number of pages31
JournalAnnals of Applied Probability
Volume31
Issue number2
DOIs
Publication statusPublished - Apr 2021

Bibliographical note

Publisher Copyright:
© Institute of Mathematical Statistics, 2021.

Keywords

  • CSMA algorithms
  • State space collapse
  • Stochastic averaging principle

Fingerprint

Dive into the research topics of 'Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms'. Together they form a unique fingerprint.

Cite this