Indexing the archive…
Your Universe of Digital Possibilities
Throw a million jobs at a million servers at random and some server is buried under nine. Let every job glance at just two and join the shorter, and the worst pile is four — the gap between logarithmic and doubly logarithmic, bought with one more question.
Throw n balls into n bins uniformly at random and the fullest bin holds about this many — about 9 for a million bins. The asymptote is slow: at a million it says 5.3, and Γ⁻¹ is what the bins actually do.
Let each ball look at d bins and join the least loaded and the fullest falls from logarithmic to doubly logarithmic: 4 for a million bins with d = 2. Almost all the gain is in the second look; the third only divides by ln 3 instead of ln 2.
Jobs arrive at rate λ per server, each joins the shortest of d sampled queues, service takes one unit on average. The fraction of queues with at least i jobs is si: geometric λi for one choice, doubly exponential for two. At λ = 0.9 the mean time in system falls from 10 to about 2.61.
The Window shared a wire by feel; The Choice shares the work by a glance. No dispatcher knows the loads — each job asks two servers and keeps the better answer, and that one extra question does what a central scheduler does, nearly, for a constant bill. It is the engineered cousin of The Walk: there one random step at a time wanders logarithmically far; here two random looks at a time pull the worst case down to doubly logarithmic. Next, The Hash asks how to keep a map of the work stable when the servers themselves come and go.