LNCS 2764 Perfectly Balanced Allocation 1st Edition by Artur Czumaj, Chris Riley, Christian Scheideler ISBN 3540380450 9783540380450

We investigate randomized processes underlying load balancing based on the multiple-choice paradigm: m balls have to be placed in n bins, and each ball can be placed into one out of 2 randomly selected bins. The aim is to distribute the balls as evenly as possible among the bins. Previously, it was known that a simple process that places the balls one by one in the least loaded bin can achieve a maximum load of m/n + Θ(loglogn) with high probability. Furthermore, it was known that it is possible to achieve (with high probability) a maximum load of at most ⌈m/n ⌉ + 1 using maximum flow computations.

In this paper, we extend these results in several aspects. First of all, we show that if m ≥ c n logn for some sufficiently large c, then a perfect distribution of balls among the bins can be achieved (i.e., the maximum load is ⌈m/n ⌉) with high probability. The bound for m is essentially optimal, because it is known that if m ≤ c′ n logn for some sufficiently small constant c′, the best possible maximum load that can be achieved is ⌈m/n ⌉ + 1 with high probability. Next, we analyze a simple, randomized load balancing process based on a local search paradigm. Our first result here is that this process always converges to a best possible load distribution. Then, we study the convergence speed of the process. We show that if m is sufficiently large compared to n, then no matter with which ball distribution the system starts, if the imbalance is Δ, then the process needs only Δ · n ^O(1) steps to reach a perfect distribution, with high probability. We also prove a similar result for m ≈ n, and show that if m = O(n logn / loglogn), then an optimal load distribution (which has the maximum load of ⌈m/n ⌉ + 1) is reached by the random process after a polynomial number of steps, with high probability.