A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels.

A problem related to the decentralized control of a multiple access channel is considered: Suppose k stations from an ensemble of n simultaneously transmit to a multiple access channel that provides the feedback 0, 1 or 2+, denoting k = 0, k = 1, or k >= 2 respectively. If k = 1 then the transmission succeeds. In this paper we introduce a general model of deterministic algorithms to resolve conflict, and establish that, for all k and n (2