Local Divergence of Markov Chains and the Analysis of Iterative Load-Balancing Schemes

Conference contribution


Publication Details

Author(s): Rabani Y, Sinclair A, Wanka R
Publication year: 1998
Conference Proceedings Title: Proc. 39th IEEE Symposium on Foundations of Computer Science (FOCS)
Pages range: 694-703
Language: English


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.



 



FAU Authors / FAU Editors

Wanka, Rolf Prof. Dr.
Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)


How to cite

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: 

Last updated on 2018-20-10 at 13:40