- Tight analyses of two local load balancing
algorithms. B. Ghosh, F. T. Leighton, B. M. Maggs, S.
Muthukrishnan, C. G. Plaxton, R. Rajaraman, A. W. Richa, R. E.
Tarjan, and D. Zuckerman, Proceedings of the 27th Annual ACM
Symposium on the Theory of Computing (STOC), May 1995, pp. 548-558.

- This paper presents an analysis of the following load balancing
algorithm. At each step, each node in a network examines the number
of tokens at each of its neighbors and sends a token to each neighbor
with at least $2d+1$ fewer tokens, where $d$ is the maximum degree of
any node in the network. We show that within $O(\Delta / \alpha)$
steps, the algorithm reduces the maximum difference in tokens between
any two nodes to at most $O((d^2 \log n)/\alpha)$, where $\Delta$ is
the maximum difference between the number tokens at any node initially
and the average number of tokens, $n$ is the number of nodes in the
network, and $\alpha$ is the edge expansion of the network. The time
bound is tight in the sense that for any graph with edge expansion
$\alpha$, and for any value $\Delta$, there exists an initial
distribution of tokens with imbalance $\Delta$ for which the time to
reduce the imbalance to even $\Delta/2$ is at least
$\Omega(\Delta/\alpha)$. The bound on the final imbalance is tight in
the sense that there exists a class of networks that can be locally
balanced everywhere (i.e., the maximum difference in tokens between
any two neighbors is at most $2d$), while the global imbalance
remains $\Omega((d^2 \log n) / \alpha)$. Furthermore, we show that
upon reaching a state with a global imbalance of $O((d^2
\log n)/\alpha)$, the time for this algorithm to locally balance the
network can be as large as $\Omega(n^{1/2})$. We extend our analysis to a
variant of this algorithm for dynamic and asynchronous networks. We
also present tight bounds for a randomized algorithm in which each node
sends at most one token in each step.

**Back to other
publications**

**Back to my home page**