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 article in proceedingsScientificpeer-review

1 Citation (Scopus)
19 Downloads (Pure)


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
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages3
ISBN (Electronic)978-3-95977-168-9
Publication statusPublished - 2020
MoE publication typeA4 Conference publication
EventInternational Symposium on Distributed Computing - Virtual, Online, Germany
Duration: 12 Oct 202016 Oct 2020
Conference number: 32

Publication series

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


ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
CityVirtual, Online
Internet address


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

Cite this