文章基本信息

标题：Randomized Load Balancing on Networks with Stochastic Inputs
本地全文：下载
作者：Leran Cai ; Thomas Sauerwald
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：139:1-139:14
DOI：10.4230/LIPIcs.ICALP.2017.139
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 a new upper bound on the t-step transition probability of a general Markov chain, which is derived by invoking the evolving set process.
关键词：random walks; randomized algorithms; parallel computing