Efficient load-balancing through distributed token dropping Brandt, Sebastian Keller, Barbara Rybicki, Joel ; https://orcid.org/0000-0002-6432-6646 Suomela, Jukka Uitto, Jara 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(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). 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 · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively. Association for Computing Machinery 2021 info:eu-repo/semantics/conferenceObject doc-type:ConferenceObject ConferenceObject http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/9678 Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. Efficient load-balancing through distributed token dropping. In: <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>. Association for Computing Machinery; 2021:129-139. doi:<a href="https://doi.org/10.1145/3409964.3461785">10.1145/3409964.3461785</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1145/3409964.3461785 info:eu-repo/semantics/altIdentifier/isbn/9781450380706 info:eu-repo/semantics/altIdentifier/arxiv/2005.07761 info:eu-repo/semantics/openAccess