Randomized Load Balancing on Networks with Stochastic Inputs
Randomized Load Balancing on Networks with Stochastic Inputs
复制标题
DOI：
10.4230/lipics.icalp.2017.139
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Leran Cai;Thomas Sauerwald
中科院分区：
文献类型：
--
作者：
Leran Cai;Thomas Sauerwald
针对不可分令牌的迭代负载均衡算法在过去已经得到了深入的研究。补充以前的最坏情况下的分析，我们研究了平均情况下的情况下，从一个固定的概率分布的负载输入。对于循环，环面，超立方体和膨胀，我们得到几乎匹配的上下界的差异，最大和最小负载之间的差异。我们的边界适用于各种概率分布，包括均匀分布和二项分布，但也适用于范围无界的分布，如泊松分布和几何分布。对于像周期和环面的收敛速度慢的图，我们的结果表明，在最坏和平均情况下的收敛性之间有很大的差异。在我们的分析中的一个重要组成部分是一个一般的马尔可夫链，这是通过调用不断变化的集合过程的t步转移概率的新的上界。
Iterative load balancing algorithms for indivisible tokens have been studied intensively in the past. Complementing previous worst-case analyses, we study an average-case scenario where the load inputs are drawn from a fixed probability distribution. For cycles, tori, hypercubes and expanders, we obtain almost matching upper and lower bounds on the discrepancy, the difference between the maximum and the minimum load. Our bounds hold for a variety of probability distributions including the uniform and binomial distribution but also distributions with unbounded range such as the Poisson and geometric distribution. For graphs with slow convergence like cycles and tori, our results demonstrate a substantial difference between the convergence in the worst- and average-case. An important ingredient in our analysis is new upper bound on the t-step transition probability of a general Markov chain, which is derived by invoking the evolving set process.