Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping

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

doi:10.4230/LIPIcs.DISC.2020.40

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 proceeding › Conference article in proceedings › Scientific › peer-review

1 Citation (Scopus)

45 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 language	English
Title of host publication	34th International Symposium on Distributed Computing (DISC 2020)
Editors	Hagit Attiya
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-3
Number of pages	3
ISBN (Electronic)	978-3-95977-168-9
DOIs	https://doi.org/10.4230/LIPIcs.DISC.2020.40
Publication status	Published - 2020
MoE publication type	A4 Conference publication
Event	International Symposium on Distributed Computing - Virtual, Online, Germany Duration: 12 Oct 2020 → 16 Oct 2020 Conference number: 32 http://www.disc-conference.org/wp/disc2020/

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl--Leibniz-Zentrum für Informatik
Volume	179
ISSN (Electronic)	1868-8969

Conference

Conference	International Symposium on Distributed Computing
Abbreviated title	DISC
Country/Territory	Germany
City	Virtual, Online
Period	12/10/2020 → 16/10/2020
Internet address	http://www.disc-conference.org/wp/disc2020/

Access to Document

10.4230/LIPIcs.DISC.2020.40Licence: CC BY

Brandt_Brief_Announcement.LIPIcs-DISC-2020-40Final published version, 295 KBLicence: CC BY

https://drops.dagstuhl.de/opus/volltexte/2020/13118/Licence: CC BY

Cite this

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) (pp. 1-3). Article 40 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 179). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2020.40

@inproceedings{9b72d885d7ac4a289f327abf240dc9db,

title = "Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping",

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. ",

author = "Brandt Sebastian and Barbara Keller and Joel Rybicki and Jukka Suomela and Jara Uitto",

year = "2020",

doi = "10.4230/LIPIcs.DISC.2020.40",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--3",

editor = "Hagit Attiya",

booktitle = "34th International Symposium on Distributed Computing (DISC 2020)",

address = "Germany",

note = "International Symposium on Distributed Computing, DISC ; Conference date: 12-10-2020 Through 16-10-2020",

url = "http://www.disc-conference.org/wp/disc2020/",

}

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

Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping. / Sebastian, Brandt; Keller, Barbara; Rybicki, Joel et al.
34th International Symposium on Distributed Computing (DISC 2020). ed. / Hagit Attiya. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. p. 1-3 40 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 179).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping

AU - Sebastian, Brandt

AU - Keller, Barbara

AU - Rybicki, Joel

AU - Suomela, Jukka

AU - Uitto, Jara

N1 - Conference code: 32

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

U2 - 10.4230/LIPIcs.DISC.2020.40

DO - 10.4230/LIPIcs.DISC.2020.40

M3 - Conference article in proceedings

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 3

BT - 34th International Symposium on Distributed Computing (DISC 2020)

A2 - Attiya, Hagit

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Symposium on Distributed Computing

Y2 - 12 October 2020 through 16 October 2020

ER -

Sebastian B, Keller B, Rybicki J, Suomela J , Uitto J. Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping. In Attiya H, editor, 34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2020. p. 1-3. 40. (Leibniz International Proceedings in Informatics (LIPIcs)). doi: 10.4230/LIPIcs.DISC.2020.40

Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this