Improved Analysis of Deterministic Load-Balancing Schemes

ABSTRACT

We consider the problem of deterministic load balancing of tokens in the discrete model. A set of n processors is connected into a d-regular undirected network. In every time step, each processor exchanges some of its tokens with each of its neighbors in the network. The goal is to minimize the discrepancy between the number of tokens on the most-loaded and the least-loaded processor as quickly as possible. Rabani et al. (1998) present a general technique for the analysis of a wide class of discrete load balancing algorithms. Their approach is to characterize the deviation between the actual loads of a discrete balancing algorithm with the distribution generated by a related Markov chain. The Markov chain can also be regarded as the underlying model of a continuous diffusion algorithm. Rabani et al. showed that after time T = O(log (Kn)/μ), any algorithm of their class achieves a discrepancy of O(d log n/μ), where μ is the spectral gap of the transition matrix of the graph, and K is the initial load discrepancy in the system.

In this work we identify some natural additional conditions on deterministic balancing algorithms, resulting in a class of algorithms reaching a smaller discrepancy. This class contains well-known algorithms, e.g., the rotor-router. Specifically, we introduce the notion of cumulatively fair load-balancing algorithms where in any interval of consecutive time steps, the total number of tokens sent out over an edge by a node is the same (up to constants) for all adjacent edges. We prove that algorithms which are cumulatively fair and where every node retains a sufficient part of its load in each step, achieve a discrepancy of O(d√log n/μ ,d√n) in time O(T). We also show that in general neither of these assumptions may be omitted without increasing discrepancy. We then show by a combinatorial potential reduction argument that any cumulatively fair scheme satisfying some additional assumptions achieves a discrepancy of O(d) almost as quickly as the continuous diffusion process. This positive result applies to some of the simplest and most natural discrete load balancing schemes.

References

1. C. Adolphs and P. Berenbrink. Distributed self-prefering load balancing with weights and speeds. In PODC, pages 135--144, 2012.
2. C. Adolphs and P. Berenbrink. Improved bounds on diffusion load balancing. In IPDPS, 2012.
3. H. Akbari and P. Berenbrink. Parallel rotor walks on finite graphs and applications in discrete load balancing. In SPAA, pages 186--195, 2013.
4. H. Akbari, P. Berenbrink, and T. Sauerwald. A simple approach for adapting continuous load balancing processes to discrete settings. In PODC, pages 271--280, 2012.
5. P. Berenbrink, C. Cooper, T. Friedetzky, T. Friedrich, and T. Sauerwald. Randomized diffusion for indivisible loads. In SODA, pages 429--439, 2011.
6. J. Cooper, B. Doerr, T. Friedrich, and J. Spencer. Deterministic random walks on regular trees. Random Struct. Algorithms, 37(3):353--366, 2010.
7. J. Cooper and J. Spencer. Simulating a random walk with constant error. Combinatorics, Probability and Computing, 15:815--822, 2006.
8. B. Doerr and T. Friedrich. Deterministic random walks on the two-dimensional grid. Combinatorics, Probability and Computing, 18(1--2):123--144, 2009.
9. T. Friedrich, M. Gairing, and T. Sauerwald. Quasirandom load balancing. In SODA, pages 1620--1629, 2010.
10. T. Friedrich and T. Sauerwald. Near-perfect load balancing by randomized rounding. In STOC, pages 121--130, 2009.
11. T. Friedrich and T. Sauerwald. The cover time of deterministic random walks. In COCOON, pages 130--139, 2010.
12. S. Kijima, K. Koga, and K. Makino. Deterministic random walks on finite graphs. In ANALCO, pages 16--25, 2012.
13. A. Kosowski and D. Pająk. Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router. In ICALP, pages 544--555, 2014.
14. D. Levin, Y. Peres, and E. Wilmer. Markov chains and mixing times. American Mathematical Society, 2006.
15. J. Norris, Y. Peres, A. Zhai. Surprise probabilities in Markov chains. In SODA, pages 1759--1773, 2015.
16. V. Priezzhev, D. Dhar, A. Dhar, and S. Krishnamurthy. Eulerian walkers as a model of self-organized criticality. Phys. Rev. Lett., 77:5079--5082, 1996.
17. Y. Rabani, A. Sinclair, and R. Wanka. Local divergence of Markov chains and the analysis of iterative load-balancing schemes. In FOCS, pages 694--703, 1998.
18. T. Sauerwald and H. Sun. Tight bounds for randomized load balancing on arbitrary network topologies. In FOCS, pages 341--350, 2012. A revised and extended version is available online at: http://arxiv.org/abs/1201.2715.
19. R. Subramanian and I. Scherson. An analysis of diffusive load-balancing. In SPAA, pages 220--225, 1994.
20. T. Shiraga, Y. Yamauchi, S. Kijimam, and M. Yamashita. Deterministic Random Walks for Rapidly Mixing Chains. arXiv:1311.3749, 2013.
21. P. Berenbrink, R. Klasing, A. Kosowski, F. Mallmann-Trenn, and P. Uznański. Improved Analysis of Deterministic Load-Balancing Schemes. arXiv:1404.4344, 2014.
22. V. Yanovski, I. Wagner, and A. Bruckstein. A Distributed Ant Algorithm for Efficiently Patrolling a Network Algorithmica, 37(3):165--186, 2003.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

• Theory of computation

  • Design and analysis of algorithms