Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel

Gianluca De Marco, Dariusz R. Kowalski

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


A classical problem in addressing a decentralized multiple-access channel is resolving conflicts when a set of stations attempt to transmit at the same time on a shared communication channel. In a static scenario, i.e., when all stations are activated simultaneously, Komlos and Greenberg [IEEE Trans. Inform. Theory, 31 (1985), pp. 302-306] in their seminal work showed that it is possible to resolve the conflict among k stations from an ensemble of n, with a nonadaptive deterministic algorithm in time O(k +k log(n/k)) in the worst case. In this paper we show that in a dynamic scenario, when the stations can join the channel at arbitrary rounds, there is a nonadaptive deterministic algorithm guaranteeing a successful transmission for each station in only a slightly bigger time: O(k log n log log n) in the worst case. This almost matches the O(k log n/ log k) lower bound by Greenberg and Winograd [J. ACM, 32 (1985), pp. 589-596] that holds even in much stronger settings: for adaptive algorithms, in the static scenario, and with additional channel feedback-collision detection. In terms of channel utilization, our result implies throughput, understood as the average number of successful transmissions per time unit, O(1/(log n log log n)) on the dynamic deterministic channel.

Original languageEnglish (US)
Pages (from-to)868-888
Number of pages21
JournalSIAM Journal on Computing
Issue number3
StatePublished - Jan 1 2015
Externally publishedYes


  • Contention resolution
  • Deterministic algorithms
  • Distributed algorithms
  • Latency
  • Multiple-access channel
  • Throughput

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'Fast nonadaptive deterministic algorithm for conflict resolution in a dynamic multiple-access channel'. Together they form a unique fingerprint.

Cite this