Rabani Y, Sinclair A, Wanka R (1998)
Publication Language: English
Publication Type: Conference contribution
Publication year: 1998
Pages Range: 694-703
Conference Proceedings Title: Proc. 39th IEEE Symposium on Foundations of Computer Science (FOCS)
Event location: San Francisco, USA
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.
APA:
Rabani, Y., Sinclair, A., & Wanka, R. (1998). Local Divergence of Markov Chains and the Analysis of Iterative Load-Balancing Schemes. In Proc. 39th IEEE Symposium on Foundations of Computer Science (FOCS) (pp. 694-703). San Francisco, USA.
MLA:
Rabani, Yuval, Alistair Sinclair, and Rolf Wanka. "Local Divergence of Markov Chains and the Analysis of Iterative Load-Balancing Schemes." Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), San Francisco, USA 1998. 694-703.
BibTeX: Download