Contention resolution on a restrained channel

Elijah Hradovich, Marek Klonowski, Dariusz R. Kowalski

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

4 Scopus citations


We examine deterministic contention resolution on a multiple-access channel when packets are injected continuously by an adversary to the buffers of n available stations in the system, arbitrarily at rate at most ? packets per round. The aim is to successfully transmit packets and maintain system stability, that is, bounded queues, even in infinite executions. The largest injection rate for which a given contention resolution algorithm guaranties stability is called (algorithm's) throughput. In contrast to the previous work, we consider a channel in which there is a strict limit k on the total number of stations allowed to transmit or listen to the channel at a given time, that can never be exceeded; we call such channel a k-restrained channel. We construct adaptive and full sensing protocols with optimal throughput 1 and almost optimal throughput 1-1/n, respectively, in a constant-restrained channel. By contrast, we show that restricted protocols based on schedules known in advance obtain throughput at most k n, 1{3 n. We also support our theoretical analysis by simulation results of our algorithms in systems of moderate, realistic sizes and scenarios, and compare them with popular backoff protocols.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 26th International Conference on Parallel and Distributed Systems, ICPADS 2020
PublisherIEEE Computer Society
Number of pages10
ISBN (Electronic)9781728190747
StatePublished - Dec 2020
Externally publishedYes
Event26th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2020 - Virtual, Hong Kong, Hong Kong
Duration: Dec 2 2020Dec 4 2020

Publication series

NameProceedings of the International Conference on Parallel and Distributed Systems - ICPADS
ISSN (Print)1521-9097


Conference26th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2020
Country/TerritoryHong Kong
CityVirtual, Hong Kong


  • Adversarial queueing
  • Contention resolution
  • Multiple-access channel
  • Restrained channel
  • Stability
  • Throughput

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Contention resolution on a restrained channel'. Together they form a unique fingerprint.

Cite this