Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies

Details Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies

2012-01-13

arxiv.org/abs/1201.2715v2

Computer Science

Discrete Mathematics

61 pages, 4 figures

Scientific paper

We consider the problem of balancing load items (tokens) on networks. Starting with an arbitrary load distribution, we allow in each round nodes to exchange tokens with their neighbors. The goal is to achieve a distribution where all nodes have nearly the same number of tokens. For the continuous case where tokens are arbitrarily divisible, most load balancing schemes correspond to Markov chains whose convergence is fairly well-understood in terms of their spectral gap. However, in many applications load items cannot be divided arbitrarily and we need to deal with the discrete case where the load is composed of indivisible tokens. This discretization entails a non-linear behavior due to its rounding errors, which makes the analysis much harder than in the continuous case. Therefore, it has been a major open problem to understand the limitations of discrete load balancing and its relation to the continuous case. We investigate several randomized protocols for different communication models in the discrete case. Our results demonstrate that there is almost no difference between the discrete and continuous case. For instance, for any regular network in the matching model, all nodes have the same load up to an additive constant in (asymptotically) the same number of rounds required in the continuous case. This generalizes and tightens the previous best result, which only holds for expander graphs (STOC'09).

Affiliated with

Also associated with

No associations

Rating

Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-468205