INDUCED IDLENESS LEADS TO DETERMINISTIC HEAVY TRAFFIC LIMITS FOR QUEUE-BASED RANDOM-ACCESS ALGORITHMS

• 成果类型: Article
• 署名作者: Castiel, Eyal; Borst, Sem; Miclo, Laurent; Simatos, Florian; Whiting, Phil
• 署名单位: Universite de Toulouse; Institut Superieur de l'Aeronautique et de l'Espace (ISAE-SUPAERO); Eindhoven University of Technology; Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Centre National de la Recherche Scientifique (CNRS); Macquarie University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/20-AAP1609
• 发表日期: 2021
• 页码: 941-971
• 关键词: polling systems; fluid limit; network; MODEL; inequalities

摘要

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/N-2 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.