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


    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)
    Number of pages8
    StatePublished - 2005
    EventSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - Las Vegas, NV, United States
    Duration: Jul 18 2005Jul 20 2005


    ConferenceSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures
    Country/TerritoryUnited States
    CityLas Vegas, NV


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

    ASJC Scopus subject areas

    • General Engineering


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

    Cite this