SPAA 2021 · 33th ACM Symposium on Parallelism in Algorithms and Architectures, online, July 2021
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.