2000 · 83 citations · 22 references
ComputingComputer ScienceMathematicsAlgorithmsDistributed SystemsTheory Of ComputationAssignment ProblemsResource AllocationAllocationAllocation Policies
We investigate load balancing processes based on the multiplechoice paradigm. In these randomized processes m balls are inserted into n bins. In the classical single-choice variant each ball is placed simply into a randomly selected bin. In a multiple-choice process each ball can be placed into one out of d _> 2 randomly selected bins. It is well known that having more than one choice for each ball can improve the load balance significantly. In contrast to previous work on multiple-choice processes, we investigate the heavily loaded case, that is, we assume m >> n rather than m ,.~ n. The best previously known results for the multiple-choice processes in the heavily loaded case were obtained by majorization from the single-choice process. This yields an upper bound of
22
Stéphane Crépey, Olivier Guéant, David Hobson et al. · HAL (Le Centre pour la Communication Scientifique Directe) · 2011 · 10.2K citations
Yossi Azar, Andrei Broder, Anna R. Karlin et al. · SIAM Journal on Computing · 1999 · 754 citations
Path coupling: A technique for proving rapid mixing in Markov chains
Russ Bubley, Martin Dyer · 2002 · 365 citations