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.2018.28
URN: urn:nbn:de:0030-drops-98172
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9817/
Go to the corresponding LIPIcs Volume Portal

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

Local Queuing Under Contention

pdf-format:
LIPIcs-DISC-2018-28.pdf (0.4 MB)

Abstract

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

BibTeX - Entry

@InProceedings{garncarek_et_al:LIPIcs:2018:9817,
  author =	{Pawel Garncarek and Tomasz Jurdzinski and Dariusz R. Kowalski},
  title =	{{Local Queuing Under Contention}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9817},
  URN =		{urn:nbn:de:0030-drops-98172},
  doi =		{10.4230/LIPIcs.DISC.2018.28},
  annote =	{Keywords: Distributed algorithms, local queuing, shared channel, multiple-access channel, adversarial packet arrivals, stability, deterministic algorithms}
}

Keywords: Distributed algorithms, local queuing, shared channel, multiple-access channel, adversarial packet arrivals, stability, deterministic algorithms
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

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