| Publications [#236683] of Bruce Maggs
Journal articles or Book chapters PUBLISHED
- Aiello, W; Awerbuch, B; Zkfaggs, B; Rao, S, Approximate load balancing on dynamic and asynchronous networks,
Proceedings of the Annual ACM Symposium on Theory of Computing, vol. Part F129585
(June, 1993),
pp. 632-641 [doi]
(last updated on 2024/03/28)
Abstract: 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 networic 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 μ-expander, the algorithm will balance the load to within an additive 0(d log n/fi) term in 0(Δ log(nΔ)//μ) time, where A is the initial imbalance. The algorithm improves upon previous approaches that yield 0(n) time bounds in dynamic and asynchronous networks.
|