Dynamic Averaging on Regular Graphs

Abstract

We study a dynamic averaging process on finite regular graphs with bounded, time-varying load arrivals. At each discrete time $t$, an edge is chosen uniformly at random, a load $0\le w_t\le 1$ is introduced, and the total load of its two endpoints together with $w_t$ is divided equally between them. Starting from the flat configuration, we obtain a pairwise concentration bound governed by the effective resistance between vertices and use generic chaining to derive a general upper bound on the expected gap between the largest and smallest loads. As a consequence, we show that every $d$-regular graph has expected gap $O_d(\sqrt{n})$, uniformly in time and over all deterministic arrival sequences. Applying our general bound to the discrete two-dimensional torus yields the sharp $O(\log n)$ upper bound, improving the best previously known bound. For the cycle, whenever the arriving loads are bounded away from zero, we prove that the expected gap is $\hat{I}\text{c◯}(\sqrt{n})$ for all sufficiently large times. Together with our upper bound, this confirms the conjecture of Alistarh, Nadiradze, and Sabour that the expected gap on the cycle is of order $\sqrt{n}$.