Conflict Resolution in a Multiple Access Channel

Nonadaptive conflict-resolution algorithms for a multiple access channel are considered. A worst-case lower bound on the algorithm time is obtained, which coincides (up to a constant multiplier) with a well-known upper bound. A constructive technique for the design of nonadaptive algorithms is proposed. If the conflict multiplicity is fixed and the number of transmitting stations $n$ tends to infinity, then an algorithm with minimal (up to a constant multiplier) worst-case time is constructed in almost linear time $O(n\log_2^3n)$.