Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping

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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

4 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äiskieliEnglanti
Otsikko34th International Symposium on Distributed Computing (DISC 2020)
ToimittajatHagit Attiya
KustantajaSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Sivut1-3
Sivumäärä3
ISBN (elektroninen)978-3-95977-168-9
DOI - pysyväislinkit
TilaJulkaistu - 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Distributed Computing - Virtual, Online, Saksa
Kesto: 12 lokak. 202016 lokak. 2020
Konferenssinumero: 32
http://www.disc-conference.org/wp/disc2020/

Julkaisusarja

NimiLeibniz International Proceedings in Informatics (LIPIcs)
KustantajaSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Vuosikerta179
ISSN (elektroninen)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
LyhennettäDISC
Maa/AlueSaksa
KaupunkiVirtual, Online
Ajanjakso12/10/202016/10/2020
www-osoite

Sormenjälki

Sukella tutkimusaiheisiin 'Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä