TY - GEN
T1 - Stable memoryless queuing under contention
AU - Garncarek, Pawel
AU - Jurdziński, Tomasz
AU - Kowalski, Dariusz R.
N1 - Funding Information:
Funding This work was funded by Polish National Science Center grant 2017/25/B/ST6/02010.
Publisher Copyright:
© Paweł Garncarek, Tomasz Jurdziński, and Dariusz R. Kowalski.
PY - 2019/10
Y1 - 2019/10
N2 - In this work we study stability of local memoryless packet scheduling policies in a distributed system of n nodes/queues under contention. The local policies at nodes may only access their current local queues, and have no other feedback from the underlying distributed system. Moreover, their memory is limited to some basic parameters. The packets arrive at queues according to arrival patterns controlled by an adversary restricted only by injection rate ρ and burstiness b, or driven by a stochastic process; the former model analyzes worst-case stability while the latter – average case. We assume that the underlying distributed system is a classic shared channel, in which no two packets could be successfully scheduled (and removed from queues) at the same time. We show that there is a local memoryless scheduling policy which is both adversarially and stochastically stable for injection rates Ω(1/log n). Another algorithm achieves even higher – constant – stable injection rate, but only for a bounded range of burstiness. The first algorithm is utilizing properties of interleaved ultra-selectors, for which we prove stronger properties than known so far, while the second one is based on entirely new concept of selector with thresholds, unlike previously considered binary selectors/codes in the literature. Note that popular Backoff algorithms, some of which achieve stability for constant (stochastic) injection rates [18], use memory to record current state (e.g., the number of unsuccessful transmissions or the result of random sampling in each window) as well as randomization and feedback from the channel; unlike solutions in this work, which are memoryless and do not rely on randomization or channel feedback (thus, could be used independently from the link layer protocols).
AB - In this work we study stability of local memoryless packet scheduling policies in a distributed system of n nodes/queues under contention. The local policies at nodes may only access their current local queues, and have no other feedback from the underlying distributed system. Moreover, their memory is limited to some basic parameters. The packets arrive at queues according to arrival patterns controlled by an adversary restricted only by injection rate ρ and burstiness b, or driven by a stochastic process; the former model analyzes worst-case stability while the latter – average case. We assume that the underlying distributed system is a classic shared channel, in which no two packets could be successfully scheduled (and removed from queues) at the same time. We show that there is a local memoryless scheduling policy which is both adversarially and stochastically stable for injection rates Ω(1/log n). Another algorithm achieves even higher – constant – stable injection rate, but only for a bounded range of burstiness. The first algorithm is utilizing properties of interleaved ultra-selectors, for which we prove stronger properties than known so far, while the second one is based on entirely new concept of selector with thresholds, unlike previously considered binary selectors/codes in the literature. Note that popular Backoff algorithms, some of which achieve stability for constant (stochastic) injection rates [18], use memory to record current state (e.g., the number of unsuccessful transmissions or the result of random sampling in each window) as well as randomization and feedback from the channel; unlike solutions in this work, which are memoryless and do not rely on randomization or channel feedback (thus, could be used independently from the link layer protocols).
KW - Adversarial injections
KW - Memoryless algorithms
KW - Online algorithms
KW - Packet scheduling
KW - Stability
KW - Stochastic injections
UR - http://www.scopus.com/inward/record.url?scp=85074587681&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85074587681&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.DISC.2019.17
DO - 10.4230/LIPIcs.DISC.2019.17
M3 - Conference contribution
AN - SCOPUS:85074587681
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 33rd International Symposium on Distributed Computing, DISC 2019
A2 - Suomela, Jukka
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 33rd International Symposium on Distributed Computing, DISC 2019
Y2 - 14 October 2019 through 18 October 2019
ER -