Local queuing under contention

Paweł Garncarek, Tomasz Jurdziński, Dariusz R. Kowalski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


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.

Original languageEnglish (US)
Title of host publication32nd International Symposium on Distributed Computing, DISC 2018
EditorsUlrich Schmid, Josef Widder
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770927
StatePublished - Oct 1 2018
Externally publishedYes
Event32nd International Symposium on Distributed Computing, DISC 2018 - New Orleans, United States
Duration: Oct 15 2018Oct 19 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference32nd International Symposium on Distributed Computing, DISC 2018
Country/TerritoryUnited States
CityNew Orleans


  • Adversarial packet arrivals
  • Deterministic algorithms
  • Distributed algorithms
  • Local queuing
  • Multiple-access channel
  • Shared channel
  • Stability

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Local queuing under contention'. Together they form a unique fingerprint.

Cite this