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

Access Restriction
Subscribed

 Author Greenberg, Albert G. ♦ Winograd, Schmuel Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1985 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract A problem related to the decentralized control of a multiple access channel is considered: Suppose $\textit{k}$ stations from an ensemble of $\textit{n}$ simultaneously transmit to a multiple access channel that provides the feedback 0, 1, or 2+, denoting $\textit{k}$ = 0, $\textit{k}$ = 1, or $\textit{k}$ ≥ 2, respectively. If $\textit{k}$ = 1, then the transmission succeeds. But if $\textit{k}$ ≥ 2, as a result of the conflict, none of the transmissions succeed. An algorithm to $\textit{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 $\textit{k}$ and $\textit{n}$ (2 ≤ $\textit{k}$ ≤ $\textit{n}),$ $&OHgr;(\textit{k}(log$ $\textit{n})/(log$ $\textit{k}))$ time must elapse in the worst case before all $\textit{k}$ transmissions succeed. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1985-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 32 Issue Number 3 Page Count 8 Starting Page 589 Ending Page 596

#### Open content in new tab

Source: ACM Digital Library