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

Beitrag bei einer Tagung


Details zur Publikation

Autorinnen und Autoren: Rabani Y, Sinclair A, Wanka R
Jahr der Veröffentlichung: 1998
Tagungsband: Proc. 39th IEEE Symposium on Foundations of Computer Science (FOCS)
Seitenbereich: 694-703
Sprache: Englisch


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-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

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


Zitierweisen

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: 

Zuletzt aktualisiert 2018-20-10 um 13:40