论文标题
通过分布式令牌下降有效的负载平衡
Efficient Load-Balancing through Distributed Token Dropping
论文作者
论文摘要
我们介绍了一个新的图形问题，即令牌删除游戏，并展示了如何在分布式设置中有效地解决它。我们使用令牌删除游戏作为一种工具，以设计有效的分布式算法，以实现稳定的方向，更通常用于本地最佳的半匹配。 Czygrinow等人的先前工作。 （DISC 2012）在$ O（δ^5）$ $ graphs $δ$的图中找到了稳定的方向，而我们将其提高到$ O（δ^4）$，并且也证明了$ω（δ）$的下限。
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 $Ω(Δ)$.
