Ergodic Effects in Token Circulation

Abstract : We consider a dynamical process in a network which distributes all particles (tokens) located at a node among its neighbors, in a round-robin manner. We show that in the recurrent state of this dynamics (i.e., disregarding a polynomially long initialization phase of the system), the number of particles located on a given edge, averaged over an interval of time, is tightly concentrated around the average particle density in the system. Formally, for a system of $k$ particles in a graph of $m$ edges, during any interval of length $T$, this time-averaged value is $k/m \pm \widetilde O(1/T)$, whenever $gcd(m,k) = \widetilde O(1)$ (and so, e.g., whenever $m$ is a prime number). To achieve these bounds, we link the behavior of the studied dynamics to ergodic properties of traversals based on Eulerian circuits on a symmetric directed graph. These results are proved through sum set methods and are likely to be of independent interest. As a corollary, we also obtain bounds on the \emph{idleness} of the studied dynamics, i.e., on the longest possible time between two consecutive appearances of a token on an edge, taken over all edges. Designing trajectories for $k$ tokens in a way which minimizes idleness is fundamental to the study of the patrolling problem in networks. Our results immediately imply a bound of $\widetilde O(m/k)$ on the idleness of the studied process, showing that it is a distributed $\widetilde O(1)$-competitive solution to the patrolling task, for all of the covered cases. Our work also provides some further insights that may be interesting in load-balancing applications.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01963249
Contributor : Adrian Kosowski <>
Submitted on : Friday, December 21, 2018 - 11:30:40 AM
Last modification on : Wednesday, October 2, 2019 - 5:30:22 PM
Long-term archiving on : Friday, March 22, 2019 - 2:01:22 PM

Identifiers

  • HAL Id : hal-01963249, version 1

Collections

Citation

Adrian Kosowski, Przemysław Uznanski. Ergodic Effects in Token Circulation. SODA '18 - Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States. pp.2668-2682. ⟨hal-01963249⟩

Share

Metrics

Record views

66

Files downloads

134