Dynamic Averaging Load Balancing on Cycles
Dan-Adrian Alistarh, Giorgi Nadiradze, Amirmojtaba Sabour · Algorithmica · 2021
Abstract We consider the following dynamic load-balancing process: given an underlying graphGwithnnodes, in each step $$t\ge 0$$ t≥0 , a random edge is chosen, one unit of load is created, and placed at one of the endpoints. In the same step, assuming that loads are arbitrarily divisible, the two nodesbalancetheir loads by averaging them. We are interested in the expected gap between the minimum and maximum loads at nodes as the process progresses, and its dependence onnand on the graph structure. Peres et al. (Random Struct Algorithms 47(4):760–775, 2015) studied the variant of this process, where the unit of load is placed in the least loaded endpoint of the chosen edge, and the averaging is not performed. In the case of dynamic load balancing on the cycle of lengthnthe only known upper bound on the expected gap is of order $$\mathcal {O}( n \log n )$$ O(nlogn) , following from the majorization argument due to the same work. In this paper, we leverage the power of averaging and provide an improved upper bound of $$\mathcal {O} ( \sqrt{n} \log n )$$ O(nlogn) . We introduce a new potential analysis technique, which enables us to bound the difference in load betweenk-hop neighbors on the cycle, for any $$k \le n/2$$ k≤n/2 . We complement this with a “gap covering” argument, which bounds the maximum value of the gap by bounding its value across all possible subsets of a certain structure, and recursively bounding the gaps within each subset. We also show that our analysis can be extended to the specific instance of Harary graphs. On the other hand, we prove that the expected second moment of the gap is lower bounded by $$\Omega (n)$$ Ω(n) . Additionally, we provide experimental evidence that our upper bound on the gap is tight up to a logarithmic factor.