A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels
- 1 July 1985
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 32 (3), 589-596
- https://doi.org/10.1145/3828.214125
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.Keywords
This publication has 4 references indexed in Scilit:
- Cutoff points for roll call protocols in multiple access systemsIEEE Transactions on Information Theory, 1987
- A new upper bound to the throughput of a multi-access broadcast channelIEEE Transactions on Information Theory, 1982
- On the capacity of infinite population multiple access protocolsIEEE Transactions on Information Theory, 1982
- An Adaptive Technique for Local DistributionIEEE Transactions on Communications, 1978