An Asymptotically Nonadaptive Algorithm for Conflict Resolution in Multiple-Access Channels

Janos Komlos, Albert G. Greenberg

Research output: Contribution to journalArticle

89 Scopus citations


A basic problem in the decentralized control of a multiple access channel is to resolve the conflicts that arise when several stations transmit simultaneously to the channel. Capetanakis, Hayes, and Tsybakov and Mikhailov found a deterministic tree algorithm that resolves conflicts among k stations from an ensemble of n in time Θ(k + k log(n/k)) in the worst case. In this algorithm, at each step, the choice of which stations to enable to transmit depends crucially on feedback information provided by the channel. We show that if k is given a priori then such conflicts can be resolved in time Θ(k + k log(n/k)) using an algorithm in which the corresponding choices do not depend on feedback.

Original languageEnglish (US)
Pages (from-to)302-306
Number of pages5
JournalIEEE Transactions on Information Theory
Issue number2
StatePublished - Mar 1985
Externally publishedYes


All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this