Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Brandt, Sebastian; Keller, Barbara; Rybicki, Joel; Suomela, Jukka; Uitto, Jara https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-131182
URL:

; ; ; ;

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


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