Contended compare-and-swap: n²T/2 and the value of jitter

Simulate a modelNeeds Python

Problem

Writers that commit by a conditional write on one shared pointer (a table format's metadata pointer, an optimistic lock) serialize: each round, one wins and the rest retry. With n writers and immediate retry, draining them takes n rounds, but the failed attempts add up to n(n − 1)/2, each a real round trip and possibly real files written. Jittered backoff spreads the retries out, cutting wasted attempts at the price of some idle rounds.

Simulate n writers that each need one successful conditional write on one shared pointer. A round takes T = 50 ms; in each round exactly one of the writers that try wins. Compare immediate retry with jittered exponential backoff for n from 2 to 40, and compare wasted attempts with n(n−1)/2.

The question. How long does it take to drain n writers, and how many attempts are wasted, with and without backoff?

Predict

With immediate retry, how many attempts do 40 contending writers waste?

About 40HundredsThousands

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

contended-compare-and-swap-n-t.py43 linesDownload

View the code

contended-compare-and-swap-n-t.py

# /// script
# requires-python = ">=3.10"
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Contended compare-and-swap: n²T/2.

n writers each need one successful conditional write on a shared pointer; a
round takes T = 50 ms and exactly one of the writers trying in a round wins.
Total time and wasted attempts with immediate retry and with jittered
exponential backoff, against n(n − 1)/2 and n²T/2.
"""
import argparse, json, random

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--ns", default="2,5,10,20,40", help="Writer counts.")
p.add_argument("--t", type=float, default=0.05, help="Round time T (s).")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()

def drain(n, backoff=None, seed=1):
    rng = random.Random(seed); waiting = list(range(n)); wasted = rounds = 0
    next_try = {w: 0 for w in waiting}; fails = {w: 0 for w in waiting}
    while waiting:
        trying = [w for w in waiting if next_try[w] <= rounds]
        if trying:
            winner = rng.choice(trying); waiting.remove(winner)
            for w in trying:
                if w != winner:
                    wasted += 1; fails[w] += 1
                    next_try[w] = rounds + 1 + (rng.randint(0, 2 ** min(fails[w], 6)) if backoff == "jitter" else 0)
        rounds += 1
    return rounds * args.t, wasted
rows = []
for n in map(int, args.ns.split(",")):
    t0, w0 = drain(n); t1, w1 = drain(n, "jitter")
    rows.append({"n": n, "no_backoff_s": t0, "no_backoff_wasted": w0, "jitter_s": t1, "jitter_wasted": w1, "pairs": n * (n - 1) / 2, "formula_s": n * n * args.t / 2})
for r in rows: print(f"n = {r['n']:>2}: no backoff {r['no_backoff_s']:5.2f} s, {r['no_backoff_wasted']:>4} wasted   jitter {r['jitter_s']:5.2f} s, {r['jitter_wasted']:>4} wasted   n(n-1)/2 = {r['pairs']:.0f}, n²T/2 = {r['formula_s']:.2f} s")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"writers": rows}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.
Terminal
```
uv run contended-compare-and-swap-n-t.py
uv run contended-compare-and-swap-n-t.py --help     # every knob
```

Knobs
Knob · default	What it changes
--ns2, 5, 10, 20, 40	Writer counts.
--t0.05	Round time T (s).

Our run

Wasted attempts against writersApple M2 · 8 cores · 8 GB

Immediate retryJittered backoffn(n − 1)/2

Data table

Wasted attempts against writers
Writers n	Immediate retry	Jittered backoff	n(n − 1)/2
2	1	1	1
5	10	5	10
10	45	21	45
20	190	55	190
40	780	149	780

macOS 26.6.2 · Python 3.13.3 · run 2026-10-20

Draining n writers

Draining n writers
n	Immediate: time	Immediate: wasted	Jitter: time	Jitter: wasted
2	100 ms	1	200 ms	1
5	250 ms	10	300 ms	5
10	500 ms	45	900 ms	21
20	1 s	190	2.1 s	55
40	2 s	780	4.35 s	149

Output · uv run contended-compare-and-swap-n-t.py

n =  2: no backoff  0.10 s,    1 wasted   jitter  0.20 s,    1 wasted   n(n-1)/2 = 1, n²T/2 = 0.10 s
n =  5: no backoff  0.25 s,   10 wasted   jitter  0.30 s,    5 wasted   n(n-1)/2 = 10, n²T/2 = 0.62 s
n = 10: no backoff  0.50 s,   45 wasted   jitter  0.90 s,   21 wasted   n(n-1)/2 = 45, n²T/2 = 2.50 s
n = 20: no backoff  1.00 s,  190 wasted   jitter  2.10 s,   55 wasted   n(n-1)/2 = 190, n²T/2 = 10.00 s
n = 40: no backoff  2.00 s,  780 wasted   jitter  4.35 s,  149 wasted   n(n-1)/2 = 780, n²T/2 = 40.00 s

What we found

With immediate retry, 40 writers drained in 2 s (n × T) and wasted 780 attempts, exactly n(n − 1)/2. With jittered backoff they took 4.35 s and wasted 149.

Read it

The n²T/2 in the chapter counts coordination work, not the wall-clock time of one writer: the queue drains in linear time, but the work thrown away grows quadratically. Backoff spends a little latency to save most of that work, which matters when each attempt writes data (a lakehouse commit writes its files before it tries the pointer).