DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2017.139

Randomized Load Balancing on Networks with Stochastic Inputs

Authors: Leran Cai and Thomas Sauerwald

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract

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.

Cite as

Leran Cai and Thomas Sauerwald. Randomized Load Balancing on Networks with Stochastic Inputs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 139:1-139:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ICALP.2017.139,
  author =	{Cai, Leran and Sauerwald, Thomas},
  title =	{{Randomized Load Balancing on Networks with Stochastic Inputs}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{139:1--139:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.139},
  URN =		{urn:nbn:de:0030-drops-74839},
  doi =		{10.4230/LIPIcs.ICALP.2017.139},
  annote =	{Keywords: random walks, randomized algorithms, parallel computing}
}

Search Results

Documents authored by Cai, Leran

Randomized Load Balancing on Networks with Stochastic Inputs

Abstract

Cite as

Thanks for your feedback!

Could not send message