文章基本信息
- 标题：Brief Announcement: Efficient Load-Balancing Through Distributed Token Dropping
- 本地全文：下载
- 作者：Sebastian Brandt ; Barbara Keller ; Joel Rybicki 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：179
- 页码：1-3
- DOI：10.4230/LIPIcs.DISC.2020.40
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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.
- 关键词：distributed algorithms; graph problems; semi-matching
