Randomized load balancing by joining and splitting bins

We analyze the performance of a very natural randomized load balancing scheme: uniformly joining and splitting weighted bins. We develop a norm-based technique for analyzing this simple procedure. By applying the technique, we prove several bounds for the expected load factor. Specifically, if we keep uniformly splitting the bins without joining them, the expected load factor is between Ω(n0.5)Ω(n0.5) and O(n0.742)O(n0.742), however, if we alternatively join and split bins, the expected load factor converges to O(n1/12log2n). These bounds justify the intuition that the power of being adaptive to the current loads is essential for load balancing tasks, and they also show a somehow surprising phenomenon that joins can actually help load balancing if such power is not available.

► Study of the load balance performance of uniform joining and splitting bins.
► An Ω(n0.5)Ω(n0.5) lower bound for split-only process.
► An O(n0.742)O(n0.742) upper bound for split-only process.
► An O(n1/12log2n) upper bound for join–split alternations.