Alistarh Dan, Nadiradze Giorgi, Sabour Amirmojtaba
IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria.
Algorithmica. 2022;84(4):1007-1029. doi: 10.1007/s00453-021-00905-9. Epub 2021 Dec 24.
We consider the following dynamic load-balancing process: given an underlying graph with nodes, in each step , 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 nodes their 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 on and 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 length the only known upper bound on the expected gap is of order , 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 . We introduce a new potential analysis technique, which enables us to bound the difference in load between -hop neighbors on the cycle, for any . 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 . Additionally, we provide experimental evidence that our upper bound on the gap is tight up to a logarithmic factor.
给定一个具有(n)个节点的基础图，在每一步(t)，选择一条随机边，创建一个单位的负载，并将其放置在其中一个端点上。在同一步骤中，假设负载可以任意分割，两个节点通过平均它们的负载来重新分配负载。我们感兴趣的是随着过程的进行，节点上最小负载和最大负载之间的期望差距，以及它对(n)和图结构的依赖关系。佩雷斯等人（《随机结构与算法》47(4):760 - 775，2015）研究了这个过程的变体，其中负载单位被放置在所选边的负载最小的端点上，并且不进行平均操作。在长度为(n)的循环上进行动态负载均衡的情况下，由于同一工作中的优超论证，关于期望差距的唯一已知上界是(O(\sqrt{\log n}))。在本文中，我们利用平均的力量，提供了一个改进的上界(O((\log n)^{2/3}))。我们引入了一种新的势能分析技术，这使我们能够界定循环上任意(k)跳邻居之间的负载差异。我们用一个“差距覆盖”论证来补充这一点，该论证通过界定其在特定结构的所有可能子集上的值，并递归地界定每个子集中的差距，来界定差距的最大值。我们还表明，我们的分析可以扩展到哈拉里图的特定实例。另一方面，我们证明差距的期望二阶矩下限为(\Omega(\log n))。此外，我们提供了实验证据，表明我们的差距上界在对数因子范围内是紧的。
