Computer Science – Data Structures and Algorithms
Scientific paper
2010-06-16
Computer Science
Data Structures and Algorithms
24 pages, extended version of a conference paper which appeared in the Proceedings of 21st ACM-SIAM Symposium on Discrete Algo
Scientific paper
We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a random algorithm by keeping the accumulated rounding errors as small as possible. Our new algorithm surprisingly closely approximates the idealized process (where the tokens are divisible) on important network topologies. On d-dimensional torus graphs with n nodes it deviates from the idealized process only by an additive constant. In contrast to that, the randomized rounding approach of Friedrich and Sauerwald (2009) can deviate up to Omega(polylog(n)) and the deterministic algorithm of Rabani, Sinclair and Wanka (1998) has a deviation of Omega(n^{1/d}). This makes our quasirandom algorithm the first known algorithm for this setting which is optimal both in time and achieved smoothness. We further show that also on the hypercube our algorithm has a smaller deviation from the idealized process than the previous algorithms.
Friedrich Tobias
Gairing Martin
Sauerwald Thomas
No associations
LandOfFree
Quasirandom Load Balancing 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 Quasirandom Load Balancing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quasirandom Load Balancing will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-101254