Adversarial analyses of window backoff strategies for simple multiple-access channels
Michael A. Bender, Martı́n Farach-Colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson · 2004
Summary form only given. Backoff strategies have typically been analyzed by making statistical assumptions on the distribution of problem inputs. Although these analyses have provided valuable insights into the efficacy of various backoff strategies, they leave open the question as to which backoff algorithms perform best in the worst case or on inputs, such as bursty inputs, that are not covered by the statistical models. We analyze randomized backoff strategies using worst-case assumptions on the inputs.