License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.18
URN: urn:nbn:de:0030-drops-180707
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18070/
Go to the corresponding LIPIcs Volume Portal

Berenbrink, Petra ; Hintze, Lukas ; Hosseinpour, Hamed ; Kaaser, Dominik ; Rau, Malin

Dynamic Averaging Load Balancing on Arbitrary Graphs

pdf-format:
LIPIcs-ICALP-2023-18.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{berenbrink_et_al:LIPIcs.ICALP.2023.18,
  author =	{Berenbrink, Petra and Hintze, Lukas and Hosseinpour, Hamed and Kaaser, Dominik and Rau, Malin},
  title =	{{Dynamic Averaging Load Balancing on Arbitrary Graphs}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18070},
  URN =		{urn:nbn:de:0030-drops-180707},
  doi =		{10.4230/LIPIcs.ICALP.2023.18},
  annote =	{Keywords: Dynamic Load Balancing, Distributed Computing, Randomized Algorithms, Drift Analysis}
}

Keywords: Dynamic Load Balancing, Distributed Computing, Randomized Algorithms, Drift Analysis
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI