Approximate load balancing on dynamic and asynchronous networks
William A. Aiello, Baruch Awerbuch, Bruce MacDowell Maggs, Satish B. Rao · 1993
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, forma p-expander, the algorithm will balance the load to within an additive O(d log n/p) term in O(A log(nA)/p) time, where A is the initial imbalance.The algorithm improves upon previous approaches that yield O(n) time bounds in dynamic and asynchronous networks.