The Library
Contention resolution with guaranteed constant expected delay
Tools
Tools
Tools
Goldberg, Leslie Ann and MacKenzie, Phil (1997) Contention resolution with guaranteed 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-328.pdf - Other - Requires a PDF viewer. Download (2425Kb) | Preview |
Abstract
We study contention resolution in multiple-access channels such as the Ethernet. Under a stochastic model of continuous packet generation from a set of n processors, we construct a protocol which guarantees constant expected delay for generation rates up to a fixed constant which is less than 1. Previous protocols which are stable for constant arrival rates do not guarantee constant expected delay. The two protocols that achieved results closest to this are one by Raghavan and Upfal, which only guarantees logarithmic (in n) expected delay, and one by Paterson and Srinivasan, which only guarantees constant expected delay with high probability. (In the latter protocol, there is a non-zero probability that the initial clock synchronization might fail and cause the expected delay to grow unboundedly.) Although those protocols do not guarantee constant expected delay, we have used ideas from them in the construction of our protocol, which does guarantee constant expected delay. We achieve our results using a technique called Robust Synchronization which is applied periodically in our protocol. The introduction of this technique and the analysis of this technique are the major contributions of the paper.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Contention resolution protocols (Computer network protocols) | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | 21 July 1997 | ||||
| Dates: |
|
||||
| Number: | Number 328 | ||||
| Number of Pages: | 29 | ||||
| DOI: | CS-RR-328 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | L.A. Goldberg and P.D. MacKenzie, “Contention Resolution with Guaranteed Constant Expected Delay”, <i>Proceedings of the Symposium on Foundations of Computer Science 38</i>, pp. 213-222 (1997) | ||||
| Funder: | European Strategic Programme of Research and Development in Information Technology (ESPRIT), Engineering and Physical Sciences Research Council (EPSRC), United States. Department of Energy | ||||
| Grant number: | 21726 (ESPRIT), 20244 (ESPRIT), GR/L60982 (EPSRC), DBAC04-76DP00789 (DOE) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
