Adversarial contention resolution for simple channels

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

Research output: Contribution to conferencePaperpeer-review

79 Scopus citations

Abstract

This paper analyzes the worst-case performance of randomized backoff on simple multiple-access channels. Most previous analysis of backoff has assumed a statistical arrival model. For batched arrivals, in which all n packets arrive at time 0, we show the following tight high-probability bounds. Randomized binary exponential backoff has makespan Θ(n lg n), and more generally, for any constant r, r-exponential backoff has makespan Θ(n loglgr n). Quadratic backoff has makespan Θ((n/lg n)3/2), and more generally, for r > 1, r-polynomial backoff has make-span Θ((n/ lg n)1+1/r). Thus, for batched inputs, both exponential and polynomial backoff are highly sensitive to backoff constants. We exhibit a monotone superpolynomial subexponential backoff algorithm, called loglog-iterated backoff, that achieves makespan Θ(n lg lg n/ lg lg lg n). We provide a matching lower bound showing that this strategy is optimal among all monotone backoff algorithms. Of independent interest is that this lower bound was proved with a delay sequence argument. In the adversarial-queuing model, we present the following stability and instability results for exponential backoff and log log-iterated backoff. Given a (λ, T)-stream, in which at most n = λT packets arrive in any interval of size T, exponential backoff is stable for arrival rates of λ = O(l/ lg n) and unstable for arrival rates of λ = Ω(lg lg n/lg n); loglog-iterated backoff is stable for arrival rates of λ = O(1/(lg lg n lg n)) and unstable for arrival rates of λ = Ω(1 / lg n). Our instability results show that bursty input is close to being worst-case for exponential backoff and variants and that even small bursts can create instabilities in the channel.

Original languageEnglish (US)
Pages325-332
Number of pages8
DOIs
StatePublished - Dec 1 2005
EventSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - Las Vegas, NV, United States
Duration: Jul 18 2005Jul 20 2005

Other

OtherSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures
CountryUnited States
CityLas Vegas, NV
Period7/18/057/20/05

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Keywords

  • Batch
  • Exponential Back-off
  • On-line
  • Polynomial Backoff
  • Worst-Case Backoff Performance

Fingerprint Dive into the research topics of 'Adversarial contention resolution for simple channels'. Together they form a unique fingerprint.

Cite this