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

  This paper presents a simple local algorithm for load balancing in a distributed network. The algorithm makes no assumption about the structure of the network. It can be executed on a synchronous network with fixed topology, a synchronous network with dynamically changing topology, or an asynchronous network. It works quickly and balances well when the network has an expansion property. In particular, we show that in an n-node network with maximum degree d whose live edges, at every time step, form a mu-expander, the algorithm will balance to within an additive O(d log n/mu) term in O((Delta log(nDelta))/mu) time, where Delta is the initial imbalance. The algorithm improves on previous approaches that yield O(n) time bounds in dynamic and asynchronous networks.

  Postscript Compressed Postscript
  Back to other publications

  Back to my home page