The Library
Contention resolution with constant expected delay
Tools
Tools
Tools
Goldberg, Leslie Ann, MacKenzie, Phil, Paterson, Michael S. and Srinivasan, Aravind (2000) Contention resolution with constant expected delay. Journal of the ACM, Volume 47 (Number 6). pp. 1048-1096. ISSN 0004-5411.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1145/355541.355567
Abstract
We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider, n users generate messages for the channel according to a probability distribution. Raghavan and Upfai have given a protocol in which the expected delay (time to get serviced) of every message is O(log 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 lie, 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/e. (Each message constitutes a new user.)
To achieve (a), we first show how to simulate (b) using n synchronized users, and then show how to build the synchronization into the protocol.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Alternative Title: | |||||
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Journal or Publication Title: | Journal of the ACM | ||||
| Publisher: | Association for Computing Machinery, Inc. | ||||
| ISSN: | 0004-5411 | ||||
| Official Date: | November 2000 | ||||
| Dates: |
|
||||
| Volume: | Volume 47 | ||||
| Number: | Number 6 | ||||
| Number of Pages: | 49 | ||||
| Page Range: | pp. 1048-1096 | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
