Local Divergence of Markov Chains and the Analysis of Iterative Load-Balancing Schemes
(Preliminary version)
Yuval Rabani
Computer Science Department
Technion
Haifa 32000, Israel
email: rabani@cs.technion.ac.ilAlistair Sinclair
Computer Science Division
University of California
Berkeley, CA 94720-1776
email: sinclair@cs.berkeley.edu
Rolf Wanka
Heinz Nixdorf Institute and
Dept. of Mathematics & Computer Science
Paderborn University
33095 Paderborn, Germany
email: wanka@uni-paderborn.de
Abstract
We develop a general technique for the quantitative analysis of iterative distributed load balancing schemes. We illustrate the technique by studying two simple, intuitively appealing models that are prevalent in the literature: the diffusive paradigm, and periodic balancing circuits (or the dimension exchange paradigm). It is well known that such load balancing schemes can be roughly modeled by Markov chains, but also that this approximation can be quite inaccurate. Our main contribution is an effective way of characterizing the deviation between the actual loads and the distribution generated by a related Markov chain, in terms of a natural quantity which we call the local divergence. We apply this technique to obtain bounds on the number of rounds required to achieve coarse balancing in general networks, cycles and meshes in these models. For balancing circuits, we also present bounds for the stronger requirement of perfect balancing, or counting.
Paper in compressed Postscript format (gzip used):
A4 format US letter format Published in the Proceedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS); pp. 694-703, 1998.
© Copyright 1998 IEEE. Published in the Proceedings of FOCS '98, 8-11 November 1998 in Palo Alto, CA. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works, must be obtained from the IEEE. Contact: Manager, Copyrights and Permissions / IEEE Service Center / 445 Hoes Lane / P.O. Box 1331 / Piscataway, NJ 08855-1331, USA. Telephone: + Intl. 732-562-3966.