Exponential Backoff: Channel and Retry Storm Simulator

Introduction

Imagine a room where many people want to speak, and there is no moderator. If two speak at once, nobody is understood, and they all have to try again. The question is what each person should do after a failed attempt, knowing only that they failed.

This is not an analogy invented for teaching. It is the real problem faced by ALOHAnet, the radio network built at the University of Hawaii and described by Norman Abramson in 1970, where terminals on several islands shared one radio channel with a central computer. If a terminal transmitted and heard no acknowledgement, it waited a random time and sent again.

In 1976, Robert Metcalfe and David Boggs brought the same idea onto a coaxial cable at Xerox PARC in the paper Ethernet: Distributed Packet Switching for Local Computer Networks (Communications of the ACM, July 1976). Their rule, and the version later standardized as IEEE 802.3, is called binary exponential backoff: after the $k$ -th collision of the same frame, pick a random number of slots in $\{0, 1, \dots, 2^{\min(k,10)}-1\}$ and wait that long. After 16 failed attempts, give up.

attempts = 0
while attempts < 16:
    send(frame)
    if success: return
    attempts += 1
    k = min(attempts, 10)
    wait( random_integer(0, 2^k - 1) * slot_time )
report_failure()

Two ingredients matter, and they solve different problems. Doubling makes the sender adapt to how crowded the channel is without anyone measuring it. Randomness keeps the senders who collided from colliding again in lockstep. The same two ingredients now sit in the retry logic of cloud SDKs, as described in Marc Brooker's 2015 post Exponential Backoff And Jitter on the AWS Architecture Blog. Related ideas appear in TCP congestion control and in the circuit breaker pattern.

Try It: Channel and Retry Storm

The demo has two modes.

Shared channel. Pick a protocol, the number of stations and the load, and press Run: each cell is one slot, green when exactly one station transmitted and red when two or more did. Sweep the load measures the throughput at twelve loads and draws it over the theoretical curves for ALOHA. Try the two backoff variants at load above 0.5: the version with no randomness collapses, because stations that collided choose the same wait and collide again.

Retry storm. A server is down for a few ticks while hundreds of clients fail. When it comes back, it can handle only a fixed number of requests per tick. Compare four retry policies. The server is identical in all four; only the clients' waiting rule changes.

<!-- Two modes - a shared channel and a retry storm -->
<div class="tabs">
  <button id="tabCh" type="button" class="tab on">Shared channel</button>
  <button id="tabSt" type="button" class="tab">Retry storm</button>
</div>

<div id="chPane">
  <div class="row">
    <label>Protocol
      <select id="proto">
        <option value="pure">Pure ALOHA (transmit whenever)</option>
        <option value="slotted">Slotted ALOHA (transmit at slot starts)</option>
        <option value="beb_plain">Backoff 2^k slots, no randomness</option>
        <option value="beb_jit" selected>Binary exponential backoff, random (Ethernet)</option>
      </select>
    </label>
  </div>
  <div class="row"><label>Stations: <b id="nv">20</b>
    <input type="range" id="n" min="2" max="50" value="20"></label></div>
  <div class="row"><label>New frames per frame time: <b id="gv">0.30</b>
    <input type="range" id="g" min="5" max="200" value="30"></label></div>
  <div id="strip" class="strip" aria-label="Last transmission slots"></div>
  <div class="legend">green = success, red = collision, gray = idle slot</div>
  <div class="stats" id="chStats"></div>
  <div class="btns">
    <button id="run" type="button">Run</button>
    <button id="sweep" type="button">Sweep the load</button>
    <button id="reset" type="button" class="ghost">Reset</button>
  </div>
  <canvas id="plot"></canvas>
  <p class="note" id="chNote"></p>
</div>

<div id="stPane" class="hide">
  <div class="row">
    <label>Retry policy
      <select id="policy">
        <option value="imm">Retry on the next tick</option>
        <option value="exp">Exponential backoff, no jitter</option>
        <option value="full" selected>Exponential backoff, full jitter</option>
        <option value="deco">Decorrelated jitter</option>
      </select>
    </label>
  </div>
  <div class="row"><label>Clients: <b id="mv">200</b>
    <input type="range" id="m" min="20" max="500" step="10" value="200"></label></div>
  <div class="row"><label>Server capacity (requests per tick): <b id="cv">20</b>
    <input type="range" id="cap" min="5" max="60" value="20"></label></div>
  <div class="row"><label>Server down for (ticks): <b id="dv">6</b>
    <input type="range" id="down" min="1" max="20" value="6"></label></div>
  <div class="btns">
    <button id="storm" type="button">Run the storm</button>
    <button id="compare" type="button" class="ghost">Compare all policies</button>
  </div>
  <canvas id="splot"></canvas>
  <div class="stats" id="stStats"></div>
  <p class="note" id="stNote"></p>
</div>

:root { --fg:#222; --bg:#fff; --mut:#555; --acc:#1d3557; --line:#cdd9e3; --ok:#2a9d5c; --bad:#e63946; --idle:#d5dae0; --c1:#2f6fd0; --c2:#e08a1e; --c3:#8a3ffc; }
@media (prefers-color-scheme: dark) {
  :root { --fg:#e6e9ee; --bg:#14181d; --mut:#aab3bf; --acc:#7fa6e6; --line:#39424d; --ok:#43c07c; --bad:#ff6b77; --idle:#3a424c; --c1:#6ea2ff; --c2:#ffb04a; --c3:#b890ff; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; font-size: 14px; }
.tabs { display: flex; gap: 6px; margin-bottom: 10px; }
.tab { flex: 1; background: transparent; color: var(--acc); border: 1px solid var(--acc); }
.tab.on { background: var(--acc); color: var(--bg); }
.hide { display: none; }
.row { margin: 6px 0; }
.row label { display: block; font-weight: 600; }
select { width: 100%; max-width: 100%; margin-top: 3px; padding: 5px; font: inherit; color: var(--fg); background: var(--bg); border: 1px solid var(--line); border-radius: 6px; }
input[type=range] { width: 100%; }
.strip { display: flex; gap: 2px; height: 22px; margin: 8px 0 2px; overflow: hidden; }
.c { flex: 1 1 0; min-width: 3px; border-radius: 2px; background: var(--idle); }
.c.ok { background: var(--ok); }
.c.col { background: var(--bad); }
.legend { font-size: 12px; color: var(--mut); margin-bottom: 6px; }
.stats { display: flex; flex-wrap: wrap; gap: 6px 14px; margin: 6px 0; font-size: 13px; }
.stats span b { font-variant-numeric: tabular-nums; }
.btns { display: flex; gap: 6px; flex-wrap: wrap; margin: 8px 0; }
button { font: 600 14px system-ui, sans-serif; padding: 7px 12px; border: 1px solid var(--acc); background: var(--acc); color: var(--bg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--acc); }
canvas { width: 100%; display: block; margin-top: 6px; }
.note { font-size: 13px; color: var(--mut); line-height: 1.45; margin: 6px 0; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const $ = (id) => document.getElementById(id);
const SUB = 16;
const css = (name) => getComputedStyle(document.documentElement).getPropertyValue(name).trim();

function rng(seed) {
  let s = seed >>> 0;
  return function () {
    s = (s + 0x6D2B79F5) >>> 0;
    let t = s;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function makeChan(proto, N, G, seed) {
  const rand = rng(seed);
  const ch = { proto, N, G, slots: 0, succ: 0, col: 0, idle: 0, drop: 0 };
  const count = (kind) => { ch.slots++; if (kind === 'ok') ch.succ++; else if (kind === 'col') ch.col++; else ch.idle++; return kind; };
  if (proto === 'pure') {
    let p2 = new Array(SUB).fill(0), p1 = new Array(SUB).fill(0);
    ch.step = function () {
      const cur = new Array(SUB).fill(0);
      for (let s = 0; s < SUB; s++) for (let i = 0; i < N; i++) if (rand() < G / (N * SUB)) cur[s]++;
      const arr = p2.concat(p1, cur);
      let ok = 0, tot = 0;
      for (let i = 0; i < SUB; i++) {
        const c = p1[i];
        if (!c) continue;
        tot += c;
        let sum = 0;
        for (let j = SUB + i - (SUB - 1); j <= SUB + i + (SUB - 1); j++) sum += arr[j];
        if (c === 1 && sum === 1) ok++;
      }
      p2 = p1; p1 = cur;
      const kind = tot === 0 ? 'idle' : ok > 0 ? 'ok' : 'col';
      if (kind === 'ok') { ch.succ += ok - 1; }
      return count(kind);
    };
  } else if (proto === 'slotted') {
    ch.step = function () {
      let a = 0;
      for (let i = 0; i < N; i++) if (rand() < G / N) a++;
      return count(a === 0 ? 'idle' : a === 1 ? 'ok' : 'col');
    };
  } else {
    const st = [];
    for (let i = 0; i < N; i++) st.push({ has: false, k: 0, w: 0 });
    const jit = proto === 'beb_jit';
    ch.step = function () {
      const att = [];
      for (const s of st) {
        if (!s.has && rand() < G / N) { s.has = true; s.k = 0; s.w = 0; }
        if (s.has) { if (s.w === 0) att.push(s); else s.w--; }
      }
      if (att.length === 1) { att[0].has = false; return count('ok'); }
      if (att.length === 0) return count('idle');
      for (const s of att) {
        s.k++;
        if (s.k >= 16) { s.has = false; ch.drop++; }
        else {
          const m = Math.min(s.k, 10);
          s.w = jit ? Math.floor(rand() * Math.pow(2, m)) : Math.pow(2, m) - 1;
        }
      }
      return count('col');
    };
  }
  return ch;
}

const NOTES = { pure: "Idealized model: every station starts a frame with probability G/N per 1/16 frame time, with no memory of past collisions. A frame survives only if nobody else starts within one frame time before or after, so S = G e^(-2G), peaking at 0.184.", slotted: "Idealized model: every station transmits in a slot with probability G/N. A slot succeeds when exactly one does, so S = G e^(-G), peaking at 0.368 when G = 1. Past that point, more load means less throughput.", beb_plain: "Each station that collides for the k-th time waits exactly 2^k - 1 slots. The colliding stations all choose the same wait, so they collide again, and again, until they give up after 16 attempts. Backoff without randomness does not separate anyone.", beb_jit: "Each station that collides for the k-th time waits a random number of slots from 0 to 2^min(k,10) - 1, and drops the frame after 16 attempts. The load on the x axis is new frames only, so this curve can be compared with ALOHA but is a different model." };
let chan = null, timer = null, cells = [], sweepPts = null;

function setup(canvas, h) {
  const w = Math.max(240, canvas.parentNode.clientWidth - 8);
  const dpr = window.devicePixelRatio || 1;
  canvas.style.height = Math.round(w * h) + 'px';
  canvas.width = Math.round(w * dpr);
  canvas.height = Math.round(w * h * dpr);
  const ctx = canvas.getContext('2d');
  ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
  ctx.font = '11px system-ui, sans-serif';
  return { ctx, W: w, H: w * h };
}

function axes(ctx, W, H, m, xmax, ymax, xl, yl) {
  ctx.strokeStyle = css('--line'); ctx.fillStyle = css('--mut'); ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(m.l, m.t); ctx.lineTo(m.l, H - m.b); ctx.lineTo(W - m.r, H - m.b); ctx.stroke();
  ctx.textAlign = 'center';
  for (let i = 0; i <= 4; i++) {
    const x = m.l + (W - m.l - m.r) * i / 4;
    ctx.fillText((xmax * i / 4).toFixed(xmax < 5 ? 1 : 0), x, H - m.b + 13);
  }
  ctx.textAlign = 'right';
  for (let i = 0; i <= 4; i++) {
    const y = H - m.b - (H - m.t - m.b) * i / 4;
    ctx.fillText((ymax * i / 4).toFixed(ymax < 2 ? 2 : 0), m.l - 4, y + 4);
  }
  ctx.textAlign = 'center';
  ctx.fillText(xl, m.l + (W - m.l - m.r) / 2, H - 4);
  ctx.save(); ctx.translate(10, m.t + (H - m.t - m.b) / 2); ctx.rotate(-Math.PI / 2); ctx.fillText(yl, 0, 0); ctx.restore();
}

function drawPlot() {
  const { ctx, W, H } = setup($('plot'), 0.62);
  const m = { l: 38, r: 8, t: 8, b: 30 }, XM = 2, YM = 0.5;
  ctx.clearRect(0, 0, W, H);
  axes(ctx, W, H, m, XM, YM, "Offered load G (frames per frame time)", "Throughput S");
  const X = (x) => m.l + (W - m.l - m.r) * x / XM, Y = (y) => H - m.b - (H - m.t - m.b) * y / YM;
  const curve = (f, col) => {
    ctx.strokeStyle = col; ctx.setLineDash([5, 4]); ctx.lineWidth = 1.5; ctx.beginPath();
    for (let i = 0; i <= 100; i++) { const g = XM * i / 100; i ? ctx.lineTo(X(g), Y(f(g))) : ctx.moveTo(X(g), Y(f(g))); }
    ctx.stroke(); ctx.setLineDash([]);
  };
  curve((g) => g * Math.exp(-g), css('--c1'));
  curve((g) => g * Math.exp(-2 * g), css('--c2'));
  if (sweepPts) {
    ctx.strokeStyle = css('--c3'); ctx.fillStyle = css('--c3'); ctx.lineWidth = 2; ctx.beginPath();
    sweepPts.forEach((p, i) => i ? ctx.lineTo(X(p[0]), Y(p[1])) : ctx.moveTo(X(p[0]), Y(p[1])));
    ctx.stroke();
    sweepPts.forEach((p) => { ctx.beginPath(); ctx.arc(X(p[0]), Y(p[1]), 3, 0, 7); ctx.fill(); });
  }
  ctx.textAlign = 'left';
  const lg = [[css('--c1'), "Slotted ALOHA theory"], [css('--c2'), "Pure ALOHA theory"], [css('--c3'), "Measured"]];
  lg.forEach((l, i) => { ctx.fillStyle = l[0]; ctx.fillRect(W - m.r - 150, m.t + 4 + i * 14, 10, 4); ctx.fillStyle = css('--fg'); ctx.fillText(l[1], W - m.r - 136, m.t + 9 + i * 14); });
}

function renderStrip() {
  $('strip').innerHTML = cells.map((k) => '<i class="c ' + k + '"></i>').join('');
}

function renderStats() {
  const c = chan;
  const n = Math.max(1, c.slots);
  const G = c.G;
  const th = c.proto === 'pure' ? G * Math.exp(-2 * G) : G * Math.exp(-G);
  const parts = [
    "Throughput: <b>" + (c.succ / n).toFixed(3) + "</b>",
    "Collisions: <b>" + (100 * c.col / n).toFixed(0) + "%</b>",
    "Idle: <b>" + (100 * c.idle / n).toFixed(0) + "%</b>"
  ];
  if (c.proto.indexOf('beb') === 0) parts.push("Frames dropped: <b>" + c.drop + "</b>");
  else parts.push("Theory at this load: <b>" + th.toFixed(3) + "</b>");
  $('chStats').innerHTML = parts.map((p) => '<span>' + p + '</span>').join('');
}

function newChan() {
  stop();
  chan = makeChan($('proto').value, +$('n').value, +$('g').value / 100, 1 + Math.floor(Math.random() * 1e9));
  cells = []; renderStrip(); renderStats();
  $('chNote').textContent = NOTES[$('proto').value];
  $('nv').textContent = $('n').value;
  $('gv').textContent = (+$('g').value / 100).toFixed(2);
}

function stop() { if (timer) { clearInterval(timer); timer = null; } $('run').textContent = "Run"; }

$('run').addEventListener('click', () => {
  if (timer) { stop(); return; }
  $('run').textContent = "Pause";
  timer = setInterval(() => {
    for (let i = 0; i < 2; i++) cells.push(chan.step());
    if (cells.length > 64) cells = cells.slice(cells.length - 64);
    renderStrip(); renderStats();
  }, 80);
});
$('reset').addEventListener('click', () => { sweepPts = null; newChan(); drawPlot(); });
['proto', 'n', 'g'].forEach((id) => $(id).addEventListener('input', () => { sweepPts = null; newChan(); drawPlot(); }));

$('sweep').addEventListener('click', () => {
  stop();
  const loads = [0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.8, 1.0, 1.2, 1.5, 2.0];
  sweepPts = loads.map((G) => {
    const c = makeChan($('proto').value, +$('n').value, G, 12345);
    for (let i = 0; i < 3000; i++) c.step();
    return [G, c.succ / c.slots];
  });
  drawPlot();
});

const SN = { imm: "Every failed client retries on the very next tick, so the server sees the whole crowd again and again. Most of its capacity is spent rejecting requests, and many clients exhaust their 10 attempts.", exp: "The delay doubles after each failure (up to 64 ticks), but every client uses the same delay, so they all come back at the same instants in huge synchronized waves.", full: "The delay is a random number from 1 to min(64, 2^k) ticks. The same average backoff, but the retries are spread out, and the server works near its capacity.", deco: "Each delay is random between 1 and three times the previous delay, capped at 64 ticks. It does not depend on a global attempt count, only on the client's own last wait." };
const CAPD = 64, MAXTRY = 10;

function runStorm(policy, M, cap, down, seed) {
  const r = rng(seed);
  const cl = [];
  for (let i = 0; i < M; i++) cl.push({ next: 0, k: 0, prev: 1, done: false });
  const load = [];
  let served = 0, gaveup = 0, total = 0, peak = 0, t = 0;
  while (t < 600 && served + gaveup < M) {
    const reqs = cl.filter((c) => !c.done && c.next === t);
    load.push(reqs.length); total += reqs.length; peak = Math.max(peak, reqs.length);
    for (let i = reqs.length - 1; i > 0; i--) { const j = Math.floor(r() * (i + 1)); const x = reqs[i]; reqs[i] = reqs[j]; reqs[j] = x; }
    let slot = 0;
    for (const c of reqs) {
      if (t >= down && slot < cap) { slot++; c.done = true; served++; continue; }
      c.k++;
      if (c.k >= MAXTRY) { c.done = true; gaveup++; continue; }
      const win = Math.min(CAPD, Math.pow(2, c.k));
      let d;
      if (policy === 'imm') d = 1;
      else if (policy === 'exp') d = win;
      else if (policy === 'full') d = 1 + Math.floor(r() * win);
      else { d = Math.min(CAPD, 1 + Math.floor(1 + r() * (c.prev * 3 - 1))); c.prev = d; }
      c.next = t + d;
    }
    t++;
  }
  return { load, served, gaveup, total, peak, ticks: t };
}

function drawStorm(res, cap, down) {
  const { ctx, W, H } = setup($('splot'), 0.55);
  const m = { l: 38, r: 8, t: 8, b: 30 };
  ctx.clearRect(0, 0, W, H);
  const T = Math.max(30, res.load.length);
  const YM = Math.max(res.peak, cap * 1.2);
  axes(ctx, W, H, m, T, YM, "Time (ticks)", "Requests per tick");
  const pw = W - m.l - m.r, ph = H - m.t - m.b;
  ctx.fillStyle = css('--idle'); ctx.fillRect(m.l, m.t, pw * Math.min(down, T) / T, ph);
  ctx.fillStyle = css('--c3');
  const bw = Math.max(1, pw / T - 1);
  res.load.forEach((v, i) => { const h = ph * v / YM; ctx.fillRect(m.l + pw * i / T, H - m.b - h, bw, h); });
  ctx.strokeStyle = css('--ok'); ctx.lineWidth = 2; ctx.setLineDash([6, 4]);
  const yc = H - m.b - ph * cap / YM;
  ctx.beginPath(); ctx.moveTo(m.l, yc); ctx.lineTo(W - m.r, yc); ctx.stroke(); ctx.setLineDash([]);
  ctx.textAlign = 'left'; ctx.fillStyle = css('--ok'); ctx.fillText("Server capacity", m.l + 4, yc - 4);
  ctx.fillStyle = css('--mut'); ctx.fillText("Server down", m.l + 4, m.t + 12);
}

function stormArgs() { return [+$('m').value, +$('cap').value, +$('down').value]; }

function doStorm() {
  const [M, cap, down] = stormArgs();
  $('mv').textContent = M; $('cv').textContent = cap; $('dv').textContent = down;
  const policy = $('policy').value;
  const res = runStorm(policy, M, cap, down, 777);
  drawStorm(res, cap, down);
  const parts = [
    "Ticks: <b>" + res.ticks + "</b>",
    "Peak requests per tick: <b>" + res.peak + "</b>",
    "Total requests sent: <b>" + res.total + "</b>",
    "Served: <b>" + res.served + "</b>",
    "Gave up after 10 failures: <b>" + res.gaveup + "</b>"
  ];
  $('stStats').innerHTML = parts.map((p) => '<span>' + p + '</span>').join('');
  $('stNote').textContent = SN[policy];
}
$('storm').addEventListener('click', doStorm);
['m', 'cap', 'down', 'policy'].forEach((id) => $(id).addEventListener('input', doStorm));

$('compare').addEventListener('click', () => {
  const [M, cap, down] = stormArgs();
  const names = { imm: "Retry on the next tick", exp: "Exponential backoff, no jitter", full: "Exponential backoff, full jitter", deco: "Decorrelated jitter" };
  const rows = ['imm', 'exp', 'full', 'deco'].map((p) => {
    const r = runStorm(p, M, cap, down, 777);
    return '<span><b>' + names[p] + '</b>: ' + fmt("%t% ticks, peak %p%, %w% requests, %g% gave up", { t: r.ticks, p: r.peak, w: r.total, g: r.gaveup }) + '</span>';
  });
  $('stStats').innerHTML = rows.join('<br>');
});

function switchTab(storm) {
  $('chPane').className = storm ? 'hide' : '';
  $('stPane').className = storm ? '' : 'hide';
  $('tabCh').className = 'tab' + (storm ? '' : ' on');
  $('tabSt').className = 'tab' + (storm ? ' on' : '');
  if (storm) { stop(); doStorm(); } else { drawPlot(); }
}
$('tabCh').addEventListener('click', () => switchTab(false));
$('tabSt').addEventListener('click', () => switchTab(true));
window.addEventListener('resize', () => { if ($('stPane').className === 'hide') drawPlot(); else doStorm(); });

newChan();
drawPlot();

<!-- Two modes - a shared channel and a retry storm -->
<div class="tabs">
  <button id="tabCh" type="button" class="tab on">Shared channel</button>
  <button id="tabSt" type="button" class="tab">Retry storm</button>
</div>

<div id="chPane">
  <div class="row">
    <label>Protocol
      <select id="proto">
        <option value="pure">Pure ALOHA (transmit whenever)</option>
        <option value="slotted">Slotted ALOHA (transmit at slot starts)</option>
        <option value="beb_plain">Backoff 2^k slots, no randomness</option>
        <option value="beb_jit" selected>Binary exponential backoff, random (Ethernet)</option>
      </select>
    </label>
  </div>
  <div class="row"><label>Stations: <b id="nv">20</b>
    <input type="range" id="n" min="2" max="50" value="20"></label></div>
  <div class="row"><label>New frames per frame time: <b id="gv">0.30</b>
    <input type="range" id="g" min="5" max="200" value="30"></label></div>
  <div id="strip" class="strip" aria-label="Last transmission slots"></div>
  <div class="legend">green = success, red = collision, gray = idle slot</div>
  <div class="stats" id="chStats"></div>
  <div class="btns">
    <button id="run" type="button">Run</button>
    <button id="sweep" type="button">Sweep the load</button>
    <button id="reset" type="button" class="ghost">Reset</button>
  </div>
  <canvas id="plot"></canvas>
  <p class="note" id="chNote"></p>
</div>

<div id="stPane" class="hide">
  <div class="row">
    <label>Retry policy
      <select id="policy">
        <option value="imm">Retry on the next tick</option>
        <option value="exp">Exponential backoff, no jitter</option>
        <option value="full" selected>Exponential backoff, full jitter</option>
        <option value="deco">Decorrelated jitter</option>
      </select>
    </label>
  </div>
  <div class="row"><label>Clients: <b id="mv">200</b>
    <input type="range" id="m" min="20" max="500" step="10" value="200"></label></div>
  <div class="row"><label>Server capacity (requests per tick): <b id="cv">20</b>
    <input type="range" id="cap" min="5" max="60" value="20"></label></div>
  <div class="row"><label>Server down for (ticks): <b id="dv">6</b>
    <input type="range" id="down" min="1" max="20" value="6"></label></div>
  <div class="btns">
    <button id="storm" type="button">Run the storm</button>
    <button id="compare" type="button" class="ghost">Compare all policies</button>
  </div>
  <canvas id="splot"></canvas>
  <div class="stats" id="stStats"></div>
  <p class="note" id="stNote"></p>
</div>

:root { --fg:#222; --bg:#fff; --mut:#555; --acc:#1d3557; --line:#cdd9e3; --ok:#2a9d5c; --bad:#e63946; --idle:#d5dae0; --c1:#2f6fd0; --c2:#e08a1e; --c3:#8a3ffc; }
@media (prefers-color-scheme: dark) {
  :root { --fg:#e6e9ee; --bg:#14181d; --mut:#aab3bf; --acc:#7fa6e6; --line:#39424d; --ok:#43c07c; --bad:#ff6b77; --idle:#3a424c; --c1:#6ea2ff; --c2:#ffb04a; --c3:#b890ff; }
}
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: var(--fg); background: var(--bg); margin: 0; padding: 4px; font-size: 14px; }
.tabs { display: flex; gap: 6px; margin-bottom: 10px; }
.tab { flex: 1; background: transparent; color: var(--acc); border: 1px solid var(--acc); }
.tab.on { background: var(--acc); color: var(--bg); }
.hide { display: none; }
.row { margin: 6px 0; }
.row label { display: block; font-weight: 600; }
select { width: 100%; max-width: 100%; margin-top: 3px; padding: 5px; font: inherit; color: var(--fg); background: var(--bg); border: 1px solid var(--line); border-radius: 6px; }
input[type=range] { width: 100%; }
.strip { display: flex; gap: 2px; height: 22px; margin: 8px 0 2px; overflow: hidden; }
.c { flex: 1 1 0; min-width: 3px; border-radius: 2px; background: var(--idle); }
.c.ok { background: var(--ok); }
.c.col { background: var(--bad); }
.legend { font-size: 12px; color: var(--mut); margin-bottom: 6px; }
.stats { display: flex; flex-wrap: wrap; gap: 6px 14px; margin: 6px 0; font-size: 13px; }
.stats span b { font-variant-numeric: tabular-nums; }
.btns { display: flex; gap: 6px; flex-wrap: wrap; margin: 8px 0; }
button { font: 600 14px system-ui, sans-serif; padding: 7px 12px; border: 1px solid var(--acc); background: var(--acc); color: var(--bg); border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--acc); }
canvas { width: 100%; display: block; margin-top: 6px; }
.note { font-size: 13px; color: var(--mut); line-height: 1.45; margin: 6px 0; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const $ = (id) => document.getElementById(id);
const SUB = 16;
const css = (name) => getComputedStyle(document.documentElement).getPropertyValue(name).trim();

function rng(seed) {
  let s = seed >>> 0;
  return function () {
    s = (s + 0x6D2B79F5) >>> 0;
    let t = s;
    t = Math.imul(t ^ (t >>> 15), t | 1);
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}

function makeChan(proto, N, G, seed) {
  const rand = rng(seed);
  const ch = { proto, N, G, slots: 0, succ: 0, col: 0, idle: 0, drop: 0 };
  const count = (kind) => { ch.slots++; if (kind === 'ok') ch.succ++; else if (kind === 'col') ch.col++; else ch.idle++; return kind; };
  if (proto === 'pure') {
    let p2 = new Array(SUB).fill(0), p1 = new Array(SUB).fill(0);
    ch.step = function () {
      const cur = new Array(SUB).fill(0);
      for (let s = 0; s < SUB; s++) for (let i = 0; i < N; i++) if (rand() < G / (N * SUB)) cur[s]++;
      const arr = p2.concat(p1, cur);
      let ok = 0, tot = 0;
      for (let i = 0; i < SUB; i++) {
        const c = p1[i];
        if (!c) continue;
        tot += c;
        let sum = 0;
        for (let j = SUB + i - (SUB - 1); j <= SUB + i + (SUB - 1); j++) sum += arr[j];
        if (c === 1 && sum === 1) ok++;
      }
      p2 = p1; p1 = cur;
      const kind = tot === 0 ? 'idle' : ok > 0 ? 'ok' : 'col';
      if (kind === 'ok') { ch.succ += ok - 1; }
      return count(kind);
    };
  } else if (proto === 'slotted') {
    ch.step = function () {
      let a = 0;
      for (let i = 0; i < N; i++) if (rand() < G / N) a++;
      return count(a === 0 ? 'idle' : a === 1 ? 'ok' : 'col');
    };
  } else {
    const st = [];
    for (let i = 0; i < N; i++) st.push({ has: false, k: 0, w: 0 });
    const jit = proto === 'beb_jit';
    ch.step = function () {
      const att = [];
      for (const s of st) {
        if (!s.has && rand() < G / N) { s.has = true; s.k = 0; s.w = 0; }
        if (s.has) { if (s.w === 0) att.push(s); else s.w--; }
      }
      if (att.length === 1) { att[0].has = false; return count('ok'); }
      if (att.length === 0) return count('idle');
      for (const s of att) {
        s.k++;
        if (s.k >= 16) { s.has = false; ch.drop++; }
        else {
          const m = Math.min(s.k, 10);
          s.w = jit ? Math.floor(rand() * Math.pow(2, m)) : Math.pow(2, m) - 1;
        }
      }
      return count('col');
    };
  }
  return ch;
}

const NOTES = { pure: "Idealized model: every station starts a frame with probability G/N per 1/16 frame time, with no memory of past collisions. A frame survives only if nobody else starts within one frame time before or after, so S = G e^(-2G), peaking at 0.184.", slotted: "Idealized model: every station transmits in a slot with probability G/N. A slot succeeds when exactly one does, so S = G e^(-G), peaking at 0.368 when G = 1. Past that point, more load means less throughput.", beb_plain: "Each station that collides for the k-th time waits exactly 2^k - 1 slots. The colliding stations all choose the same wait, so they collide again, and again, until they give up after 16 attempts. Backoff without randomness does not separate anyone.", beb_jit: "Each station that collides for the k-th time waits a random number of slots from 0 to 2^min(k,10) - 1, and drops the frame after 16 attempts. The load on the x axis is new frames only, so this curve can be compared with ALOHA but is a different model." };
let chan = null, timer = null, cells = [], sweepPts = null;

function setup(canvas, h) {
  const w = Math.max(240, canvas.parentNode.clientWidth - 8);
  const dpr = window.devicePixelRatio || 1;
  canvas.style.height = Math.round(w * h) + 'px';
  canvas.width = Math.round(w * dpr);
  canvas.height = Math.round(w * h * dpr);
  const ctx = canvas.getContext('2d');
  ctx.setTransform(dpr, 0, 0, dpr, 0, 0);
  ctx.font = '11px system-ui, sans-serif';
  return { ctx, W: w, H: w * h };
}

function axes(ctx, W, H, m, xmax, ymax, xl, yl) {
  ctx.strokeStyle = css('--line'); ctx.fillStyle = css('--mut'); ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(m.l, m.t); ctx.lineTo(m.l, H - m.b); ctx.lineTo(W - m.r, H - m.b); ctx.stroke();
  ctx.textAlign = 'center';
  for (let i = 0; i <= 4; i++) {
    const x = m.l + (W - m.l - m.r) * i / 4;
    ctx.fillText((xmax * i / 4).toFixed(xmax < 5 ? 1 : 0), x, H - m.b + 13);
  }
  ctx.textAlign = 'right';
  for (let i = 0; i <= 4; i++) {
    const y = H - m.b - (H - m.t - m.b) * i / 4;
    ctx.fillText((ymax * i / 4).toFixed(ymax < 2 ? 2 : 0), m.l - 4, y + 4);
  }
  ctx.textAlign = 'center';
  ctx.fillText(xl, m.l + (W - m.l - m.r) / 2, H - 4);
  ctx.save(); ctx.translate(10, m.t + (H - m.t - m.b) / 2); ctx.rotate(-Math.PI / 2); ctx.fillText(yl, 0, 0); ctx.restore();
}

function drawPlot() {
  const { ctx, W, H } = setup($('plot'), 0.62);
  const m = { l: 38, r: 8, t: 8, b: 30 }, XM = 2, YM = 0.5;
  ctx.clearRect(0, 0, W, H);
  axes(ctx, W, H, m, XM, YM, "Offered load G (frames per frame time)", "Throughput S");
  const X = (x) => m.l + (W - m.l - m.r) * x / XM, Y = (y) => H - m.b - (H - m.t - m.b) * y / YM;
  const curve = (f, col) => {
    ctx.strokeStyle = col; ctx.setLineDash([5, 4]); ctx.lineWidth = 1.5; ctx.beginPath();
    for (let i = 0; i <= 100; i++) { const g = XM * i / 100; i ? ctx.lineTo(X(g), Y(f(g))) : ctx.moveTo(X(g), Y(f(g))); }
    ctx.stroke(); ctx.setLineDash([]);
  };
  curve((g) => g * Math.exp(-g), css('--c1'));
  curve((g) => g * Math.exp(-2 * g), css('--c2'));
  if (sweepPts) {
    ctx.strokeStyle = css('--c3'); ctx.fillStyle = css('--c3'); ctx.lineWidth = 2; ctx.beginPath();
    sweepPts.forEach((p, i) => i ? ctx.lineTo(X(p[0]), Y(p[1])) : ctx.moveTo(X(p[0]), Y(p[1])));
    ctx.stroke();
    sweepPts.forEach((p) => { ctx.beginPath(); ctx.arc(X(p[0]), Y(p[1]), 3, 0, 7); ctx.fill(); });
  }
  ctx.textAlign = 'left';
  const lg = [[css('--c1'), "Slotted ALOHA theory"], [css('--c2'), "Pure ALOHA theory"], [css('--c3'), "Measured"]];
  lg.forEach((l, i) => { ctx.fillStyle = l[0]; ctx.fillRect(W - m.r - 150, m.t + 4 + i * 14, 10, 4); ctx.fillStyle = css('--fg'); ctx.fillText(l[1], W - m.r - 136, m.t + 9 + i * 14); });
}

function renderStrip() {
  $('strip').innerHTML = cells.map((k) => '<i class="c ' + k + '"></i>').join('');
}

function renderStats() {
  const c = chan;
  const n = Math.max(1, c.slots);
  const G = c.G;
  const th = c.proto === 'pure' ? G * Math.exp(-2 * G) : G * Math.exp(-G);
  const parts = [
    "Throughput: <b>" + (c.succ / n).toFixed(3) + "</b>",
    "Collisions: <b>" + (100 * c.col / n).toFixed(0) + "%</b>",
    "Idle: <b>" + (100 * c.idle / n).toFixed(0) + "%</b>"
  ];
  if (c.proto.indexOf('beb') === 0) parts.push("Frames dropped: <b>" + c.drop + "</b>");
  else parts.push("Theory at this load: <b>" + th.toFixed(3) + "</b>");
  $('chStats').innerHTML = parts.map((p) => '<span>' + p + '</span>').join('');
}

function newChan() {
  stop();
  chan = makeChan($('proto').value, +$('n').value, +$('g').value / 100, 1 + Math.floor(Math.random() * 1e9));
  cells = []; renderStrip(); renderStats();
  $('chNote').textContent = NOTES[$('proto').value];
  $('nv').textContent = $('n').value;
  $('gv').textContent = (+$('g').value / 100).toFixed(2);
}

function stop() { if (timer) { clearInterval(timer); timer = null; } $('run').textContent = "Run"; }

$('run').addEventListener('click', () => {
  if (timer) { stop(); return; }
  $('run').textContent = "Pause";
  timer = setInterval(() => {
    for (let i = 0; i < 2; i++) cells.push(chan.step());
    if (cells.length > 64) cells = cells.slice(cells.length - 64);
    renderStrip(); renderStats();
  }, 80);
});
$('reset').addEventListener('click', () => { sweepPts = null; newChan(); drawPlot(); });
['proto', 'n', 'g'].forEach((id) => $(id).addEventListener('input', () => { sweepPts = null; newChan(); drawPlot(); }));

$('sweep').addEventListener('click', () => {
  stop();
  const loads = [0.05, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.8, 1.0, 1.2, 1.5, 2.0];
  sweepPts = loads.map((G) => {
    const c = makeChan($('proto').value, +$('n').value, G, 12345);
    for (let i = 0; i < 3000; i++) c.step();
    return [G, c.succ / c.slots];
  });
  drawPlot();
});

const SN = { imm: "Every failed client retries on the very next tick, so the server sees the whole crowd again and again. Most of its capacity is spent rejecting requests, and many clients exhaust their 10 attempts.", exp: "The delay doubles after each failure (up to 64 ticks), but every client uses the same delay, so they all come back at the same instants in huge synchronized waves.", full: "The delay is a random number from 1 to min(64, 2^k) ticks. The same average backoff, but the retries are spread out, and the server works near its capacity.", deco: "Each delay is random between 1 and three times the previous delay, capped at 64 ticks. It does not depend on a global attempt count, only on the client's own last wait." };
const CAPD = 64, MAXTRY = 10;

function runStorm(policy, M, cap, down, seed) {
  const r = rng(seed);
  const cl = [];
  for (let i = 0; i < M; i++) cl.push({ next: 0, k: 0, prev: 1, done: false });
  const load = [];
  let served = 0, gaveup = 0, total = 0, peak = 0, t = 0;
  while (t < 600 && served + gaveup < M) {
    const reqs = cl.filter((c) => !c.done && c.next === t);
    load.push(reqs.length); total += reqs.length; peak = Math.max(peak, reqs.length);
    for (let i = reqs.length - 1; i > 0; i--) { const j = Math.floor(r() * (i + 1)); const x = reqs[i]; reqs[i] = reqs[j]; reqs[j] = x; }
    let slot = 0;
    for (const c of reqs) {
      if (t >= down && slot < cap) { slot++; c.done = true; served++; continue; }
      c.k++;
      if (c.k >= MAXTRY) { c.done = true; gaveup++; continue; }
      const win = Math.min(CAPD, Math.pow(2, c.k));
      let d;
      if (policy === 'imm') d = 1;
      else if (policy === 'exp') d = win;
      else if (policy === 'full') d = 1 + Math.floor(r() * win);
      else { d = Math.min(CAPD, 1 + Math.floor(1 + r() * (c.prev * 3 - 1))); c.prev = d; }
      c.next = t + d;
    }
    t++;
  }
  return { load, served, gaveup, total, peak, ticks: t };
}

function drawStorm(res, cap, down) {
  const { ctx, W, H } = setup($('splot'), 0.55);
  const m = { l: 38, r: 8, t: 8, b: 30 };
  ctx.clearRect(0, 0, W, H);
  const T = Math.max(30, res.load.length);
  const YM = Math.max(res.peak, cap * 1.2);
  axes(ctx, W, H, m, T, YM, "Time (ticks)", "Requests per tick");
  const pw = W - m.l - m.r, ph = H - m.t - m.b;
  ctx.fillStyle = css('--idle'); ctx.fillRect(m.l, m.t, pw * Math.min(down, T) / T, ph);
  ctx.fillStyle = css('--c3');
  const bw = Math.max(1, pw / T - 1);
  res.load.forEach((v, i) => { const h = ph * v / YM; ctx.fillRect(m.l + pw * i / T, H - m.b - h, bw, h); });
  ctx.strokeStyle = css('--ok'); ctx.lineWidth = 2; ctx.setLineDash([6, 4]);
  const yc = H - m.b - ph * cap / YM;
  ctx.beginPath(); ctx.moveTo(m.l, yc); ctx.lineTo(W - m.r, yc); ctx.stroke(); ctx.setLineDash([]);
  ctx.textAlign = 'left'; ctx.fillStyle = css('--ok'); ctx.fillText("Server capacity", m.l + 4, yc - 4);
  ctx.fillStyle = css('--mut'); ctx.fillText("Server down", m.l + 4, m.t + 12);
}

function stormArgs() { return [+$('m').value, +$('cap').value, +$('down').value]; }

function doStorm() {
  const [M, cap, down] = stormArgs();
  $('mv').textContent = M; $('cv').textContent = cap; $('dv').textContent = down;
  const policy = $('policy').value;
  const res = runStorm(policy, M, cap, down, 777);
  drawStorm(res, cap, down);
  const parts = [
    "Ticks: <b>" + res.ticks + "</b>",
    "Peak requests per tick: <b>" + res.peak + "</b>",
    "Total requests sent: <b>" + res.total + "</b>",
    "Served: <b>" + res.served + "</b>",
    "Gave up after 10 failures: <b>" + res.gaveup + "</b>"
  ];
  $('stStats').innerHTML = parts.map((p) => '<span>' + p + '</span>').join('');
  $('stNote').textContent = SN[policy];
}
$('storm').addEventListener('click', doStorm);
['m', 'cap', 'down', 'policy'].forEach((id) => $(id).addEventListener('input', doStorm));

$('compare').addEventListener('click', () => {
  const [M, cap, down] = stormArgs();
  const names = { imm: "Retry on the next tick", exp: "Exponential backoff, no jitter", full: "Exponential backoff, full jitter", deco: "Decorrelated jitter" };
  const rows = ['imm', 'exp', 'full', 'deco'].map((p) => {
    const r = runStorm(p, M, cap, down, 777);
    return '<span><b>' + names[p] + '</b>: ' + fmt("%t% ticks, peak %p%, %w% requests, %g% gave up", { t: r.ticks, p: r.peak, w: r.total, g: r.gaveup }) + '</span>';
  });
  $('stStats').innerHTML = rows.join('<br>');
});

function switchTab(storm) {
  $('chPane').className = storm ? 'hide' : '';
  $('stPane').className = storm ? '' : 'hide';
  $('tabCh').className = 'tab' + (storm ? '' : ' on');
  $('tabSt').className = 'tab' + (storm ? ' on' : '');
  if (storm) { stop(); doStorm(); } else { drawPlot(); }
}
$('tabCh').addEventListener('click', () => switchTab(false));
$('tabSt').addEventListener('click', () => switchTab(true));
window.addEventListener('resize', () => { if ($('stPane').className === 'hide') drawPlot(); else doStorm(); });

newChan();
drawPlot();

Result

Console

Two warnings about what you are seeing. The ALOHA curves use the idealized textbook model (every station transmits with a fixed probability and ignores history), which is what the formulas describe. The backoff curve uses stations that remember their collisions. They answer different questions, so the point is where they bend, not that they coincide.

The Real Complexity

Slotted ALOHA. Time is cut into frame-sized slots and each of the $N$ stations transmits with probability $G/N$ per slot. A slot succeeds exactly when one station transmits, so for large $N$ the throughput per slot is

S = G\,e^{-G}.

Setting $dS/dG = (1-G)e^{-G} = 0$ gives $G = 1$ and a maximum of $S = 1/e \approx 0.368$ . Past that point additional load reduces throughput. The 1/e figure is attributed to Lawrence Roberts, who proposed slotting ALOHA.

Pure ALOHA. With no slots, a frame is hit by any other frame that starts within one frame time before or after it, a vulnerable window of length $2$ . Hence

S = G\,e^{-2G},

with maximum at $G = 1/2$ : $S = 1/(2e) \approx 0.184$ . Synchronizing the senders exactly doubles the usable capacity.

Binary exponential backoff. After the $k$ -th collision the wait is uniform on $\{0,\dots,2^{\min(k,10)}-1\}$ slots, so the expected wait is $(2^{\min(k,10)}-1)/2$ slots, and the window stops growing at $1024$ slots. If $n$ stations contend, the window needs about $\log_2 n$ doublings before a collision becomes unlikely, so the number of attempts per frame grows like $O(\log n)$ for a burst of $n$ stations. Each station needs only $O(1)$ memory (its attempt counter) and no communication.

Stability is the delicate part. The 1987 paper by Johan Håstad, Tom Leighton and Brian Rogoff, Analysis of backoff protocols for multiple access channels (STOC 1987; journal version in SIAM Journal on Computing, 1996), is the standard reference. It shows that with a finite number of stations and Poisson-style arrivals, binary exponential backoff becomes unstable once the total arrival rate exceeds roughly $0.567$ frames per slot, while polynomial backoff (waits growing like a power of the attempt number, above linear) is stable for every arrival rate below $1$ . Practical Ethernet avoids the problem mostly by being lightly loaded and by truncating the window at 1024 slots.

Retry storms. Suppose $m$ clients fail together and the server can serve $c$ requests per tick. If everyone retries on the next tick, request counts go $m, m-c, m-2c, \dots$ so the server sees about $m^2/(2c)$ requests in total to serve $m$ of them. If instead each retry is spread uniformly over a window of $W$ ticks, the load is about $m/W$ per tick, which is below capacity once $W \ge m/c$ , reached after about $\log_2(m/c)$ doublings. Exponential growth finds the right scale by itself. The time to drain cannot beat $m/c$ ticks, whatever the policy.

Jitter variants (Brooker, 2015). With base delay $b$ , cap $C$ and attempt number $k$ , let $t = \min(C, b\cdot 2^k)$ :

Full jitter: sleep $\sim U(0, t)$ .
Equal jitter: sleep $= t/2 + U(0, t/2)$ .
Decorrelated jitter: sleep $\sim U(b, 3\cdot\text{previous sleep})$ , capped at $C$ .

In his simulations, jittered variants completed with far fewer calls than plain exponential backoff under contention, with full jitter the simplest of them.

Where It Matters

Ethernet (CSMA/CD). Stations listen before sending and abort when they detect a collision, then use binary exponential backoff. Modern switched, full-duplex Ethernet has no shared medium, so it no longer needs it, but the rule is still in the IEEE 802.3 standard for half-duplex links.
Wi-Fi (CSMA/CA). A radio cannot listen while it transmits, so Wi-Fi tries to avoid collisions: each station draws a random backoff counter from a contention window that doubles after each failed (unacknowledged) transmission, up to a maximum. Typical OFDM-era parameters are a window from 15 up to 1023 slots.
Cloud APIs and microservices. Throttled or failing services are retried with capped exponential backoff and jitter, which is why the AWS SDKs and many other clients ship it by default. Pair it with a circuit breaker and rate limiting so that a struggling dependency is protected instead of hammered.
Transport protocols. TCP doubles its retransmission timeout after each timeout, the same doubling rule applied to a single connection.
Locks and queues. Optimistic concurrency, lock acquisition and polling loops all use randomized, growing waits to avoid the thundering herd.

The mathematical backbone is the theory of randomized algorithms and Markov chains: stability of a backoff protocol is the question of whether a certain chain returns to empty.

Conclusion

Exponential backoff is a small piece of code that solves a hard coordination problem: many parties, one resource, no referee and no communication. Doubling the wait lets the crowd find its own size. Randomizing the wait stops the crowd from moving as a single herd.

The numbers keep it honest. Uncoordinated senders waste most of the channel (at best $1/e$ with slots, $1/(2e)$ without), and plain binary exponential backoff can become unstable at high load. The next time your client library says "retrying with jitter", you know what the jitter is for: not to be polite, but to be different from everyone else who just failed.

Comments

Loading comments...

https://www.kipuhub.com/en/article/exponential-backoff/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Exponential Backoff

How networks share a channel