Efficient Load-Balancing through Distributed Token Dropping

2020/05/15 by Brandt, Sebastian, Keller, Barbara, Rybicki, Joel +2 · 1 citation
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.2005.07761

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(Δ⁵) rounds in graphs of maximum degree Δ, while we improve it to O(Δ⁴) and also prove a lower bound of Ω(Δ).

Cited by

• Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees

Related

• Simple Load Balancing
• Locally Optimal Load Balancing
• Local Deal-Agreement Based Monotonic Distributed Algorithms for Load\n Balancing in General Graphs
• (Almost) Perfect Discrete Iterative Load Balancing
• Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies