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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

1 Sitaatiot (Scopus)

11 Lataukset (Pure)

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	34th International Symposium on Distributed Computing (DISC 2020)
Toimittajat	Hagit Attiya
Kustantaja	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivut	1-3
Sivumäärä	3
ISBN (elektroninen)	978-3-95977-168-9
DOI - pysyväislinkit	https://doi.org/10.4230/LIPIcs.DISC.2020.40
Tila	Julkaistu - 2020
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	International Symposium on Distributed Computing - Virtual, Online, Saksa Kesto: 12 lokak. 2020 → 16 lokak. 2020 Konferenssinumero: 32 http://www.disc-conference.org/wp/disc2020/

Julkaisusarja

Nimi	Leibniz International Proceedings in Informatics (LIPIcs)
Kustantaja	Schloss Dagstuhl--Leibniz-Zentrum für Informatik
Vuosikerta	179
ISSN (elektroninen)	1868-8969

Conference

Conference	International Symposium on Distributed Computing
Lyhennettä	DISC
Maa/Alue	Saksa
Kaupunki	Virtual, Online
Ajanjakso	12/10/2020 → 16/10/2020
www-osoite	http://www.disc-conference.org/wp/disc2020/

Pääsy asiakirjaan

10.4230/LIPIcs.DISC.2020.40Lisenssi: CC BY

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

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

OpenUrl-saatavuus

Koko teksti

Siteeraa tätä

Sebastian, B., Keller, B., Rybicki, J., Suomela, J., & Uitto, J. (2020). Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping. teoksessa H. Attiya (Toimittaja), 34th International Symposium on Distributed Computing (DISC 2020) (Sivut 1-3). [40] (Leibniz International Proceedings in Informatics (LIPIcs); Vuosikerta 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. julkaisussa H Attiya (Toimittaja), 34th International Symposium on Distributed Computing (DISC 2020)., 40, Leibniz International Proceedings in Informatics (LIPIcs), Vuosikerta 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Sivut 1-3, International Symposium on Distributed Computing, Virtual, Online, Saksa, 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). toim. / Hagit Attiya. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. s. 1-3 40 (Leibniz International Proceedings in Informatics (LIPIcs); Vuosikerta 179).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

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 contribution

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. julkaisussa Attiya H, toimittaja, 34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2020. s. 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

Abstrakti

Julkaisusarja

Conference

Pääsy asiakirjaan

OpenUrl-saatavuus

Sormenjälki

Siteeraa tätä