Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.40
URN: urn:nbn:de:0030-drops-131182
URL: https://drops.dagstuhl.de/opus/volltexte/2020/13118/
Brandt, Sebastian ; Keller, Barbara ; Rybicki, Joel ; Suomela, Jukka ; Uitto, Jara
Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{brandt_et_al:LIPIcs:2020:13118,
author = {Sebastian Brandt and Barbara Keller and Joel Rybicki and Jukka Suomela and Jara Uitto},
title = {{Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {40:1--40:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-168-9},
ISSN = {1868-8969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13118},
URN = {urn:nbn:de:0030-drops-131182},
doi = {10.4230/LIPIcs.DISC.2020.40},
annote = {Keywords: distributed algorithms, graph problems, semi-matching}
}
| Keywords: | distributed algorithms, graph problems, semi-matching | |
| Seminar: | 34th International Symposium on Distributed Computing (DISC 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 07.10.2020 |
