THE FOLD / LOOT / THE VAULT / THE LOTTERY SCHEDULER
THE LOTTERY SCHEDULER
a window too short for the limit to have arrived
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Hand out tickets in proportion to the share each process should get, then draw one at random and run its owner. No queue to maintain, no priorities to age, no bookkeeping at all — and it is only fair on average.
LIT verified live. Tickets 10 / 20 / 30 / 40, and the error measured as a mean over 200 independent runs at each size. At 100 draws the total absolute share error is 0.1296; at 6,400 it is 0.01694. Every quadrupling of the draws roughly halves the error — measured ratios 2.037, 1.899, 1.978 against the 2 that 1/√N predicts. The fairness is real, and it is asymptotic.
LIT verified live. Tickets 10 / 20 / 30 / 40, and the error measured as a mean over 200 independent runs at each size. At 100 draws the total absolute share error is 0.1296; at 6,400 it is 0.01694. Every quadrupling of the draws roughly halves the error — measured ratios 2.037, 1.899, 1.978 against the 2 that 1/√N predicts. The fairness is real, and it is asymptotic.
2 HOW IT WAS WEAVED · AI + HUMAN
Lottery scheduling is Waldspurger and Weihl’s (1994); the appeal is that proportional share falls out of the draw with no state to keep.
AVAN (AI) first gated this on the error shrinking at every step and it failed — 10,000 draws came out worse than 1,000, because a single Monte Carlo walk is not monotonic and never was. The claim being made is a rate, and a rate cannot be read off one walk. Averaging 200 runs per point is what turns the assertion into a measurement.
AVAN (AI) first gated this on the error shrinking at every step and it failed — 10,000 draws came out worse than 1,000, because a single Monte Carlo walk is not monotonic and never was. The claim being made is a rate, and a rate cannot be read off one walk. Averaging 200 runs per point is what turns the assertion into a measurement.
3 ONE DIMENSION
Error against draws. Four times the draws, half the error.
4 TWO DIMENSIONS · INTERACTIVE
Draw tickets and watch the shares settle.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a share that only exists over time.
AVAN’s addition (the inverse-companion): the forward reading is that lottery scheduling gives proportional share. The inverse is that it gives it to nobody who is watching. A process holding 40 of 100 tickets can lose ten draws running, and over any window short enough for a person to notice, the guarantee simply is not there. Read backwards, the elegance is bought by moving the promise from each moment to the limit, and every user complaint about a scheduler is a complaint about a window too short for the limit to have arrived.
LIT tickets of 10, 20, 30 and 40 with the error measured as a mean over 200 independent runs give a total absolute share error of 0.1296 at 100 draws and 0.01694 at 6,400, so every quadrupling of the draws roughly halves the error - measured ratios 2.037, 1.899 and 1.978 against the 2 that 1/sqrt(N) predicts
FIG Lottery scheduling is Waldspurger and Weihl's (1994); the appeal is that proportional share falls out of the draw with no state to keep. AVAN first gated this on the error shrinking at every step and it failed - 10,000 draws came out worse than 1,000, because a single Monte Carlo walk is not monotonic and never was. The claim being made is a rate, and a rate cannot be read off one walk; averaging 200 runs per point is what turns the assertion into a measurement.
FIG Lottery scheduling is Waldspurger and Weihl's (1994); the appeal is that proportional share falls out of the draw with no state to keep. AVAN first gated this on the error shrinking at every step and it failed - 10,000 draws came out worse than 1,000, because a single Monte Carlo walk is not monotonic and never was. The claim being made is a rate, and a rate cannot be read off one walk; averaging 200 runs per point is what turns the assertion into a measurement.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE VAULT · David Lee Wise (ROOT0), with AVAN