Skip to main content
SpringerLink
Log in

On the Stability of Dynamic Diffusion Load Balancing

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We consider the problem of dynamic load balancing in arbitrary (connected) networks on n nodes. Our load generation model is such that during each round, n tasks are generated on arbitrary nodes, and then (possibly after some balancing) one task is deleted from every non-empty node. Notice that this model fully saturates the resources of the network in the sense that we generate just as many new tasks per round as the network is able to delete. We show that even in this situation the system is stable, in that the total load remains bounded (as a function of n alone) over time. Our proof only requires that the underlying “communication” graph be connected. (It of course also works if we generate less than n new tasks per round, but the major contribution of this paper is the fully saturated case.) We further show that the upper bound we obtain is asymptotically tight (up to a moderate multiplicative constant) by demonstrating a corresponding lower bound on the system load for the particular example of a linear array (or path). We also show some simple negative results (i.e., instability) for work-stealing based diffusion-type algorithms in this setting.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aiello, W., Awerbuch, B., Maggs, B., Rao, S.: Approximate load balancing on dynamic and asynchronous networks. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC 1993), pp. 632–641 (1993)

  2. Aiello, W., Kushilevitz, E., Ostrovsky, R., Rosen, A.: Adaptive packet routing for bursty adversarial traffic. J. Comput. Syst. Sci. 60, 482–509 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  3. Anagnostopoulos, A., Kirsch, A., Upfal, E.: Stability and efficiency of a random local load balancing protocol. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), pp. 472–481 (2003)

  4. Anshelevich, E., Kempe, D., Kleinberg, J.: Stability of load balancing algorithms in dynamic adversarial systems. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 399–406 (2002)

  5. Awerbuch, B., Berenbrink, P., Brinkmann, A., Scheideler, C.: Simple routing strategies for adversarial systems. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 158–167 (2001)

  6. Awerbuch, B., Leighton, T.: A simple local control algorithm for multi-commodity flow. In: Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 459–468 (1993)

  7. Awerbuch, B., Leighton, T.: Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pp. 487–496 (1994)

  8. Berenbrink, P., Friedetzky, T., Goldberg, L.A.: The natural work-stealing algorithm is stable. SIAM J. Comput. 32, 1260–1279 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  9. Berenbrink, P., Friedetzky, T., Mayr, E.W.: Parallel continuous randomized load balancing. In: Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA’98), pp.192–201 (1998)

  10. Boillat, J.E.: Load balancing and Poisson equation in a graph. Concurr. Pract. Exp. 2, 289–313 (1990)

    Article  Google Scholar 

  11. Cybenko, G.: Dynamic load balancing for distributed memory multiprocessors. J. Parallel Distrib. Comput. 7, 279–301 (1989)

    Article  Google Scholar 

  12. Diekmann, R., Frommer, A., Monien, B.: Efficient schemes for nearest neighbor load balancing. J. Parallel Comput. 25, 789–812 (1999)

    Article  MathSciNet  Google Scholar 

  13. Elsässer, R., Monien, B.: Load balancing of unit size tokens and expansion properties of graphs. In: Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 266–273 (2003)

  14. Elsässer, R., Monien, B., Preis, R.: Diffusion schemes for load balancing on heterogeneous networks. Theory Comput. Syst. 35, 305–320 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  15. Ghosh, B., Leighton, F.T., Maggs, B.M., Muthukrishnan, S., Plaxton, C.G., Rajaraman, R., Richa, A.W., Tarjan, R.E., Zuckerman, D.: Tight analyses of two local load balancing algorithms. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pp. 548–558 (1995)

  16. Ghosh, B., Muthukrishnan, S.: Dynamic load balancing by random matchings. J. Comput. Syst. Sci. 53, 357–370 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  17. auf der Heide, F.M., Oesterdiekhoff, B., Wanka, R.: Strongly adaptive token distribution. Algorithmica 15, 413–427 (1996)

    MathSciNet  MATH  Google Scholar 

  18. auf der Heide, F.M., Scheideler, C., Stemann, V.: Exploiting storage redundancy to speed up randomized shared memory simulations. Theor. Comput. Sci. 162, 245–281 (1996)

    Article  MATH  Google Scholar 

  19. Muthukrishnan, S., Ghosh, B., Schultz, M.H.: First- and second-order diffusive methods for rapid, coarse, distributed load balancing. Theory Comput. Syst. 31, 331–354 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  20. Muthukrishnan, S., Rajaraman, R.: An adversarial model for distributed load balancing. In: Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 47–54 (1998)

  21. Peleg, D., Upfal, E.: The token distribution problem. SIAM J. Comput. 18, 229–243 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  22. Rabani, Y., Sinclair, A., Wanka, R.: Local divergence of Markov chains and the analysis of iterative load-balancing schemes. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 694–703 (1998)

Download references

Author information

Authors and Affiliations

  1. School of Computing Science, Simon Fraser University, Burnaby, Canada

    Petra Berenbrink

  2. Department of Computer Science, University of Durham, Durham, DH1 3LE, UK

    Tom Friedetzky

  3. Department of Computer Science, University of Liverpool, Liverpool, UK

    Russell Martin

Authors
  1. Petra Berenbrink
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tom Friedetzky
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Russell Martin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tom Friedetzky.

Additional information

A preliminary version of this paper entitled “Dynamic diffusion load balancing” was published in Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP’05), Lecture Notes in Computer Science 3580, Springer-Verlag, pp. 1386–1398.

P. Berenbrink is supported by NSERC Discovery Grant 250284-2002.

R. Martin is supported by EPSRC grant “Discontinuous Behaviour in the Complexity of Randomized Algorithms.”

Rights and permissions

Reprints and permissions

About this article

Cite this article

Berenbrink, P., Friedetzky, T. & Martin, R. On the Stability of Dynamic Diffusion Load Balancing. Algorithmica 50, 329–350 (2008). https://doi.org/10.1007/s00453-007-9081-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-007-9081-y

Keywords

Search

Navigation