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. In: 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, 20-22 Oct 1997. Published in: 38th Annual Symposium on Foundations of Computer Science, 1997. Proceedings. pp. 213-222. ISBN 0818681977. ISSN 0272-5428.
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.1109/SFCS.1997.646110
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 lambda o < 1. Previous protocols which are stable for constant arrival rates do not guarantee constant expected delay. The two protocols that achieved results closest to the's 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 nora-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 care the main contributions of the paper.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Series Name: | ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE | ||||
| Journal or Publication Title: | 38th Annual Symposium on Foundations of Computer Science, 1997. Proceedings. | ||||
| Publisher: | IEEE | ||||
| ISBN: | 0818681977 | ||||
| ISSN: | 0272-5428 | ||||
| Official Date: | 1997 | ||||
| Dates: |
|
||||
| Number of Pages: | 10 | ||||
| Page Range: | pp. 213-222 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 38th Annual Symposium on Foundations of Computer Science | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Miami Beach, FL | ||||
| Date(s) of Event: | 20-22 Oct 1997 |
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 |
