Efficient Local Medium Access

Pawel Garncarek, Tomasz Jurdzinski, Dariusz R. Kowalski

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


Shah, Shin and Tetali [25] initiated the study of queuing systems on the medium access channel with arbitrary interference graph. The graph models dependencies between the channel members - any two connected by an edge are dependent. This problem could be also re-stated as a query system with dependent elements or local scheduling of dependent packets/jobs. In short, if two dependent units, also called stations, want to transmit (or be in the same query, or do jobs in parallel), there is a conflict and none of them succeeds. The problem is particularly challenging, if the units need to make their decisions locally, without any coordination. Prior the paper by Shah, Shin and Tetali [FOCS 2011], the main focus was on the clique graph - even in this simple topology, many problems related to stability remain open. While the solution by Shah, Shin and Tetali [FOCS 2011] is semi-local, as nodes make use of information about interfering neighbors in the graph, we provide the first purely local stable algorithms. In particular, in our algorithms stations make their decision whether to transmit or not based only on looking at their local queues. Based only on this feature, and without using a priori knowledge of topology, we design an algorithm that allows all stations for implicit transferring information to and from all other stations. We use it as a tool for developing universally stable algorithms for the problem of queuing messages - i.e., guaranteeing bounded queues when, on average, less than one independent set is injected per round. The first one is stable in adversarial (worst-case) sense, the second one - in stochastic sense (average-case). We also prove optimality of our algorithm in adversarial sense: no algorithm can be stable against injections with rate ρ=1 (when, on average, one independent set is injected per round). Moreover, for the class of non-adaptive protocols, we show that it is not possible to achieve stability for any injection rate ω(1/log m), where m is the size of the largest clique in the interference graph. We extend the result by showing that such protocols are not stable on some interference graphs with no cliques of size at least 3 even for injection rates ω([3](log n)/n). This result separates the model with general interference graphs from the classical model of a multiple access channel (in which the interference graph is a clique), in which there exist non-adaptive algorithms stable for adversarial injection rates O(1/log2 n).

Original languageEnglish (US)
Title of host publicationSPAA 2020 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Number of pages11
ISBN (Electronic)9781450369350
StatePublished - Jul 6 2020
Event32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2020 - Virtual, Online, United States
Duration: Jul 15 2020Jul 17 2020

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures


Conference32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2020
Country/TerritoryUnited States
CityVirtual, Online


  • adversarial packet arrivals
  • deterministic algorithms
  • distributed algorithms
  • local queuing
  • multiple-access channel
  • shared channel
  • stability

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'Efficient Local Medium Access'. Together they form a unique fingerprint.

Cite this