Quasirandom load balancing

DOI10.1137/100799216MaRDI QIDQ3143292zbMATH OpenOpenAlexFDO

Authors Tobias Friedrich, Martin Gairing, Thomas Sauerwald

Publication date 29 November 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.3302

zbMATH Keywords

distributed computingload balancingquasirandomnessrandom walkrandomized algorithms

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Distributed algorithms (68W15) Randomized algorithms (68W20)

Abstract: We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a random algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm surprisingly closely approximates the idealized process (where the tokens are divisible) on important network topologies. On d-dimensional torus graphs with n nodes it deviates from the idealized process only by an additive constant. In contrast to that, the randomized rounding approach of Friedrich and Sauerwald (2009) can deviate up to Omega(polylog(n)) and the deterministic algorithm of Rabani, Sinclair and Wanka (1998) has a deviation of Omega(n^{1/d}). This makes our quasirandom algorithm the first known algorithm for this setting which is optimal both in time and achieved smoothness. We further show that also on the hypercube our algorithm has a smaller deviation from the idealized process than the previous algorithms.

Recommendations

• Quasirandom load balancing
• Near-perfect load balancing by randomized rounding
• scientific article; zbMATH DE number 6783405
• Randomized diffusion for indivisible loads
• Improved analysis of deterministic load-balancing schemes

Cited in

(16)

• Periodic load balancing
• Total variation discrepancy of deterministic random walks for ergodic Markov chains
• Discrete load balancing on complete bipartite graphs
• Does adding more agents make a difference? A case study of cover time for the rotor-router
• Deterministic random walks for rapidly mixing chains
• Unbounded discrepancy of deterministic random walks on grids
• Reachability switching games
• Reachability Switching Games
• Near-perfect load balancing by randomized rounding
• Randomized rumour spreading: the effect of the network topology
• Quasirandom load balancing
• A simple approach for adapting continuous load balancing processes to discrete settings
• The Power of Filling in Balanced Allocations
• Dynamic load balancing by random matchings
• An analysis of load-balancing algorithms on edge-Markovian evolving graphs
• Randomized diffusion for indivisible loads

This page was built for publication: Quasirandom load balancing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3143292)