License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.17
URN: urn:nbn:de:0030-drops-113244
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11324/
Go to the corresponding LIPIcs Volume Portal

Garncarek, Pawel ; Jurdzinski, Tomasz ; Kowalski, Dariusz R.

Stable Memoryless Queuing under Contention

pdf-format:
LIPIcs-DISC-2019-17.pdf (0.5 MB)

Abstract

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 rho 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 Omega(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 [Johan Håstad et al., 1996], 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). {}

BibTeX - Entry

@InProceedings{garncarek_et_al:LIPIcs:2019:11324,
  author =	{Pawel Garncarek and Tomasz Jurdzinski and Dariusz R. Kowalski},
  title =	{{Stable Memoryless Queuing under Contention}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11324},
  URN =		{urn:nbn:de:0030-drops-113244},
  doi =		{10.4230/LIPIcs.DISC.2019.17},
  annote =	{Keywords: packet scheduling, online algorithms, adversarial injections, stochastic injections, stability, memoryless algorithms}
}

Keywords: packet scheduling, online algorithms, adversarial injections, stochastic injections, stability, memoryless algorithms
Collection: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 08.10.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI