TY - GEN
T1 - Local queuing under contention
AU - Garncarek, Paweł
AU - Jurdziński, Tomasz
AU - Kowalski, Dariusz R.
N1 - Funding Information:
Supported by Polish National Science Center grant 2017/25/B/ST6/02010.
Publisher Copyright:
© Paweł Garncarek, Tomasz Jurdzinski, and Dariusz R. Kowalski.
PY - 2018/10/1
Y1 - 2018/10/1
N2 - We study stability of local packet scheduling policies in a distributed system of n nodes. The local policies at nodes may only access their local queues, and have no other feedback from the underlying distributed system. The packets arrive at queues according to arrival patterns controlled by an adversary restricted only by injection rate ρ and burstiness b. In this work, we assume that the underlying distributed system is a shared channel, in which in order to get rid of a packet from the queue, a node needs to schedule it for transmission on the channel and no other packet is scheduled for transmission at the same time. We show that there is a local adaptive scheduling policy with relatively small memory, which is universally stable on a shared channel, that is, it has bounded queues for any ρ < 1 and b ≥ 0. On the other hand, without memory the maximal stable injection rate is O(1/log n). We show a local memoryless (non-adaptive) scheduling policy based on novel idea of ultra strong selectors which is stable for slightly smaller injection c/log 2 n, for some constant c > 0.
AB - We study stability of local packet scheduling policies in a distributed system of n nodes. The local policies at nodes may only access their local queues, and have no other feedback from the underlying distributed system. The packets arrive at queues according to arrival patterns controlled by an adversary restricted only by injection rate ρ and burstiness b. In this work, we assume that the underlying distributed system is a shared channel, in which in order to get rid of a packet from the queue, a node needs to schedule it for transmission on the channel and no other packet is scheduled for transmission at the same time. We show that there is a local adaptive scheduling policy with relatively small memory, which is universally stable on a shared channel, that is, it has bounded queues for any ρ < 1 and b ≥ 0. On the other hand, without memory the maximal stable injection rate is O(1/log n). We show a local memoryless (non-adaptive) scheduling policy based on novel idea of ultra strong selectors which is stable for slightly smaller injection c/log 2 n, for some constant c > 0.
KW - Adversarial packet arrivals
KW - Deterministic algorithms
KW - Distributed algorithms
KW - Local queuing
KW - Multiple-access channel
KW - Shared channel
KW - Stability
UR - http://www.scopus.com/inward/record.url?scp=85059613768&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85059613768&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.DISC.2018.28
DO - 10.4230/LIPIcs.DISC.2018.28
M3 - Conference contribution
AN - SCOPUS:85059613768
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 32nd International Symposium on Distributed Computing, DISC 2018
A2 - Schmid, Ulrich
A2 - Widder, Josef
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 32nd International Symposium on Distributed Computing, DISC 2018
Y2 - 15 October 2018 through 19 October 2018
ER -