Thumbnail
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

   Open content in new tab
Source: ACM Digital Library