Efficient Load-Balancing through Distributed Token Dropping Article Swipe

View

Related Concepts

Security token Computer science Graph Omega Distributed algorithm Distributed computing Combinatorics Theoretical computer science Mathematics Computer network Physics Quantum mechanics

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

YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.1145/3409964.3461785 · OA: W3025453635

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 $Ω(Δ)$.