### Contention resolution with constant expected delayContention resolution with constant expected delay

Access Restriction
Subscribed

 Author Goldberg, Leslie Ann ♦ Mackenzie, Philip D. ♦ Paterson, Mike ♦ Srinivasan, Aravind Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2000 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Markov chains ♦ Contention resolution ♦ Ethernet ♦ Multiple-access channel Abstract We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, $\textit{n}$ users generate messages for the channel according to a probability distribution. Raghavan and Upfal have given a protocol in which the expected $\textit{delay}$ (time to get serviced) of every message is O(log $\textit{n})$ when messages are generated according to a Bernoulli distribution with generation rate up to about 1/10. Our main results are the following protocols: (a) one in which the expected average message delay is O(1) when messages are generated according to a Bernoulli distribution with a generation rate smaller than $1/\textit{e},$ and (b) one in which the expected delay of any message is O(1) for an analogous model in which users are synchronized (i.e., they agree about the time), there are potentially an infinite number of users, and messages are generated according to a Poisson distribution with generation rate up to $1/\textit{e}.$ (Each message constitutes a new user.)To achieve (a), we first show how to simulate (b) using $\textit{n}$ synchronized users, and then show how to build the synchronization into the protocol. 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 2000-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 47 Issue Number 6 Page Count 49 Starting Page 1048 Ending Page 1096

#### Open content in new tab

Source: ACM Digital Library