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
e
in a graph of m edges, during any interval of length t , this time-averaged value is k/m ± o(1/t
),
e
whenever gcd(m, k) = 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 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
e
problem in networks. our results immediately imply a bound of o(m/k)
on the idleness of the studied
e
process, showing that it is a distributed 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.