Options
Dynamic averaging load balancing on arbitrary graphs
Citation Link: https://doi.org/10.15480/882.13975
Publikationstyp
Conference Paper
Date Issued
2023-02
Sprache
English
Author(s)
Institut
TORE-DOI
First published in
Number in series
261
Article Number
18
Citation
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023): 18
Contribution to Conference
Publisher DOI
Scopus ID
ArXiv ID
ISBN
978-3-95977-278-5
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.
Subjects
Dynamic Load Balancing
Distributed Computing
Randomized Algorithms
Drift Analysis
DDC Class
004: Informatik
Loading...
Name
LIPIcs.ICALP.2023.18.pdf
Type
Main Article
Size
866.84 KB
Format
Adobe PDF