Energy Initiative Energy Initiative
Office of the Provost
Duke University

 HOME > Provost > Energy Initiative    Search Help Login pdf version printable version 

Publications [#236683] of Bruce Maggs

Journal articles or Book chapters PUBLISHED

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


Duke University * Faculty * Staff * Reload * Login