Approximate load balancing on dynamic and asynchronous networks


Journal Article

© 1993 ACM. 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.

Full Text

Duke Authors

Cited Authors

  • Aiello, W; Awerbuch, B; Zkfaggs, B; Rao, S

Published Date

  • June 1, 1993

Published In

Volume / Issue

  • Part F129585 /

Start / End Page

  • 632 - 641

International Standard Serial Number (ISSN)

  • 0737-8017

Digital Object Identifier (DOI)

  • 10.1145/167088.167250

Citation Source

  • Scopus