The Library
Contention resolution with constant expected delay
Tools
Tools
Tools
Goldberg, Leslie Ann, MacKenzie, Phil, Paterson, Michael S. and Srinavasan, Aravind (1998) Contention resolution with constant expected delay. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-340.pdf - Other - Requires a PDF viewer. Download (536Kb) | Preview |
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 Upfal 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. We present a protocol 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/e. To achieve this result we first consider 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.) We give a protocol in which the expected delay of any message is O(1). Next we show how to simulate the protocol using n synchronized users. Finally, we show how to build the synchronization into the protocol.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | T Technology > TK Electrical engineering. Electronics Nuclear engineering | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Data transmission systems, Contention resolution protocols (Computer network protocols) | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | 25 March 1998 | ||||
| Dates: |
|
||||
| Number: | Number 340 | ||||
| Number of Pages: | 47 | ||||
| DOI: | CS-RR-340 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), European Strategic Programme of Research and Development in Information Technology (ESPRIT), United States. Department of Energy, National University of Singapore | ||||
| Grant number: | 21726 (ESPRIT), 20244 (ESPRIT), GR/L60982 (EPSRC), DE-AC04-76DP00789 (DOE) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
