Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy

Gianluca De Marco, Dariusz R. Kowalski, Grzegorz Stachowiak

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

1 Scopus citations

Abstract

A shared channel, also called a multiple access channel, is among the most popular and widely studied models of communication in distributed computing. An unknown number of stations (potentially unbounded) is connected to the channel and can communicate by transmitting and listening. A message is successfully transmitted on the channel if and only if there is a unique transmitter at that time; otherwise the message collides with some other transmission and nothing is sensed by the participating stations. We consider the general framework without collision detection and in which any participating station can join the channel at any moment. The contention resolution task is to let each of the contending stations to broadcast successfully its message on the channel. In this setting we present the first algorithm which exhibits asymptotically optimal Θ(1) throughput and only an O(log k) energy cost, understood as the maximum number of transmissions performed by a single station (where k is the number of participating stations, initially unknown). We also show that such efficiency cannot be reproduced by non-adaptive algorithms, i.e., whose behavior does not depend on the channel history (for example, classic backoff protocols). Namely, we show that non-adaptive algorithms cannot simultaneously achieve throughput Ω (1/polylog (k)) and energy O (log2 k/(log log k)2).

Original languageEnglish (US)
Title of host publication36th International Symposium on Distributed Computing, DISC 2022
EditorsChristian Scheideler
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772556
DOIs
StatePublished - Oct 1 2022
Event36th International Symposium on Distributed Computing, DISC 2022 - Augusta, United States
Duration: Oct 25 2022Oct 27 2022

Publication series

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

Conference

Conference36th International Symposium on Distributed Computing, DISC 2022
Country/TerritoryUnited States
CityAugusta
Period10/25/2210/27/22

Keywords

  • Contention resolution
  • Energy consumption
  • Lower bound
  • Randomized algorithms
  • Shared channel
  • Throughput

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Contention Resolution Without Collision Detection: Constant Throughput And Logarithmic Energy'. Together they form a unique fingerprint.

Cite this