Ergodic Effects in Token Circulation - Archive ouverte HAL Access content directly
Conference Papers Year : 2018

Ergodic Effects in Token Circulation


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.
Fichier principal
Vignette du fichier
arxiv.pdf (305.6 Ko) Télécharger le fichier
dwucykl.pdf (4.3 Ko) Télécharger le fichier
freq1.pdf (6.28 Ko) Télécharger le fichier
freq5.pdf (6.52 Ko) Télécharger le fichier
skierowany_dwucykl.pdf (4.97 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Origin : Files produced by the author(s)

Dates and versions

hal-01963249 , version 1 (21-12-2018)


  • HAL Id : hal-01963249 , version 1


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⟩
40 View
56 Download


Gmail Facebook Twitter LinkedIn More