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

Abstract We develop a general technique for the quantitative analy-sis of iterative distributed load balancing schemes. We illustrate the technique by studying two simple, intuitivelyappealing models that are prevalent in the literature: the diffusive paradigm, and periodic balancing circuits (or thedimension exchange paradigm). It is well known that such load balancing schemes can be roughly modeled by Markovchains, but also that this approximation can be quite inaccurate. Our main contribution is an effective way of char-acterizing the deviation between the actual loads and the distribution generated by a related Markov chain, in termsof a natural quantity which we call the local divergence. We apply this technique to obtain bounds on the number ofrounds required to achieve coarse balancing in general networks, cycles and meshes in these models. For balancingcircuits, we also present bounds for the stronger requirement of perfect balancing, or counting