An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels
János Komlós, Albert G. Greenberg · IEEE Transactions on Information Theory · 1985
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 {\em tree algorithm} that resolves conflicts amongkstations from an ensemble ofnin time\Theta (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 ifkis given {\em a priori} then such conflicts can be resolved in time\Theta (k + k \log (n / k))using an algorithm in which the corresponding choices do not depend on feedback.