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

Eyal Castiel; Sem Borst; Laurent Miclo; Florian Simatos; Phil Whiting

doi:10.1214/20-AAP1609

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

Stochastic Operations Research

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

5 Citaten (Scopus)

Samenvatting

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² 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.

Originele taal-2	Engels
Pagina's (van-tot)	941-971
Aantal pagina's	31
Tijdschrift	Annals of Applied Probability
Volume	31
Nummer van het tijdschrift	2
DOI's	https://doi.org/10.1214/20-AAP1609
Status	Gepubliceerd - apr. 2021

Bibliografische nota

Funding Information:
Acknowledgments. Authors are listed in alphabetical order except for the first one who is the main contributor. Laurent Miclo acknowledges funding from the French National Research Agency (ANR) under the Investments for the Future (Investissements d’Avenir) program, Grant ANR-17-EURE-0010.

Publisher Copyright:
© Institute of Mathematical Statistics, 2021.

Financiering

Acknowledgments. Authors are listed in alphabetical order except for the first one who is the main contributor. Laurent Miclo acknowledges funding from the French National Research Agency (ANR) under the Investments for the Future (Investissements d’Avenir) program, Grant ANR-17-EURE-0010.

Toegang tot document

10.1214/20-AAP1609

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

@article{b2e866ca4c794972bc43a12614498e10,

title = "Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms",

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.",

keywords = "CSMA algorithms, State space collapse, Stochastic averaging principle",

author = "Eyal Castiel and Sem Borst and Laurent Miclo and Florian Simatos and Phil Whiting",

note = "Publisher Copyright: {\textcopyright} Institute of Mathematical Statistics, 2021.",

year = "2021",

month = apr,

doi = "10.1214/20-AAP1609",

language = "English",

volume = "31",

pages = "941--971",

journal = "Annals of Applied Probability",

issn = "1050-5164",

publisher = "Institute of Mathematical Statistics",

number = "2",

}

TY - JOUR

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

AU - Castiel, Eyal

AU - Borst, Sem

AU - Miclo, Laurent

AU - Simatos, Florian

AU - Whiting, Phil

PY - 2021/4

Y1 - 2021/4

N2 - 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.

AB - 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.

KW - CSMA algorithms

KW - State space collapse

KW - Stochastic averaging principle

UR - http://www.scopus.com/inward/record.url?scp=85097921619&partnerID=8YFLogxK

U2 - 10.1214/20-AAP1609

DO - 10.1214/20-AAP1609

M3 - Article

AN - SCOPUS:85097921619

SN - 1050-5164

VL - 31

SP - 941

EP - 971

JO - Annals of Applied Probability

JF - Annals of Applied Probability

IS - 2

ER -

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

Samenvatting

Bibliografische nota

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit