Thumbnail
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

   Open content in new tab
Source: ACM Digital Library