Discrepancy Analysis of a New Randomized Diffusion Algorithm for Weighted Round Matrices.

For an arbitrary initial configuration of indivisible loads over vertices ofa distributed network, we consider the problem of minimizing the discrepancybetween the maximum and minimum load among all vertices. For this problem,diffusion-based algorithms are well studied because of its simplicity. Thispaper presents a new randomized diffusion-based algorithm inspired by multiplerandom walks. In our algorithm, at each vertex, each token $k$ ($k\in\{0,1,\ldots, X-1\}$) generate a random number in $[k/X, (k+1)/X)$, and movesto a vertex corresponding to the given probability distribution. Our algorithmis adaptive to any transition transition probabilities while almost allprevious works are concerned with uniform transition probabilities. For thisalgorithm, we analyze the discrepancy between the token configuration and itsexpected value, and give an upper bound depending on the local 2-divergence ofthe transition matrix and $\sqrt{\log n}$, where $n$ is the number of vertices.The local 2-divergence is a measure which often appeared in previous works. Wealso give an upper bound of the local-2 divergence for any reversible and lazytransition matrix. These yield the following specific results. First, ouralgorithm achieves $O(\sqrt{d \log n})$ discrepancy for any $d$ regular graph,which matches the best result on previous works of diffusion model. Note thatour algorithm does not need any assumption of the number of tokens such asnegative loads which are often assumed in previous works. Second, for generalgraphs with maximum degree $d_{\max}$, our algorithm achieves $O(\sqrt{d_{\max} \log n})$ discrepancy using the transition matrix based on themetropolis hasting algorithm. Note that this algorithm does not needinformation of $d_{\max}$ while almost all previous works use it.