THE FOLD / CO-OP / SHARED-MEMORY / THE POWER OF TWO CHOICES
THE POWER OF TWO CHOICES
two throws beat one
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The power of two choices is a startling result in randomized load balancing. Throw n balls into n bins at random and the fullest bin holds about log n / log log n balls. But give each ball two random bins and let it pick the emptier one, and the fullest bin drops to about log log n / log 2 — an exponential improvement, from logarithmic to double-logarithmic, for the cost of one extra look. A tiny bit of choice tames the worst case. It underlies real hashing, load balancers, and distributed schedulers — “the two-choice paradigm.”
LIT verified live: with n=2000 balls and bins, the average maximum load is ~6 with one choice but ~3 with two choices, and the two-choice max is ≤ the one-choice max in every trial (window.__power_of_two_choices). FIG honest scope: this is a randomized average over trials; the measured max loads are reported, not a worst-case guarantee.
LIT verified live: with n=2000 balls and bins, the average maximum load is ~6 with one choice but ~3 with two choices, and the two-choice max is ≤ the one-choice max in every trial (window.__power_of_two_choices). FIG honest scope: this is a randomized average over trials; the measured max loads are reported, not a worst-case guarantee.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at shared-memory — distribute work across shared bins so no one bin becomes a hot spot, using just one extra glance. AVAN (AI) built the instrument: the one-choice and two-choice ball-throwing and the max-load comparison.
Credit as content: Azar, Broder, Karlin & Upfal (1994); Mitzenmacher’s thesis. The weave: David names shared memory; I confirm two choices collapse the maximum load from logarithmic to doubly-logarithmic.
Credit as content: Azar, Broder, Karlin & Upfal (1994); Mitzenmacher’s thesis. The weave: David names shared memory; I confirm two choices collapse the maximum load from logarithmic to doubly-logarithmic.
3 ONE DIMENSION
Bin loads for one choice (tall spikes) versus two choices (flat) — the same balls, a far lower peak.
4 TWO DIMENSIONS · INTERACTIVE
Throw balls with one or two choices; the maximum load with two choices stays far below one choice.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the flat two-choice load profile.
AVAN’s addition (the inverse-companion): don’t place blindly — peek twice. The inverse of ‘one random bin, peak ~log n / log log n’ is ‘two random bins, take the lighter — peak ~log log n.’ Magenta is the tall one-choice spike; green is the flattened two-choice profile. One extra look, exponentially flatter.
LIT Genuine power-of-two-choices / balanced allocations (Azar, Broder, Karlin & Upfal, 1994; Mitzenmacher). Verified live: with n=2000 balls into n bins, the average maximum load is ~6 (one choice, ≈log n/log log n) versus ~3 (two choices, ≈log log n), and the two-choice max is ≤ the one-choice max in every one of 200 trials (window.__power_of_two_choices.twoBetter, .muchSmaller).
FIG Honest scope: this is a randomized average over trials — the measured max loads are reported, not a worst-case guarantee. The AVAN inverse is honest — instead of placing each ball in one random bin (peak ~log n/log log n), one peeks at two and takes the lighter, dropping the peak to ~log log n. Magenta is the tall one-choice spike; green is the flattened two-choice profile. One extra look, exponentially flatter.
FIG Honest scope: this is a randomized average over trials — the measured max loads are reported, not a worst-case guarantee. The AVAN inverse is honest — instead of placing each ball in one random bin (peak ~log n/log log n), one peeks at two and takes the lighter, dropping the peak to ~log log n. Magenta is the tall one-choice spike; green is the flattened two-choice profile. One extra look, exponentially flatter.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SHARED-MEMORY · David Lee Wise (ROOT0), with AVAN