A Lower Bound on the Time Needed in the Worst Case to Resolve Conflicts Deterministically in Multiple Access Channels

Abstract

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. But if k ≥ 2, as a result of the conflict, none of the transmissions succeed. An algorithm to resolve a conflict determines how to schedule retransmissions so that each of the conflicting stations eventually transmits singly to the channel. In this paper, a general model of deterministic algorithms to resolve conflicts is introduced, and it is established that, for all k and n (2 ≤ k ≤ n), Ω(k(log n)/(log k)) time must elapse in the worst case before all k transmissions succeed. © 1985, ACM. All rights reserved.