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

Efficient load-balancing through distributed token dropping

SPAA 2021 · 33th ACM Symposium on Parallelism in Algorithms and Architectures, online, July 2021 · doi:10.1145/3409964.3461785

authors’ version publisher’s version arXiv.org

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 stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in $O(\Delta^5)$ rounds in graphs of maximum degree $\Delta$, while we improve it to $O(\Delta^4)$ and also prove a lower bound of $\Omega(\Delta)$. For the more general problem of locally optimal semi-matchings, the prior upper bound is $O(S^5)$ and our new algorithm runs in $O(C \cdot S^4)$ rounds, which is an improvement for $C = o(S)$; here $C$ and $S$ are the maximum degrees of customers and servers, respectively.

Publication

Kunal Agrawal and Yossi Azar (Eds.): SPAA ’21, Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, pages 129–139, ACM Press, New York, 2021

ISBN 978-1-4503-8070-6

Links

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.