A fast non-adaptive algorithm for conflict resolution in multiple access channels.

A basic problem is 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 0(k + k log n/k) in the worst case. This algorithm depends crucially on feedback information provided by the channel. We show that if k is given a (a priori) then such conflicts can be resolved in time 0(k + k log n/k) without feedback.