Summary: Randomized Load Balancing by Joining and Splitting Bins
Yitong Yin §
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 , 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. This is a natural choice, for example, in a peer-to-peer
system where a uniform sampling mechanism is available (e.g., [1,4]). 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