James Aspnes and Yitong Yin. Randomized load balancing by joining and splitting bins. Submitted to STACS 2009.
We study the following load balancing game: initially there is only one bin, which contains all the load; and at each time, either one existing bin is split into two bins, or two bins are joined into one bin. The choice of which bins to split or join is random; we assume a uniform choice on joins, but consider two different distributions for splits. The first is a weighted split, where the bin to split is chosen with a probability proportional to its weight; and a non-weighted split, where the bin to split is chosen uniformly from all bins. For each model, we analyze the ratio between the maximum load and the average load. We show that for weighted splits with uniform joins, this load factor is always Θ(log n) in expectation in any state with n bins; this bound is independent of the sequence of joins and splits. For non-weighted splits, we show that the expected load factor after applying n non-weighted splits to one initial bin is between Ω(n0.5) and O(n0.741). We study the performance of mixed joins and non-weighted splits, and show that the expected load factor approaches O(n1/√(½ lg n)) after alternatively applying sufficiently many joins and non-weighted splits to an arbitrary initial load assignment of n bins.
@unpublished{AspnesY2008balancing,
author = {James Aspnes and Yitong Yin},
title = {Randomized load balancing by joining and splitting bins},
month=sep,
year = 2008,
note = "Submitted to STACS 2009"}