SIAM Journal on Computing · 1999 · 754 citations · 6 references
ComputingComputer ScienceMathematicsAlgorithmsDistributed SystemsTheory Of ComputationAssignment ProblemsResource AllocationAllocationAllocation Policies
In the classic balls‑into‑bins model, placing each of n balls uniformly at random into n boxes results in a maximum load of (1+o(1))ln n/ln ln n with high probability. The paper investigates how this two‑choice allocation strategy impacts dynamic resource allocation, hashing, and online load balancing. The method assigns each ball to the less full of two randomly selected boxes. With high probability, the maximum load drops to ln ln n/ln 2 + O(1), an exponential improvement, and the same gap persists in an infinite process where balls are randomly deleted and reinserted using the two‑choice rule.
Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1 + o(1))ln n/ln ln n balls in it. Suppose instead that for each ball we choose two boxes at random and place the ball into the one which is less full at the time of placement. We show that with high probability, the fullest box contains only ln ln n/ln 2 + O(1) balls---exponentially less than before. Furthermore, we show that a similar gap exists in the infinite process, where at each step one ball, chosen uniformly at random, is deleted, and one ball is added in the manner above. We discuss consequences of this and related theorems for dynamic resource allocation, hashing, and on-line load balancing.
6
Yossi Azar, Andrei Broder, Anna R. Karlin · Theoretical Computer Science · 1994 · 94 citations
On-Line Load Balancing of Temporary Tasks
Yossi Azar, Bala Kalyanasundaram, Serge Plotkin et al. · Journal of Algorithms · 1997 · 76 citations