- 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.

**Back to other
publications**

**Back to my home page**