OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

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

Castiel, Eyal and Simatos, Florian and Borst, Sem and Whiting, Phil and Miclo, Laurent Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms. (2021) Annals of Applied Probability, 31 (2). 941-971. ISSN 1050-5164

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://doi.org/10.1214/20-AAP1609


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 highly 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 developed a new method for obtaining a fully coupled stochastic averaging principle.

Item Type:Article
HAL Id:hal-03203131
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Other partners > Ecole des Hautes Etudes en Sciences Sociales - EHESS (FRANCE)
French research institutions > Institut national de recherche pour l'agriculture, l'alimentation et l'environnement - INRAE (FRANCE)
Université de Toulouse > Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)
Other partners > Macquarie University (AUSTRALIA)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Eindhoven University of Technology - TU/e (NETHERLANDS)
Laboratory name:
Deposited On:06 Jan 2021 14:14

Repository Staff Only: item control page