On the power of two choices: Balls and bins in continuous time
Authors:
- Malwina J. LuczakMLMalwina J. Luczak
- Colin McDiarmidCMColin McDiarmid
Open Access
- 1 August 2005
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 15 (3) , 1733-1764
Abstract
Suppose that there are n bins, and balls arrive in a Poisson process at rate λn, where λ>0 is a constant. Upon arrival, each ball chooses a fixed number d of random bins, and is placed into one with least load. Balls have independent exponential lifetimes with unit mean. We show that the system converges rapidly to its equilibrium distribution; and when d≥2, there is an integer-valued function md(n)=ln ln n/ln d+O(1) such that, in the equilibrium distribution, the maximum load of a bin is concentrated on the two values md(n) and md(n)−1, with probability tending to 1, as n→∞. We show also that the maximum load usually does not vary by more than a constant amount from ln ln n/ln d, even over quite long periods of time.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- On the maximum queue length in the supermarket modelThe Annals of Probability, 2006
- On-line routing of random calls in networksProbability Theory and Related Fields, 2003
- Bins and balls; Large deviations of the empirical occupancy processThe Annals of Applied Probability, 2002
- Kinetic Limits for Large Communication Networks2000
- Studying Balanced Allocations with Differential EquationsCombinatorics, Probability and Computing, 1999
- Balanced AllocationsSIAM Journal on Computing, 1999
- Concentration1998
- The Effect of Increasing Routing Choice on Resource PoolingProbability in the Engineering and Informational Sciences, 1998
- Chaos hypothesis for a system interacting through shared resourcesProbability Theory and Related Fields, 1994
- On the method of bounded differences1989