Adversarial analyses of window backoff strategies for simple multiple-access channels

Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The analysis of window backoff strategies for simple multiple-access channels is studied. The online setting using an adversarial queueing model. It is observed that the the window, the packet makes an access attempt during a single randomly selected slot. A simple backoff/backon algorithm, having window sizes that vary nonmonotonically according to a sawtooth pattern, that achieves the optimal makespan of θ(n).

Original languageEnglish (US)
Title of host publicationProceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
Pages2839-2846
Number of pages8
StatePublished - 2004
EventProceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM) - Santa Fe, NM, United States
Duration: Apr 26 2004Apr 30 2004

Publication series

NameProceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
Volume18

Other

OtherProceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
CountryUnited States
CitySanta Fe, NM
Period4/26/044/30/04

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Cite this