James Aspnes and Yitong Yin. Randomized load balancing by joining and splitting bins. Information Processing Letters, 112(8–9):309–313, April 2012.
Consider the following load balancing scenario: a certain amount of work load is distributed among a set of machines that may change over time as machines join and leave the system. Upon an arrival of a new machine, one of the existing machines gives some of its load to the new machine; and upon a departure of a machine, it gives all its load away to one of the existing machines in the system. Such load balancing schemes can be modeled as a simple game of joining and splitting weighted bins. Each bin corresponds to a machine in the system, and the weight of the bin represents the amount of load assigned to the machine. The arrival of a new machine corresponds to a split of a bin, and the departure of an existing machine is represented by joining two bins.
We consider what happens when the joins and splits are randomized. When the bins are split with probability proportional to their weights, it is not hard to see that this gives the same behavior as uniformly cutting a ring as in (Karger et al., 1997), which yields an O(log n) load factor for n bins. Where it is infeasible to bias the random choice with the weights, it is natural to implement uniform splits, where the split bin is sampled uniformly. Despite its simple definition, analyzing the performance of this natural load-distribution mechanism is a nontrivial task.
In this paper, we apply a novel technique based on vector norms to analyze the load balancing performance of uniform random joins and splits. We show that if only splits (with no joins) are applied, the expected load factor, the ratio between the maximum weight and the average weight of the bins, is between Ω(n0.5) and O(n0.742). We then study the performance of mixed joins and splits, and show that the expected load factor approaches O(n1/√((1/2) lg n)) after alternatively applying sufficiently many joins and splits to an arbitrary initial load assignment of n bins. These results demonstrate that the good load factor obtained by (Karger et al., 1997) depends strongly on the ability to preferentially split heavily-loaded bins.
@article{AspnesY2012,
author = {James Aspnes and Yitong Yin},
title = {Randomized load balancing by joining and splitting bins},
month=apr,
year = 2012,
journal="Information Processing Letters",
volume=112,
number={8--9},
pages={309--313}
}