Document Open Access Logo

Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.DISC.2020.40.pdf
  • Filesize: 296 kB
  • 3 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • distributed algorithms
  • graph problems
  • semi-matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Sebastian Brandt, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto. Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 40:1-40:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.40

Author Details

Sebastian Brandt
  • ETH Zürich, Switzerland
Barbara Keller
  • Aalto University, Finland
Joel Rybicki
  • IST Austria, Klosterneuburg, Austria
Jukka Suomela
  • Aalto University, Finland
Jara Uitto
  • Aalto University, Finland

References

  1. Matti Åstrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In SPAA, 2010. URL: https://doi.org/10.1145/1810479.1810533.
  2. Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower Bounds for Maximal Matchings and Maximal Independent Sets. In FOCS, 2019. URL: https://doi.org/10.1109/FOCS.2019.00037.
  3. Sebastian Brandt. An Automatic Speedup Theorem for Distributed Problems. In PODC, 2019. URL: https://doi.org/10.1145/3293611.3331611.
  4. Andrzej Czygrinow, Michal Hanćkowiak, Edyta Szymańska, and Wojciech Wawrzyniak. Distributed 2-Approximation Algorithm for the Semi-matching Problem. In DISC, 2012. URL: https://doi.org/10.1007/978-3-642-33651-5_15.
  5. Mika Göös, Juho Hirvonen, and Jukka Suomela. Linear-in-Δ lower bounds in the LOCAL model. Distributed Computing, 30(5), 2017. URL: https://doi.org/10.1007/s00446-015-0245-8.
  6. Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. On the Distributed Complexity of Computing Maximal Matchings. In SODA, 1998. Google Scholar
  7. Nathan Linial. Locality in Distributed Graph Algorithms. SIAM J. Comput., 21(1), 1992. URL: https://doi.org/10.1137/0221015.
  8. Moni Naor and Larry Stockmeyer. What Can be Computed Locally? SIAM J. Comput., 24(6), 1995. URL: https://doi.org/10.1137/S0097539793254571.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact