The Library
Contention resolution with bounded delay
Tools
Tools
Tools
Paterson, Michael S. and Srinivasan, Aravind (1995) Contention resolution with bounded delay. In: 36th Annual Symposium on Foundations of Computer Science (FOCS 95), Milwaukee, WI, 23-25 Oct 1995. Published in: 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings. pp. 104-113. ISBN 0818671831. 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.1995.492467
Abstract
When distributed processes contend for a shared resource, we need a good distributed contention resolution protocol, e.g., for multiple-access channels (ALOHA, Ethernet), PRAM emulation, and optical routing. Under a stochastic model of request generation from n synchronous processes, Raghavan & Upfal (1995) have shown a protocol which is stable for a positive request rate; their main result is that for every resource request, its expected delay (time to get serviced) is O(log n). Assuming that the initial clock times of the processes are within a known bound of each other, we present a stable protocol, wherein the expected delay for each request is O(1). We derive this by showing an analogous result for can infinite number of processes, assuming that all processes agree on the time.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Series Name: | ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE | ||||
| Journal or Publication Title: | 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings. | ||||
| Publisher: | IEEE | ||||
| ISBN: | 0818671831 | ||||
| ISSN: | 0272-5428 | ||||
| Official Date: | 1995 | ||||
| Dates: |
|
||||
| Number of Pages: | 2 | ||||
| Page Range: | pp. 104-113 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 36th Annual Symposium on Foundations of Computer Science (FOCS 95) | ||||
| Type of Event: | Other | ||||
| Location of Event: | Milwaukee, WI | ||||
| Date(s) of Event: | 23-25 Oct 1995 |
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 |
