Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
Date
2020
Major/Subject
Mcode
Degree programme
Language
en
Pages
3
1-3
Series
34th International Symposium on Distributed Computing (DISC 2020), Leibniz International Proceedings in Informatics (LIPIcs), Volume 179
Abstract
We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for the stable orientation problem, which is a special case of the more general locally optimal semi-matching problem. The prior work by Czygrinow et al. (DISC 2012) finds a locally optimal semi-matching in O(Δ⁵) rounds in graphs of maximum degree Δ, which directly implies an algorithm with the same runtime for stable orientations. We improve the runtime to O(Δ⁴) for stable orientations and prove a lower bound of Ω(Δ) rounds.
Description
Keywords
Other note
Citation
Sebastian, B, Keller, B, Rybicki, J, Suomela, J & Uitto, J 2020, Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping . in H Attiya (ed.), 34th International Symposium on Distributed Computing (DISC 2020) ., 40, Leibniz International Proceedings in Informatics (LIPIcs), vol. 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-3, International Symposium on Distributed Computing, Virtual, Online, Germany, 12/10/2020 . https://doi.org/10.4230/LIPIcs.DISC.2020.40