*For the most recent entries see the
Petri Nets Newsletter.*

## Rapid Convergence of a Local Load Balancing Algorithm for Asynchronous Rings.

Gehrke, J.E.;
Plaxton, C.G.;
Rajaraman, R.
In:
Mavronicolas, M.; Tsigas, Ph.: *Lecture Notes in Computer Science, Vol. 1320: Distributed Algorithms, Proc. of 11th International Workshop, WDAG'97, Saarbrücken, Germany*, pages 81-95.
Springer,
September 1997.

Abstract:
We consider the problem of load balancing in a ring network. We present an
analysis of the following local algorithm. In each step, each node of the
ring examines the number of tokens at its clockwise neighbor and sends a
token to the neighbor if the neighbor has fewer tokens. We show that in a
synchronous model, for any initial token distribution b, the algorithm
converges to a completely balanced distribution within 4OPT(b)+n steps,
where OPT(b) is the time taken by the optimal centralized algorithm to
balance b completely. Our main result is an analysis of the algorithm in
an asynchronous model in which local computations and messages may be
arbitrarily delayed, subject to the constraint that each message is
eventually delivered and each computation is eventually performed. By
generalizing our analysis for the synchronous model, we show that for any
initial token distribution b, the algorithm converges to a completely
balanced distribution with 8 OPT(b)+2n rounds, where a round is a minimal
sequence of steps in which every component of the network is scheduled at
least once. We also show that for every initial token distribution, the
message complexity of the algorithm is asymptotically optimal among all
algorithms that move tokens in the clockwise direction.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*