Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping

Brandt Sebastian, Barbara Keller, Joel Rybicki, Jukka Suomela, Jara Uitto

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2 Downloads (Pure)

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.
Original languageEnglish
Title of host publication34th International Symposium on Distributed Computing (DISC 2020)
EditorsHagit Attiya
Pages1-3
Number of pages3
ISBN (Electronic)978-3-95977-168-9
DOIs
Publication statusPublished - 2020
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Distributed Computing - Virtual, Online, Germany
Duration: 12 Oct 202016 Oct 2020
Conference number: 32
http://www.disc-conference.org/wp/disc2020/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Volume179
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
CountryGermany
CityVirtual, Online
Period12/10/202016/10/2020
Internet address

Fingerprint Dive into the research topics of 'Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping'. Together they form a unique fingerprint.

Cite this