In this paper we study dynamic averaging load balancing on general graphs. We consider infinite time and dynamic processes, where in every step new load items are assigned to randomly chosen nodes. A matching is chosen, and the load is averaged over the edges of that matching. We analyze the discrete case where load items are indivisible, moreover our results also carry over to the continuous case where load items can be split arbitrarily. For the choice of the matchings we consider three different models, random matchings of linear size, random matchings containing only single edges, and deterministic sequences of matchings covering the whole graph. We bound the discrepancy, which is defined as the difference between the maximum and the minimum load. Our results cover a broad range of graph classes and, to the best of our knowledge, our analysis is the first result for discrete and dynamic averaging load balancing processes. As our main technical contribution we develop a drift result that allows us to apply techniques based on the effective resistance in an electrical network to the setting of dynamic load balancing.
翻译:在本文中,我们研究一般图形的平均动态负载平衡。 我们考虑无限的时间和动态过程, 每一步新负载项目都被指定为随机选择的节点。 选择匹配, 负载平均在匹配的边缘上。 我们分析负载项目不可分割的离散案例, 此外, 我们的结果还传递到可任意分割负载项目的连续案例。 为了选择匹配, 我们考虑三种不同的模型, 随机匹配线性大小, 随机匹配仅包含单边, 以及覆盖整个图形的定式匹配序列 。 我们将差异绑定为最大和最小负载之间的差别。 我们的结果覆盖了广泛的图表类别, 并且据我们所知, 我们的分析是离散和动态平均负载平衡过程的第一个结果。 作为我们的主要技术贡献, 我们开发了一个漂移结果, 使我们能够应用基于电子网络有效阻力的技术, 来设定动态负载平衡。