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

Preview

Text Download (488kB) | Preview

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.

Available Versions of this Item

• Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms. (deposited 26 Aug 2020 10:10)
  • Induced idleness leads to deterministicheavy traffic limits for queue-basedrandom-access algorithms. (deposited 25 Mar 2021 10:19) [Currently Displayed]