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

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 proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
Pages	2839-2846
Number of pages	8
State	Published - 2004
Event	Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM) - Santa Fe, NM, United States Duration: Apr 26 2004 → Apr 30 2004

Publication series

Name	Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
Volume	18

Conference

Conference	Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)
Country/Territory	United States
City	Santa Fe, NM
Period	4/26/04 → 4/30/04

ASJC Scopus subject areas

General Engineering

Cite this

Bender, M. A., Farach-Colton, M., He, S., Kuszmaul, B. C., & Leiserson, C. E. (2004). Adversarial analyses of window backoff strategies for simple multiple-access channels. In Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM) (pp. 2839-2846). (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM); Vol. 18).

Adversarial analyses of window backoff strategies for simple multiple-access channels. / Bender, Michael A.; Farach-Colton, Martin; He, Simai et al.
Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM). 2004. p. 2839-2846 (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM); Vol. 18).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bender, MA, Farach-Colton, M, He, S, Kuszmaul, BC & Leiserson, CE 2004, Adversarial analyses of window backoff strategies for simple multiple-access channels. in Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM). Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM), vol. 18, pp. 2839-2846, Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM), Santa Fe, NM, United States, 4/26/04.

Bender MA, Farach-Colton M, He S, Kuszmaul BC, Leiserson CE. Adversarial analyses of window backoff strategies for simple multiple-access channels. In Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM). 2004. p. 2839-2846. (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)).

Bender, Michael A. ; Farach-Colton, Martin ; He, Simai et al. / Adversarial analyses of window backoff strategies for simple multiple-access channels. Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM). 2004. pp. 2839-2846 (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)).

@inproceedings{ea0278f7ad2a4849982fe07022857983,

title = "Adversarial analyses of window backoff strategies for simple multiple-access channels",

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).",

author = "Bender, {Michael A.} and Martin Farach-Colton and Simai He and Kuszmaul, {Bradley C.} and Leiserson, {Charles E.}",

year = "2004",

language = "English (US)",

isbn = "0769521320",

series = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)",

pages = "2839--2846",

booktitle = "Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)",

note = "Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM) ; Conference date: 26-04-2004 Through 30-04-2004",

}

TY - GEN

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

AU - Bender, Michael A.

AU - Farach-Colton, Martin

AU - He, Simai

AU - Kuszmaul, Bradley C.

AU - Leiserson, Charles E.

PY - 2004

Y1 - 2004

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=12444258768&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=12444258768&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:12444258768

SN - 0769521320

SN - 9780769521329

T3 - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)

SP - 2839

EP - 2846

BT - Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)

T2 - Proceedings - 18th International Parallel and Distributed Processing Symposium, IPDPS 2004 (Abstracts and CD-ROM)

Y2 - 26 April 2004 through 30 April 2004

ER -

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

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this