Induced idleness leads to deterministicheavy traffic limits for queue-basedrandom-access algorithms

Abstract

We examine a queue-based random-access algorithm where ac-tivation 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 dependson some parameter of the algorithm and is not theN/N2scaling usuallyfound in functional central limit theorems; (2) the heavy traffic limit isdeterministic. We discuss how this nonstandard behavior arises from theidleness induced by the distributed nature of the algorithm. In order toprove our main result, we develop a new method for obtaining a fully cou-pled stochastic averaging principle.

Replaces

Eyal Castiel, Sem Borst, Laurent Miclo, Florian Simatos, and Phil Whiting, “Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms”, TSE Working Paper, n. 20-1129, August 2020.

Reference

Eyal Castiel, Sem Borst, Laurent Miclo, Florian Simatos, and Phil Whiting, “Induced idleness leads to deterministicheavy traffic limits for queue-basedrandom-access algorithms”, Annals of Applied Probability, vol. 31, n. 2, April 2021, pp. 941–971.