Improved Analysis of Deterministic Load-Balancing Schemes
Improved Analysis of Deterministic Load-Balancing Schemes
复制标题
确定性负载均衡方案的改进分析
DOI：
10.1145/2767386.2767413
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
P. Uznański
中科院分区：
文献类型：
--
作者：
P. Berenbrink;R. Klasing;A. Kosowski;Frederik Mallmann;P. Uznański
我们考虑在离散模型中令牌的确定性负载平衡问题。一组n个处理器连接成一个d-正则无向网络。在每个时间步中，每个处理器与网络中的每个邻居交换一些令牌。目标是尽可能快地减少负载最大和负载最小的处理器上的令牌数量之间的差异。Rabani等人（1998）提出了一种分析广泛的离散负载平衡算法的通用技术。他们的方法是描述离散平衡算法的实际负载与相关马尔可夫链生成的分布之间的偏差。马尔可夫链也可以被视为连续扩散算法的基础模型。Rabani等人证明，在时间T = O（log（Kn）/μ）之后，他们类中的任何算法都实现了O（d log n/μ）的差异，其中μ是图的转移矩阵的谱间隙，K是系统中的初始负载差异。在这项工作中，我们确定了一些自然的附加条件确定性平衡算法，从而在一类算法达到一个较小的差异。此类包含众所周知的算法，例如，旋转路由器。具体来说，我们引入的概念，累积公平的负载平衡算法，在任何时间间隔的连续时间步，令牌发送的总数量超过一个节点的边缘是相同的（常数）为所有相邻的边缘。我们证明了算法是累积公平的，每个节点在每一步都保留了足够的负载，在时间O（T）上实现了O（d log n/μ，d n）的差异。我们还表明，在一般情况下，这些假设都不能省略，而不会增加差异。然后，我们表明，任何累积公平的计划，满足一些额外的假设，几乎一样快的连续扩散过程实现了差异的O（d）的组合潜在的减少参数。这个积极的结果适用于一些最简单和最自然的离散负载平衡方案。
We consider the problem of deterministic load balancing of tokens in the discrete model. A set of n processors is connected into a d-regular undirected network. In every time step, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. Rabani et al. (1998) present a general technique for the analysis of a wide class of discrete load balancing algorithms. Their approach is to characterize the deviation between the actual loads of a discrete balancing algorithm with the distribution generated by a related Markov chain. The Markov chain can also be regarded as the underlying model of a continuous diffusion algorithm. Rabani et al. showed that after time T = O(log (Kn)/μ), any algorithm of their class achieves a discrepancy of O(d log n/μ), where μ is the spectral gap of the transition matrix of the graph, and K is the initial load discrepancy in the system. In this work we identify some natural additional conditions on deterministic balancing algorithms, resulting in a class of algorithms reaching a smaller discrepancy. This class contains well-known algorithms, e.g., the rotor-router. Specifically, we introduce the notion of cumulatively fair load-balancing algorithms where in any interval of consecutive time steps, the total number of tokens sent out over an edge by a node is the same (up to constants) for all adjacent edges. We prove that algorithms which are cumulatively fair and where every node retains a sufficient part of its load in each step, achieve a discrepancy of O(d√log n/μ ,d√n) in time O(T). We also show that in general neither of these assumptions may be omitted without increasing discrepancy. We then show by a combinatorial potential reduction argument that any cumulatively fair scheme satisfying some additional assumptions achieves a discrepancy of O(d) almost as quickly as the continuous diffusion process. This positive result applies to some of the simplest and most natural discrete load balancing schemes.