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

Computer Science

Rutgers - The State University of New Jersey, New Brunswick
Stony Brook University
Massachusetts Institute of Technology

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

1 Scopus citations

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
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	04/26/04 → 04/30/04

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

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{4a8b52b91dff44e289337f19b49f7e59,

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

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

}

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, 04/26/04.

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 › peer-review

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 - https://www.scopus.com/pages/publications/12444258768

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 -

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

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

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this