Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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)

[img]
Preview
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-340.pdf - Other - Requires a PDF viewer.

Download (536Kb) | Preview

Request Changes to record.

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 > 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:
DateEvent
25 March 1998Completion
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:
  • Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us