Contention resolution with guaranteed constant expected delay
UNSPECIFIED (1997) Contention resolution with guaranteed constant expected delay. In: 38th Annual Symposium on Foundations of Computer Science, MIAMI BEACH, FL, OCT 20-22, 1997. Published in: 38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS pp. 213-222.Full text not available from this repository.
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 (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Series Name:||ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE|
|Journal or Publication Title:||38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS|
|Publisher:||IEEE COMPUTER SOC|
|Number of Pages:||10|
|Page Range:||pp. 213-222|
|Title of Event:||38th Annual Symposium on Foundations of Computer Science|
|Location of Event:||MIAMI BEACH, FL|
|Date(s) of Event:||OCT 20-22, 1997|
Actions (login required)