Ergodic Effects in Token Circulation
Adrian Kosowski1 and Przemysław Uznański2
1

arXiv:1612.09145v3 [cs.DS] 3 Nov 2017

2

Inria Paris and IRIF, Université Paris Diderot, France
Department of Computer Science, ETH Zürich, Switzerland

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.

1

Introduction

The notion of ergodicity captures the characteristic of a dynamical system which displays averaging behavior
in both its state space and in time. For example, a finite Markov chain is ergodic if it is both aperiodic and
irreducible, that is, for any sufficiently large integer t, it has positive probability to go between any pair
of states in exactly t steps. In this work, we focus on systems consisting of multiple particles (or tokens)
moving around sites in a finite graph. In such a setting, an important manifestation of ergodicity is the
property of time-averaging: a measurement performed at a fixed location in the system over a period of time
is representative of the averaged behavior of the system, for any site or location.
As an example, consider a system of k non-interacting random walk particles on a connected non-bipartite
symmetric directed graph, moving around the graph in synchronous steps. A direct consequence of the
ergodicity of this system is that, in the limit, any multiset of k arcs has the same probability of being traversed
by the k walks in any given step. The slightly weaker property of time-averaging for this system is phrased as
follows: if the graph has m arcs, then for any given arc, the average number of particles traversing this arc
tends to k/m per step, when averaging over sufficiently long time intervals. However, when the number of
1

particles k in the system is small, the length of the time window required to obtain a reliable time-averaged
measurement at any single measurement point becomes long: if we observe any given arc for Θ(m2 /k 2 )
consecutive steps, we have constant probability of not spotting any particle on the arc, even when the expected
number of particles passing through this arc during the considered time interval is Θ(m/k) (cf. e.g. [19, 28]
for related analyses and more general considerations of parallel random walks).
In this paper, we investigate a way to obtain faster time-averaging behavior in a system with k particles,
and look at the algorithmic consequences of such a property. We study the fundamental deterministic process
of particle propagation in which k tokens circulate in a symmetric directed graph, with each node propagating
all the tokens it contains to its neighbors by a round-robin mechanism (RR dynamics), in each synchronous
round. This process is closely related to (and in fact, a variant of) chip-firing games in the sandpile model
(see Section 1.1 for more details), but has the advantage that it displays meaningful behavior even in the
regime of a very small number of tokens. At the same time, it bears numerous similarities to the model of
non-interacting parallel random walks. These similarities have been studied and exhibited in contexts ranging
from parallel cover time [15, 28, 29] to load-balancing properties [3, 8, 16, 29, 36].
As our main result, we show that under the assumption of co-prime values of m and k, the RR dynamics
in its recurrent state displays very fast time-averaging on arcs: in a time interval of length T , the number
e
of tokens passing through any arc is always in the range kT /m ± O(1),
i.e., the average number of tokens
e
e
observed per step during the interval is k/m ± O(1/T ), where the O notation hides poly-logarithmic factors
e
in m. In particular, in the studied scenario, each arc is visited by a token at least once in O(m/k)
steps.
This effect of quasi-regular traversal of arcs in the RR dynamics’ recurrent state is only observed when the
considered graph is symmetric. To prove its existence, we build on links between the RR dynamics and
the structure of Eulerian circuits in the graph. Our main contribution is to define and analyze a process of
moving around the nodes of a graph in time, by performing traversals of fragments (contiguous sequences
of arcs) of a given Eulerian circuit, and occasionally switching between different fragments of the circuit
which meet at the same vertex. Such a process is shown to have the property that any pair of temporally
e
and spatially separated states can be reached from one another within at most Θ(1)
operations of switching
between fragments of the Eulerian circuit. The latter result is obtained by proving, in a framework of additive
combinatorics, that iterated sums of the set of lengths of closed sub-circuits of any Eulerian circuit grow
rapidly, covering the set of all integers in a small number of iterations.
The rest of the paper is organized as follows. We continue the introduction by describing the context of
the RR dynamics in Section 1.1, and some applications of our results in Section 1.2. We then provide an
exposition of the technical results in Section 2. The remaining sections are devoted to a proof of the results,
starting with an exposition of the main structural lemmas on mixing properties of circulations in Section 3
and 4. We relate these results to RR dynamics in Section 5.

1.1

Overview of RR Dynamics

The RR dynamics, variously referred to as the round-robin mechanism, the rotor-router, the Eulerian walker
model, the ant walk model, or the Propp machine, describes a deterministic token propagation mechanism
on a (symmetric) directed graph.1 In each step, the state of the system is represented by the locations of
the k tokens on nodes of the graph, and a pointer for each node, indicating one outgoing arc. In discrete,
synchronous steps, all tokens are propagated according to the deterministic round robin rule, where after
sending out each token, the node sending the token advances its pointer to the next outgoing arc in some fixed
cyclic ordering of its out-neighborhood.
1

A process defined on a symmetric directed graph may also be considered as running on the corresponding undirected graph. We
consider the symmetric directed variant for an easier discussion of (Eulerian) circuits.

2

The RR dynamics was first considered in [32] and is a close cousin of the dynamics of sandpiles. The
latter model was introduced 30 years ago in the seminal work [6] (cf. e.g. [34] for an overview of its
algorithmic properties) and gave rise to the notion of self-organized criticality (SOC) — a concept since
applied in dozens of fields, ranging from Earth sciences to neurobiology, to model systems whose evolution
occurs close to a critical point. Whereas sandpile dynamics were the first synthetic physical system recognized
to display SOC behavior, the RR dynamics has been shown to exhibit comparable effects, visible for instance
in the almost identical long-distance correlation patterns of the two processes on the grid, cf. e.g. [14, 32]. In
the large-k regime, the RR system and the synchronous sandpile model (with chip-firing rules [9, 27]) are
comparable in many other respects. For instance, in a network load-balancing context, they both belong to a
class of processes with a highly desirable property of cumulative load balancing over arcs outgoing from
each node [8, 12, 16]. In the small-k regime, the RR dynamics has been studied in the context of its limit
behavior and has often been compared to parallel random walk processes, e.g., in terms of its cover time on
graphs [1, 15, 20, 23, 29, 39].
The RR dynamics, like any other finite deterministic system, exhibits an initial transient phase, after
which it stabilizes to a cyclic traversal of a set of recurrent states. For k = 1 token, multiple authors have
observed that on symmetric graphs, the dynamics stabilizes in a polynomial number of steps to a traversal
of an Eulerian circuit [1, 32, 39] (for the non-symmetric and infinite settings, see e.g. [26]). The underlying
link between the RR dynamics and Eulerian circuits is also displayed by the relation between the number of
possible states of the system and the number of Eulerian circuits in the graph, as given by the BEST theorem
(cf. e.g. [7] for further discussion). For k > 1, a structural characterization of the limit behavior of RR for
an arbitrary number k > 1 of tokens was shown in [10]. The obtained characterization shows that the RR
process provides a way of organizing tokens into balanced subsets, each of which follows a well-defined walk
in some closed circuit on a subset of arcs of the graph. When the graph is not symmetric, such token subsets
may be arbitrary and display little regularity: for example, on a one-directional cycle in which each node has
out-degree 1, a group of k tokens may perform a cyclic traversal of the graph while always located on the
same node. Herein we show how, and (plausibly) why, in any symmetric directed graph the RR dynamics will
(under almost all parameter configurations) self-organize into recurrent states with an arrangement of tokens
in which distances between tokens on their respective circuits are almost uniform.

1.2

Motivation and Consequences of Results

In Section 2 we provide a formal exposition of the obtained structural results for Eulerian circuits, and their
consequences for the RR model. Before we do this, we present here two examples of concrete scenarios in
which the results of this paper find direct application. The first concerns the deployment of the RR process in
the task of regularly patrolling network edges, while the second makes use of the RR rules to balance load in
a network fairly over periods of time. We remark that for neither of these tasks were decentralized solutions
of comparable quality previously known, whether deterministic or randomized. In particular, as discussed
further, the application of random-walk-based techniques fails completely for both tasks.
1.2.1

Network Patrolling

The term patrolling refers to an act of surveillance, which involves walking perpetually around an area in
order to protect or supervise it. It is a convenient description of numerous settings, such as locating objects
or humans that need to be rescued from a disaster, ecological monitoring, or intrusion detection. Network
administrators may patrol network nodes and links to detect network failures or to discover web pages which
need to be indexed by search engines, cf. [30]. Patrolling has been recently intensively studied in robotics
(cf. [5,11,17,18,25,30,39]) where it is often viewed as a version of terrain coverage, a central task in robotics.
3

Scenarios for RR dynamics

Patrolling competitive ratio

Cumulated load discrepancy

Reference

small gcd(k, m):

e
O(gcd(k,
m))

e
O(gcd(k,
m))

Pro. 5.14, 5.12

large k:
small k:
small diam:
small n:
tree topology:

3
O(1),
√ for k ≥ 4 m
e k)
O(
O(diam)
e √n)
O(
O(1), for trees

−
−
O(diam)
e √n)
O(
−

Pro.
Pro.
Pro.
Pro.
Pro.

5.14
5.14
5.14, 5.12
5.14, 5.12
5.14

Comparison of strategies (for m prime)
RR dynamics:

e
O(1)

k parallel random walks
or randomized rounding [22]:

Ω(m/k)
(also in expected sense)

e
O(1)
√
Ω( T ) in expectation
(i.e., unbounded)

Table 1: Summary of obtained performance bounds on RR dynamics. The underlying graph is assumed to be
symmetric directed, on n nodes, m arcs, diameter diam, and with k tokens. The cumulated load discrepancy
presented in the table holds eventually over any time interval, of arbitrary length T .
Patrolling boundaries of terrains and their area have been studied in [2, 17, 18, 31] with approaches placing
more emphasis on experimental results.
The accepted measure of the algorithmic efficiency of patrolling is called idleness or refresh time and
describes the frequency with which the points of the environment are visited (cf. [5, 11, 17, 18, 30, 31]); this
criterion was first introduced in [30]. Depending on the requirements, the idleness may sometimes be viewed
as the average ( [17]), worst-case ( [7, 39]), probabilistic ( [2]) or experimentally verified ( [30]) time elapsed
since the last visit to a node or edge (cf. also [5, 11]). A survey of diverse approaches to patrolling based on
idleness criteria can be found in [5], whereas a theoretical analysis of approaches to patrolling in graph-based
models can be found in [11].
Contribution: In the standard edge-patrolling setting on graphs, the asymptotically optimal value of
(worst-case) idleness which can be achieved using a team of k agents on a graph with m edges is Θ(m/k).
This is achieved, e.g., by deploying k agents in a centralized manner with equal spacing, traversing a
predefined Eulerian circuit in the graph (cf. e.g. [11]). We show that the RR dynamics provides a completely
decentralized (and self-organized) solution to the edge-patrolling problem on graphs, achieving idleness of
e
Θ(m/k)
in a wide variety of settings, in particular, when gcd(k, m) = 1, as well as for trees. (We remark
that some empirical studies of patrolling of trees with the RR process in trees were provided in [13], without
theoretical analysis.) In Table 1 we present the obtained results on the patrolling competitive ratio of the RR
process, i.e., the achieved value of the idleness divided by the optimal Θ(m/k) idleness of the centralized
process. To the best of our knowledge, designing a decentralized patrolling strategy with small idleness was a
relevant open question in the area, and the RR approach may prove to be a viable practical approach. As
pointed out in the discussion of time-averaging processes at the beginning of the paper, even when considering
probabilistic measures of idleness and when the considered graph is a cycle, a team of parallel random walks
achieve an idleness of Ω(m2 /k 2 ), which corresponds to a competitive ratio of Ω(m/k).

4

1.2.2

Load Balancing

Process in which nodes exchange tokens have also been extensively studied from the perspective of load
balancing, where one sees the number of tokens at a node as its load, and aims at minimizing the discrepancy,
i.e., the difference between the maximal and minimal load of a pair of nodes of a network.
Many distributed load balancing processes are inspired by continuous dynamics from nature. For example,
the heat equation, which describes real-world processes such as heat and particle diffusion, can also be used
to model the following continuous load balancing process, assuming arbitrarily divisible load instead of
indivisible tokens. Each node with load x(u) sends to each of its d neighbours load x(u)/(d + 1), and keeps
x(u)/(d + 1) load to itself. In such diffusive load balancing, it is well known that loads in d-regular graphs
will eventually become perfectly balanced [37]. However, such balancing might be impossible to achieve in a
discrete setting, and in general it is impossible to simulate a continuous process in a discrete one. Discrete
load balancing schemes, which in principle deal with integer-rounding issues in a continuous process, are
also in general much harder to analyze. In [33], a process that sends bx(u)/(d + 1)c or dx(u)/(d + 1)e
load over each edge is shown to achieve vertex discrepancy of O(d log n/µ) after O(log(Kn)/µ) steps for
d-regular graphs, where K is the initial load discrepancy and µ is the spectral gap of the transition matrix
of the underlying Markov chain. Since [33], many variants of discretization of diffusive process have been
proposed, see [4, 8, 21, 22, 35].
Contribution: This paper opens the ground for the analysis of a more fine-grained measure in discrete
load balancing, namely, balancing the load passing through a node, cumulated (summed) over intervals
of time. Thus, for an arbitrary fixed interval
of length T , rather than consider the load xt (u) of a node u
Pt+T
at time t, we look at the cumulated load τ =t −1 xτ (u), and bound the discrepancy of this value from its
average over all nodes of the graph. The existence of this measure was previously indicated in our work [8],
though we managed to obtain relatively weak bounds for a wider family of processes. Here, we show that
for the specific load balancing process governed by the RR process, the cumulated discrepancy is very low:
e
the cumulated load of every node is identical up to O(1)
when gcd(k, m) = 1 (see Table 1 for a detailed
overview of results). In other words, the total number of operations, such as storing a task, sending or
receiving a task from a neighbor, which are performed by every node, is fairly balanced over all nodes of
the network, counting over any window of time. Note that the cumulative load balancing problem cannot be
addressed using a random-walk-type approach: indeed, even a process propagating a single superfluous token
with a random walk among otherwise balanced nodes can cause significant discrepancy of cumulated load,
which eventually becomes unbounded. This is, in particular, the case for the elegant randomized rounding
approach of Friedrich and Sauerwald [22], which is extremely efficient at bounding load differences at any
fixed moment of time, but which allows the differences
√ of cumulated load of nodes over a time interval of
length T to increase (in expectation) proportionally to T . (Such behavior is observed even on simple graph
topologies, such as the three-vertex cycle, since intuitively, the best guarantees for such a randomized process
follow directly from the law of large numbers. The guarantees we obtain for the RR dynamics have a more
subtle explanation which relies on combinatorial and number-theoretic properties. Other deterministic load
balancing processes known to us show no similar advantage for cumulated load balancing).
We note that our results provide insights for the behavior of the RR dynamics after it has stabilized, and
have no direct bearing on its initial stabilization phase.

5

2
2.1

Exposition of Technical Results
Notation

In this paper, we will consider graph G = (V, E) to be directed and symmetric, i.e., such that every arc
e = (u, v) has a corresponding opposite arc (v, u) =: −e. We denote |E| = m and |V | = n. We allow the
graph to have multi-arcs as well as self-loops, however, to extend our notation to loops, we say that a loop
is the opposite of itself, only (even if there are many loops in a single vertex). For an arc e = (u, v), we
denote u = pred(e) and v = succ(e). Unless otherwise stated, we will assume that G is not bipartite, to
avoid obvious issues with the periodicity of 2 in the dynamics on G.
We denote the set of integers by Z, the set of non-negative integers by Z+ , and the set of integers in
modulo-η arithmetic as Zη . For A, B ⊆ Zη their sumset is A + B := {(a + b) mod η : a ∈ A, b ∈ B}, and
for k ∈ Z+ , kA := A + . . . + A, with the sum spanning over k copies of A.

2.2

Eulerian Mixing in Time and Space

The main technical ingredients of this paper are linked to properties of traversals of Eulerian circuits, and,
more broadly, of circulations on symmetric directed graphs. We formulate them in this section in the most
intuitive form, in a way which is independent of the RR process.
We will call ϕ : E → E a (unit) circulation on the set of arcs of a symmetric directed graph (V, E) if ϕ
is a bijection on E such that for all arcs e ∈ E, succ(e) = pred(ϕ(e)).
For a pair of vertices u, v ∈ V and t ∈ Z+ , we will write u →t v if there exists an edge e with
pred(e) = u such that succ(ϕt (e)) = v, i.e., it is possible to reach v from u by following a t-step walk along
the circulation. We will also write v →−t u whenever u →t v, for t ∈ Z+ .
We will call ϕ Eulerian if the orbit of any arc is an Eulerian circuit on (V, E), i.e., for any e ∈ E, we
have {ϕt (e) : t ∈ Z} = E. In general, we will consider our circulation ϕ as a union of g ≥ 1 orbits (cycles),
denoted E1 , . . . , Eg , forming a partition of the arc set.
For a circulation ϕ on a graph G = (V, E), let Gϕ be the graph with vertex set V × Z and edge set
{{(u, tu ), (v, tv )} : u →(tv −tu ) v}. For the important case of Eulerian circulations, i.e., g = 1, the (simpler)
version of the main technical lemma of our paper may be stated as follows.
Lemma 2.1. Let ϕ be an Eulerian circulation on a non-bipartite symmetric directed graph G. Then, graph
Gϕ has diameter O(log2 n).
The assumption that the considered graph is symmetric cannot be omitted in the statement of Lemma 2.1;
an example of a non-symmetric graph for which Gϕ has larger diameter is presented in Fig. 1.
As a side remark, we note that the above Lemma has an intuitive interpretation in that it bounds the
distance between a pair of time-separated points (u, 0) and (u, l) by O(log2 n). We can thus write the
following informal corollary.
Corollary 2.2. For any fixed Eulerian circuit in a non-bipartite symmetric directed graph G and any l ∈ Zm ,
there exists a closed walk over the arcs of G of length congruent to l modulo m, constructed by a successive
traversal of O(log2 n) contiguous fragments of the given Eulerian circuit.
Note that the trajectory between nodes (u, 0) and (u, l) which follows from a shortest path in graph Gϕ
may contain “positive” traversals along iterated applications of ϕ, as well as “negative” traversals along
iterated applications of ϕ−1 . However, one can ensure that all arcs appear in the considered walk a nonnegative (or positive) number of times by augmenting it with a traversal of sufficiently large number of
iterations of the complete Eulerian circuit ϕm . This does not change the length of the walk, modulo m.
6

Figure 1: A non-symmetric directed graph for which Lemma 2.1 does not hold: the unique Eulerian circulation
ϕ covering G results in Gϕ that has diameter linear in n. If we consider a configuration of RR dynamics with
one token per each blue vertex, symmetrically on both sides, the configuration repeats every m/2 steps, and
no mixing occurs.
The proof of Lemma 2.3 relies on a characterization of the set of lengths of self-intersections of an
Eulerian circuit. Intuitively, t belongs to the set of self-intersections if there exists a closed walk u →t u along
the Eulerian circuit. In Section 3 we exploit the spectral properties of the set of self-intersections to show that
for given η, any value in Zη may be obtained as a sum of at most O(log2 η) lengths of self-intersections. The
discussion in the section is formulated in slightly more general notation, leading to Lemma 3.6, which will
also prove useful in the consideration of non-Eulerian circulations. The claim then follows readily (Section 4).
Extending considerations beyond Eulerian circulations, we obtain the following generalization of
Lemma 2.1 to the case of g > 1.
Lemma 2.3. Let ϕ be a unit circulation on a non-bipartite symmetric directed graph G. Then, Gϕ has
diameter at most O(g log2 n).
The proof of this lemma relies on the same ingredients (Section 3) as the considerations in the Eulerian
case, however, the sum set technique only provides us with a way of showing mixing in time when considering
time values modulo the greatest common divisor of the lengths of all cycles in the circulation. The general
result for arbitrary integer time values follows from an application of the Chinese Remainder Theorem
(Section 4).
The obtained bounds on the diameter of Gϕ are tight up to polylogarithmic factors, and we subsequently
apply them to the analysis of the RR model.
We close this section with the following side remark, which appears to be interesting in its own right but
has no bearing on the main results of the paper. It is possible to obtain a slightly stronger spectral property
of Gϕ for Eulerian ϕ than merely a polylogarithmic bound on the diameter. For any Eulerian circuit in G,
one can design a random process which will terminate at a well-mixed node in G at a well-mixed time, by
traversing a polylogarithmic number of fragments of the Eulerian circuit.
Corollary 2.4. Let ϕ be an Eulerian circulation on a non-bipartite symmetric directed graph (V, E). Then,
there exists an assignment of weights w : E(Gϕ ) → [0, 1], such that the reversible Markov chain following
e
(Gϕ , w) achieves good mixing on V × Zm starting from any vertex from this set, after O(1)
steps.
The proof follows from a straightforward adaptation of the spectral arguments used in our analysis in
Section 3.

2.3

RR Dynamics and Short-Time-Averaging

We start this section by formally defining the RR dynamics. Each vertex v of G is equipped with a fixed
ordering of all its outgoing arcs ρv = (e1 , e2 , . . . , edeg(v) ). A state x at the current time step t is a tuple:
7

xt = ((pointer v )v∈V , (L(v))v∈V ), where pointer v is an arc outgoing from node v, which is referred to as
the current port pointer at node v, and L(v) is the number of tokens at any given node. The state space of the
RR dynamics is denoted X, and its cardinality is in general readily seen to be (exponentially) larger than |V |.
The system is initialized to an arbitrary state of the state space X. For an arc (v, u), let next((v, u)) denote
the arc after the arc (v, u) in the cyclic order ρv . During each step, each node v distributes in round-robin
fashion all of its tokens, using the following algorithm:
While there is a token at node v, do:
1. Send the token to pointer v ,
2. Set pointer v = next(pointer v ).
Note that during a single time step all tokens at a node v are sent out and at exactly the next time step all
those tokens arrive at their respective destination nodes. The total number of tokens in graph is denoted as k.
When the system is in state x ∈ X, let (Lx (e) : e ∈ E) ∈ Zm
+ be the distribution vector of tokens over
arcs of the RR dynamics during its transition from state x to the subsequent state, i.e., let Lx (e) represent the
number of particles sent out along arc e ∈ E in the current time step, starting from state x.
Once the RR dynamics has entered a recurrent state, the trajectory followed by the dynamics involves
only a small fraction of its entire state space X, and as such, when viewed in high dimension, it is definitely
not an ergodic process. However, we show that it is possible to make use of the time-mixing property of
(almost) Eulerian circulations captured by Lemma 2.3 to show that RR achieves the sought time-averaging
behavior when considering only one-dimensional probe functions L(e). Intuitively, in the recurrent state of
the RR dynamics, individual tokens may be seen as traversing cycles of some unit circulation, with balancing
behavior occurring at the meeting points of different cycles in the circulation.
Theorem 2.5. For any e ∈ E and t0 , T ∈ Z+ , such that x(t0 ) is recurrent, the RR dynamics satisfies:


t0 +T
1 X
k
gcd(k, m)
e
L (e) =
±O
.
T t=t x(t)
m
T
0

The above Theorem, which we prove in Section 5 after introducing more background properties of the
RR process, has immediate consequences to problems of idleness in patrolling and cumulative load balancing.
This is also discussed in Section 5.

3

Sum-sets of Self-Intersections on a Circulation

Compared to the more high-level exposition in Section 2.2, in the subsequent analysis it is more convenient
to work with measures of distance between pairs of arcs rather than pairs of vertices. We thus introduce all
further notation based on the arc-based perspective.
Intersections: We will say that an assignment λ : E → Zη along the cycle (cycles) of circulation ϕ is a
η-labeling if the following condition is fulfilled: ∀e∈E λ(ϕ(e)) = λ(e) + 1. (This is only possible when
η gcd(|E1 |, |E2 |, . . . , |Eg |).) We say that two arcs e1 and e2 outgoing from the same vertex, pred(e1 ) =
pred(e2 ), span an intersection of size (λ(e1 ) − λ(e2 )) mod η ∈ Zη . We consider the set of all intersections
Aλ ⊆ Zη :
Aλ = {λ(e1 ) − λ(e2 ) : pred(e1 ) = pred(e2 )}.
8

(a)

(b)

(c)

Figure 2: (a) Example of a graph G with a circulation with no “small” intersections: for any m-labeling,
Aλ ⊆ [m/4, 3m/4]. Examples of assignments of colors in G for: (b) m-labeling and (c) m/5-labeling. In
both cases, all 3 colors meet at least once.
Observe that Aλ does not depend on the particular choice of λ, since all λ are identical up to cyclical shift.
We immediately have 0 ∈ Aλ and Aλ = −Aλ . Observe also that even when η is even, there is an odd element
in Aλ . Otherwise, we could partition vertices into two sets, {pred(e) : 2 | λ(e)} and {pred(e) : 2 6 |λ(e)},
which contradicts the assumption that G is not bipartite.
Set Aλ may have a non-trivial structure, e.g., may contain no small elements other than 0 (see e.g. Fig. 2).
Fortunately, it turns out we can take advantage of its spectral properties (which we subsequently formally
define).
Spectral properties of Aλ : We start by showing the following key property of the set Aλ of all intersections,
expressed by Lemma 3.1. We then briefly recall the formalism of Bohr sets, and use Lemma 3.1 to characterize
the structure of the Bohr set of Aλ .
Lemma 3.1. Let ξ ∈ Zη with 1 ≤ ξ ≤ η/6. Let Aλ be the set of intersections for an arbitrary η-labeling of
a circulation. Then, there exists x ∈ Aλ such that ξ · x ∈ [ 13 η, 32 η].
Proof. Let us consider a continuous version of set E, that is a metric space E constructed on the set E × [0, 1),
such that for every edge e, we set limt→1 (e, t) = (ϕ(e), 0). Observe that E is composed of disjoint spaces
E1 , E2 , . . . , Eg , where each Ei is a continuous version of cycle Ei , isometric to R/(|Ei |·Z) (i.e., to a cyclic
interval of length |Ei |).
We say that elements of E of the form ((v, ·), 0) are occurrences of v in E. Now we can extend the labeling
λ of E to a labeling L : E → R/(η·Z), so that L((e, 0)) = λ(e) and L |Ei is a locally distance-preserving
mapping of Ei to R/(η·Z). (L is an “interpolation” of λ, increasing in a continuous fashion at a constant rate
between discrete points on which λ was defined.)
We will say that two points in E meet if they are either occurrences of the same vertex v ∈ V , or if they
are of the form (e, t), (−e, 1 − t), for some e ∈ E and 0 < t < 1, where we recall that e and −e denote a
pair of opposing arcs.
Now, for fixed ξ ∈ Zη satisfying the assumption of the lemma, we assign to each point x ∈ E one of
three colors {0, 1, 2} according to the following rule:

1

0 if ξ · L(x) ∈ [0, 3 η),
color (x) = 1 if ξ · L(x) ∈ [ 13 η, 23 η),


2 if ξ · L(x) ∈ [ 23 η, η).
Thus, intuitively we have covered the continuous version of the arc set with closed directed continuous
cycles, and each cycle is colored along its orientation with colors 0, 1, 2, with colors successively applied to
9

contiguous segments of length η/(3ξ). See Figure 2 for example.Now, by purely topological reasoning, we
observe that there is a point of E, where all 3 colors meet. To be more precise, one of the following happens:
1. There exist x0 , x1 , x2 ∈ E, all being occurrences of the same vertex from V , such that color (xi ) = i.
It follows that ξ · (L(xi ) − L(xj )) ∈ [ 31 η, 23 η] for some i 6= j.
2. There exist x, y ∈ E that meet and satisfy the following constraint (up to permutation of colors
0, 1, 2): color (x) = 0, color (x − ε) = 2 (for arbitrarily small ε), and color(y) = 1. It follows that
ξ · (L(y) − L(x)) ∈ [ 13 η, 23 η).
Since L and λ agree on all the occurrences of the vertices (if we identify the values on the edges as taken on
the starting points), and in the second case we can round pair x, y to one of the endpoints of the edge they lie
on, the claim follows.
The above lemma, applied over different ξ, yields a valuable characterisation of the set of elements in Aλ .
Bohr set: We define the Bohr set with radius α for a set S ⊆ Zη as2 :
Bohr (S, α) = {ξ ∈ Zη : ∀s∈S ks · ξkη ≤ α},
where k · kη ∈ R denotes the “fractional part” norm on Zη . (Formally, for x ∈ Zη , we put kxkη = α for the
unique real α ∈ (−1/2, 1/2] such that x ≡ αη (mod η); see also [38][beginning of Section 4.4].)
With this definition, Lemma 3.1 can be rephrased as follows: Bohr (Aλ , 1/3 − ε) ∩ (0, η/6] = ∅, for
arbitrarily small ε > 0. This is not yet the spectral property we need, but Aλ is easily transformable to a set
with such a property. Since Aλ = −Aλ , we immediately have Bohr (Aλ , 1/3 − ε) ∩ [5/6η, η) = ∅ as well.
We will say that a is critical for b, if ka · bkη ≥ α. Since x · (2 · ξ) = (2 · x) · ξ, if x is a critical element

for 2 · ξ, 2 · x is critical for ξ, thus we have Bohr (2·Aλ , 1/3 − ε) ∩ [5/12η, η/2) ∪ (η/2, 7/12η] = ∅.
Additionally, we
 observe that for any ξ ∈ (η/6, 5/12η], k2·ξkη ≥ 1/6, thus Bohr (Aλ , 1/6)∩ (η/6, 5/12η]∪
[7/12η, 5/6η) = ∅.
By Aλ ∪ 2·Aλ ⊆ Aλ + Aλ , we conclude that Bohr (Aλ + Aλ , 1/6) ⊆ {0, η/2}. However, since we
know that Aλ contains an odd element, we can eliminate η/2 from the set. Thus finally, we obtain a spectral
characterization of set Aλ .
Lemma 3.2. Let Aλ be defined as in Lemma 3.1. Then: Bohr (Aλ + Aλ , 1/6) = {0}.
Additive combinatorics: Let A ⊆ Zη be any set. We denote by Â(j) the j-th (j ∈ [0, η − 1]) Fourier
coefficient inPthe transform of 1A , normalized so that Â(0) = 1 and |Â(j)| ≤ 1, for all j. Formally,
1
Â(j) := |A|
a∈A e(aj/η), where e(x) ≡ exp(2πix)).
Define the spectrum Spec α (A) as the set of all j ∈ [0, η − 1] such that |Â(j)| > α (i.e., the set of
indices of Fourier coefficients which are sufficiently large). The definition makes sense for α ∈ (0, 1] and
0 ∈ Spec α (A). (See [38][Def. 4.34]). The following lemma about annihilation of the spectrum is folklore;
we provide a short proof for completeness.
Lemma 3.3. If Spec 1−1/s (A) = {0}, then κA − κA = Zη , for κ ≥ s ln η.
2

For all undefined notation in additive combinatorics, we refer the reader to [24, 38].

10

Proof. Let κ = s ln η, and let rκA−κA (l) denote the number of ways to represent the value l ∈ Zη using
κA − κA. We have (cf. e.g. [24][Sec I.8]):
X
rκA−κA (l) = ck
|Â(j)|2κ e(−jl/η) ≥
(1)
j





≥ ck 1 −

X

|Â(j)|2κ  ,

j6=0

where ck is some positive normalizing constant (ck = |A|k /η).
Next, for a set A satisfying
the assumption of the Lemma, we have for j 6= 0: |Â(j)|2κ ≤ (1 −
P
2s
ln
η
1/s)
< 1/η. Hence, j6=0 |Â(j)|2κ < 1. It follows that for all l ∈ Zη , we have rκA−κA (l) > 0, and so
κA − κA = Zη .
In the following, we will also use the following property linking the Bohr set and the spectrum.
Proposition 3.4 ([38], variant of Prop. 4.40). Let A, B ⊆ Zη be such that A ⊆ B and 0 ∈ A. Let K ≥ 1
and 0 < ε < 1. If |B − A| ≤ K|B|, then
√
A − A ⊆ Bohr (Spec 1−ε (B − A), 8εK).
For completeness, the proof of the above Proposition is provided in the Appendix.
We are now ready to show our final Lemma, where we extend considerations from the above Proposition
to iterated sums of a set.
Lemma 3.5. For any set A1 ⊆ Zη , such that 0 ∈ A1 , we have that Spec 1−1/576 (A1 −κA1 ) ⊆ Bohr (A1 , 1/6),
for some κ = O(log η).
Proof. Let us denote for short B = Bohr (A1 , 1/6). In the proof of the lemma, we will use an equivalent
property characterizing A1 , which follows from symmetry of multiplication in expanding the Bohr set
definition (i.e., ∀x ∈ Zη , x 6= 0 : ∃ξ∈A1 kx · ξkη > 1/6):
∀X ⊆ Zη , X 6⊆ B : A1 6⊆ Bohr (X, 1/6).

(2)

We now define sets Ai , starting from A2 , as follows: Ai+1 := Ai − A1 . We will assume that 0 ∈ A1 , so
0 ∈ Ai for all i, and Ai+1 ⊇ Ai ⊇ . . . ⊇ A1 .
We now apply Proposition 3.4 to set Ai+1 , with K = 2 and ε = 1/576. From the Proposition, one of the
following two cases must hold:
• Either the assumption of the Proposition is not fulfilled, i.e., |Ai+1 | > 2|Ai |, or:
• A1 ⊆ A1 − A1 ⊆ Bohr (Spec 1−1/576 (Ai+1 ), 1/6).
Since Ai size is bounded by η, it suffices to iterate above construction until at most i ≤ log2 η to have the
latter case satisfied. Observe that then, by Eq. (2), we must then have Spec 1−1/576 (Ai+1 ) ⊆ B.
Observe that if we take any Aλ being the set of intersections for an arbitrary η-labeling of a circulation,
then we have already established that Bohr (Aλ , 1/6) = {0} (Lemma 3.2). By Lemma 3.5, we have that for
some κ = O(log η), Spec 1−1/576 (Aλ − κAλ ) ⊆ Bohr (Aλ , 1/6) = {0}. Applying Lemma 3.3 we obtain
the following technical claim.
Lemma 3.6. Let Aλ be the set of intersections for arbitrary η-labeling of a circulation. Then, κAλ = Zη for
some κ = O(log2 η).
11

4

Bounding the Diameter of Graph Gϕ

We now apply the sum-set structure of the set of self-intersections of a circulation, expressed by Lemma 3.6,
to bound the diameter of graph Gϕ . We start with a direct argument for the case of Eulerian circulations,
followed by a more involved analysis for the general case.

4.1

Eulerian Circulations (Proof of Lemma 2.1)

Considerations of Eulerian circulations rely on the definition of a metric δt , which expresses an upper bound
on the number of contiguous fragments of the Eulerian circuit which it is sufficient to traverse in order to
return to the starting arc with a time offset of t.
Intersection distance: Fix η = m. Let us consider a labeling λ and the corresponding set of intersections
Aλ . We will say that a function δ : Z → Z+ is an intersection distance measure if it satisfies the following
constraints:
δim = 0

for any i ∈ Z

(3)

δx ≤ 1

when x ∈ Aλ

(4)

δ−x = δx

for any x ∈ Z

(5)

for any x, y ∈ Z

(6)

δx+y ≤ δx + δy

From the definition it follows that for any x ∈ κAλ , δx ≤ κ. Thus by Lemma 3.6 we immediately have:
max δx = max δx = O(log2 η),
x∈Z

x∈Zη

(7)

where the first equality holds by property (3), corresponding to shifts by a complete tour of the Eulerian
circuit.
Phrasing the above in terms of distances in Gϕ , by considering for any node v the properties of function
δx for some arc of the form (v, ·), we conclude that the distance in Gϕ between any two nodes of the form
(v, t) and (v, t + x), x, t ∈ Z is bounded by O(log2 η). Since for any pair of vertices u 6= v there exists a
path v →xvu u, for some xvu ∈ Z we moreover have that pairs of vertices of the form (v, t), (u, t + xvu ),
t ∈ Z, are at distance 1 from each other in Gϕ . The claim of Lemma 2.1 follows.

4.2

General Circulations (Proof of Lemma 2.3)

We now extend the definition of intersection distance so that it is useful for arbitrary circulations.
Generalizing intersection distance: Let ϕ be an arbitrary circulation. We will say that a function δ :
Z × E × E → Z+ is a generalized intersection distance measure if it satisfies the following constraints:
δ0 (e, e) = 0

for any e ∈ E

(8)

δ1 (e, ϕ(e)) = 0

for any e ∈ E

(9)

δ0 (e1 , e2 ) = 1
δ−x (e2 , e1 ) = δx (e1 , e2 )
δx+y (e1 , e3 ) ≤ δx (e1 , e2 ) + δy (e2 , e3 )
12

when pred(e1 ) = pred(e2 )

(10)

for any x ∈ Z, e1 , e2 ∈ E

(11)

for any x, y ∈ Z, e1 , e2 , e3 ∈ E

(12)

The generalization is to be understood in the following sense: if ϕ is an Euclidean circulation and δ is a
generalized intersection distance measure, then for arbitrary e ∈ E, δx := δx (e, e) is an intersection distance
measure.
Cycle combinatorics: We now define a few more concepts regarding how different cycles in a (nonEulerian) circulation relate to each other.
First, given a circulation with cycles (E1 , . . . , Eg ), we introduce the notion of adjacency of cycles, saying
that two cycles are adjacent if they share a common vertex. Naturally, we can use this definition of adjacency
to define a graph G on the set of cycles of the circulation, and the corresponding distance ∆(Ei , Ej ) between
any two cycles Ei and Ej as the number of adjacency hops needed to go between this pair of cycles.
Additionally, given labeling λ of the circulation, we say that two cycles Ei , Ej are λ-adjacent if there
are two arcs ei ∈ Ei , ej ∈ Ej , such that pred(ei ) = pred(ej ) and λ(ei ) = λ(ej ). We call the graph
Gλ with vertex set corresponding to the set of cycles the cycles {E1 , . . . , Eg } and edges corresponding
the λ-adjacency relation the cycle graph. For two cycles Ei , Ej , we denote by ∆λ (Ei , Ej ) the distance
in the cycle graph Gλ between respective cycles Ei and Ej . For compactness of notation, given two arcs
e1 ∈ E1 , e2 ∈ E2 , we denote ∆λ (e1 , e2 ) = ∆λ (E1 , E2 ). Finally, we say that labeling λ is cycle-connected
if its cycle graph Gλ is connected.
It is easy to see that we can always adjust any indexing λ by cyclical shifts, successively for each cycle,
so as to incorporate an arbitrary spanning tree of G in the cycle graph Gλ . In particular, by considering the
BFS tree of G, whose diameter is at most 2 · diam(G), we have the following result.
Observation 4.1. For any η| gcd(|E1 |, . . . , |Eg |), there is an η-labeling λ such that for any Ei , Ej : ∆λ (Ei , Ej ) ≤
2 · diam(G).
From now on we assume that λ satisfies the property given by Observation 4.1.
Lemma 4.2. For any pair of arcs e1 , e2 , there exists α ∈ Z such that α ≡ λ(e2 ) − λ(e1 ) (mod η) and
δα (e1 , e2 ) ≤ ∆λ (e1 , e2 ). Moreover, there exists α0 ∈ Z, such that δα0 (e1 , e2 ) ≤ ∆(e1 , e2 ).
Proof. We start by covering the first part of claim. If e1 and e2 belong to the same cycle, then there is x ∈ Z
such that δx (e1 , e2 ) = 0. However, since λ limited to one particular cycle is just a cyclic numbering modulo
n, we have that λ(e2 ) − λ(e1 ) ≡ x (mod n).
We also observe that the claim is satisfied for two arcs that make corresponding cycles λ-adjacent: if
λ(e1 ) = λ(e2 ) and e1 and e2 are adjacent, then simultaneously λ(e2 ) − λ(e1 ) = 0 and δ0 (e1 , e2 ) ≤ 1.
By a simple chaining argument we can extend this to any two arcs on λ-adjacent cycles, and by the
induction on ∆λ (e1 , e2 ) to any two arcs.
By repeating the same reasoning using cycle adjacency instead of λ-adjacency, we get the second claim
(without getting any constraint on α0 ).
Lemma 4.3. For any two arcs e, e0 and x ∈ Z, we have δx (e0 , e0 ) ≤ δx (e, e) + 2∆(e, e0 ) ≤ δx (e, e) +
O(diam(G)).
Proof. There is α ∈ Z such that δα (e, e0 ) ≤ ∆(e, e0 ). Thus δx (e0 , e0 ) ≤ δα (e0 , e) + δx−α+α (e, e) +
δ−α (e, e0 ) ≤ δx (e, e) + 2∆(e, e0 ).
Lemma 4.4. For any δ that is a generalized intersection distance measure on a circulation with g orbits, we
have:
e
max δx (e, e) = O(g).
e∈E,x∈Z

13

Proof. Let η = gcd(|E1 |, . . . , |Eg |), and consider an indexing λ following Observation 4.1. We will once
again be working with the set of all intersections Aλ ⊆ Zη .
Fix any x ∈ Aλ . Thus, there are e1 ∈ E1 , e2 ∈ E2 such that pred(e1 ) = pred(e2 ) and λ(e2 ) −
λ(e1 ) = x. The cycles E1 , E2 are not necessarily λ-adjacent, however by Lemma 4.2 we have that
δα (e1 , e2 ) = O(diam(G)) for some α ≡ x (mod η). Moreover, since pred(e1 ) = pred(e2 ), we have
δα (e1 , e1 ) ≤ δα (e1 , e2 ) + 1, and so δα (e1 , e1 ) = O(diam(G)). By a direct application of Lemma 4.3 we
can extend this bound to any arc e ∈ E: δα (e, e) ≤ 2 · ∆(e, e1 ) + δα (e1 , e1 ) = O(diam(G)). Thus we
have that for any x ∈ κAλ , there is x0 ∈ Z such that δx0 (e, e) = O(κ · diam(G)), and x0 ≡ x (mod η). By
Lemma 3.2 and Lemma 3.6, there exists κ = O(log2 n) such that κAλ = Zη .
Denote β = (x0 − x)/η. We have shown that skewed distances can be bounded for a set which, under the
projection mod η, is Zη . We will now focus on controlling the term β, describing shifts by multiplies of η.
Pick e1 ∈ E1 . We have δc·|E1 | (e1 , e1 ) = 0 for any integer c, thus by Lemma 4.3, δc·|E1 | (e, e) = O(diam(G))
for any arc e.
Recall that we put η = gcd(|E1 |, . . . , |Eg |). We observe that η has at most O(log η) ⊆ O(log n) different
primes in its factorization, thus the gcd is already obtained by taking particular
P subset of log n elements.
It follows that for any integer β, there exists a sequence c1 , . . . , cg such
that
i ci |Ei | = βη and there are
P
O(log n) non-zero coefficients in ci . Thus, in particular, δβη (e, e) ≤ i δci |Ei | (e, e) = O(diam(G) · log n).
Combining shifts by multiplicities of η with shifts with proper remainders, we finally have: δx (e, e) ≤
e
δx0 (e, e) + δβη (e, e) = O(diam(G)),
from which the claim follows.
As in the Eulerian case, we observe that the upper bound on δx (e, e) also gives an upper bound on the path
length in graph Gϕ , up to an additive factor of g which allows us to move between two spatially separated
vertices. This completes the proof of Lemma 2.3.

5
5.1

Results for RR Dynamics
Preliminaries: Properties of RR and Auxiliary Definitions

We recall that the RR dynamics was introduced in Section 1.1. We define edge load Lt and cumulated
load
P
Ct∆t as follows: Lt (e) is the number of tokens traversing arc e at timestep t, and Ct∆t (e) =
Lt+i (e).
0≤i<∆t

The following notation will be useful when discussing the load-balancing and patrolling properties of the
RR dynamics.
Load balancing: A standard notion is to define a discrepancy (over arcs) of a token distribution at a given
timestep t as max{|Lt (e1 ) − Lt (e2 )| : e1 , e2 ∈ E}. Similarly, a notion of a cumulative discrepancy over
time ∆t defined as max{ Ct∆t (e1 ) − Ct∆t (e2 ) : e1 , e2 ∈ E}.
Patrolling: We say that an arc e has an idleness of t if, starting from some point in time, e is visited at least
once in every interval of t consecutive steps, and t is the smallest such value. More precisely, we define idle
arc time at a given time step t as idle(t, e) = min(∆t : Ct∆t (e) ≥ 1). We define idleness for a single arc:
idle(e) = lim sup idle(t, e). Finally we define idleness as: idle(G) = max{idle(e) : e ∈ E}.
t→∞

Limit behavior: We recall following two results characterizing limit behavior of the RR system, reached
in polynomially many steps.

14

Theorem 5.1 ([10], Theorem 11). RR dynamics is recurrent, if and only if there is a bijection ϕ : E → E,
such that ∀t≥0 ∀e∈E Lt (e) = Lt+1 (ϕ(e)). Moreover, ϕ can always be selected so that pred(ϕ(e)) = succ(e)
for any arc e.
From now on we will identify the subcycle decomposition with bijection ϕ. We will denote the Eulerian
cycles induced by ϕ as E1 , E2 , . . . , Eg , with g denoting number of cycles.
Theorem 5.2 ([10], Theorem 26). RR dynamics reaches its recurrent state in O(m4 diam2 + mdiam log k)
steps on a graph G of diameter diam.
By Theorems 5.1 and 5.2 any configuration after polynomially many steps reaches recurrent state. Thus
from now on we assume that system at the timestep 0 is already in a recurrent state.
Averaging and
P number of cycles: Let us denote by ki the total number of tokens circulating cycle Ei ,
that is ki = e∈Ei Lt (e) (this value does not depend on the choice of k). It is easy to see that in order to
maintain cumulative discrepancy over arbitrarily long time, the following property has to hold
k1
k2
k
=
= ... = .
|E1 |
|E2 |
m

(13)

As a corollary of (13), the number of cycles g has to satisfy g | gcd(k, m), thus g ≤ gcd(k, m) follows.
Thus, in particular, if m is prime, then for any k < m we have exactly one cycle. The same occurs whenever
k ⊥ m in the general case.

5.2

RR Dynamics with Eulerian Circulation

Now we proceed to analyze RR dynamics in a recurrent state that has a circulation with a single cycle. Let us
fix circulation ϕ as in Theorem 5.1.
5.2.1

The Similarity Measure

We use the similarity of the sequence to itself under shifts, where this similarity follows from the small
discrepancy of loads on arcs that share a starting (predecessor) vertex.
We define the similarity for time shift t ∈ Z as:
δt =

max

e∈E,τ,∆t≥0

|Cτ∆t (e) − Cτ∆t
+t (e)|.

(14)

Lemma 5.3. δ defined as in (14) is an intersection distance measure.
Proof. It is immediate to verify that δ satisfies (3),(5) and (6). To show (4), take i ∈ Aλ . By the definition,
there are two edges e1 , e2 , such that pred(e1 ) = pred(e2 ) and λ(e2 ) = λ(e1 ) + i. Thus, e2 = ϕi (e1 ). Fix
e ∈ E. Since ϕ is an Eulerian circulation, let j ≥ 0 be such that ϕj (e) = e1 . We have, for any τ and ∆t:
∆t
∆t
|Cτ∆t (e) − Cτ∆t
+i (e)| = |Cτ +j (e1 ) − Cτ +j+i (e2 )| ≤ 1

thus δi ≤ 1 and (4) is satisfied.

15

5.2.2

Time-Averaging Property

Lemma 5.4. For RR dynamics on an Eulerian circulation, for any time step t in the recurrent state, T > 0
k
and e ∈ E, we have CtT (e) − m
· T ≤ δT ≤ O(log2 η).
Proof. Fix time interval T > 0 and pick t1 and t2 , with t2 > t1 , in the recurrent state arbitrarily. We have the
following bounds:
−t1
CtT1 (e) − CtT2 (e) = Ctt12 −t1 (e) − Ctt12+T
(e) ≤ δT ,
where
the factP
that, for an
sequence xi and integers a ≤ b ≤ c ≤ d, it holds that:
Pb−1 we used
Pd−1
Parbitrary
c−1
d−1
i=a xi −
i=c xi =
i=a xi −
i=b xi , and for the last bound, we used (14).
Since t1 , t2 were arbitrary, bounds on the discrepancy of the sequence (CtT )t∈Z , follow. Since this
k
k
sequence is periodic and by equation (13) its average value is T · m
, the inequality CtT (e) − m
· T ≤ δT
follows immediately from the previously shown bound. Finally, we have δT ≤ O(log2 η) by (7), since δT is
an intersection distance measure following Lemma 5.3.
P 0 +T
Recalling that by definition CtT0 (e) = tt=t
Lt (e), we obtain directly from Lemma 5.4:
0
 
t0 +T
1
1 X
k
e
±O
,
Lt (e) =
T t=t
m
T
0

which proves Theorem 2.5 for the special case of Eulerian circulations.

5.3

RR Dynamics with General Circulation

We now apply the results on circulations with multiple cycles to provide bounds for arbitrary RR dynamics.
5.3.1

Generalized Similarity Measure

We extended the notion of δx into a load similarity measure between pair of arcs, under time shift. Thus, we
define skewed distance function, for t ∈ Z
δt (e1 , e2 ) = max |Cτ∆t (e1 ) − Cτ∆t
+t (e2 )|.
τ,∆t≥0

It is easy to verify that δ defined as above satisfies (8),(9),(10),(11), and (12); δ is thus a generalized
intersection distance measure with respect to circulation ϕ. We obtain the following formulation of Lemma 4.4
for the considered function δt .
Lemma 5.5.
e
e
max δt (e, e) = O(g)
≤ O(gcd(k,
m)).

e∈E,t∈Z

5.3.2

Time-Averaging Property

The following Lemma is an automatic generalization of Lemma 5.4.
Lemma 5.6. For RR dynamics on an arbitrary circulation, for any time step t in the recurrent state, T > 0
k
and e ∈ E, we have CtT (e) − m
· T ≤ δT (e, e).

16

Recalling once again that by definition CtT0 (e) =

Pt0 +T
t=t0

Lt (e), Lemmas 5.5 and 5.6 directly give:



t0 +T
1 X
k
gcd(k, m)
e
Lt (e) =
.
±O
T t=t
m
T
0

which completes the proof of Theorem 2.5 in the general case.
5.3.3

Other Bounds on the Generalized Similarity Measure

Going beyond the bound of Theorem 2.5, we provide a number of corollaries and auxiliary results, upperbounding the generalized similarity measure δT (e, e) with respect to other graph parameters. We will then
use them in conjunction with Lemma 5.6 to bound the cumulated load of the RR dynamics.
e √n) bound that uses thresholding: we make use of the fact that in the considered
Now first provide a O(
circulation, there are either small cycles (so any cycle must have a short one in its proximity), or there are
only large cycles, so there can only be a small number of them. We use the notation developed in Section 4,
denoting distance between cycles as ∆(Ei , Ej ).
e √n).
Lemma 5.7. For any e and integer x, δx (e, e) = O(
√
Proof. We will call a cycle that contains at most n distinct vertices a small cycle.
In the adjacency graph of cycles G, any shortest path of length x between two cycles contains a cycle
using at most 2n/x distinct vertices.
First, let us assume that there is at least one small cycle in the graph. Thus, for any cycle E1 there is
√
√
2n
a small cycle E2 such that ∆(E1 , E2 ) ≤ √
= O( n). Fix e1 ∈ E1 , e2 ∈ E2 . Since diam(E2 ) ≤ n,
n
√
by Lemma 5.9, δT (e2 , e2 ) = O( n) for any integer T . By Lemma 4.3 we then have δT (e1 , e1 ) ≤
√
δT (e2 , e2 ) + 2∆(E1 , E2 ) = O( n).
√
If there are no small cycles in the graph, then every cycle is of size at least n distinct vertices. So
√
diam(G) = O( n) by the previous observation, and the claim follows from Lemma 4.4.
Next, the following bound trivially holds for small values of t, subsequently allowing us to perform
analysis of the RR for values of k close to m.
Lemma 5.8. For any e, δ4 (e, e) ≤ 3.
Proof. Observe that since arcs pred(−e) = pred(ϕ(e)), δ1 (e, −e) ≤ 1. Thus, δ2 (e, e) ≤ 2. Similarly, one
can reason that δ2 (ϕ2 (e), e) ≤ 3, giving δ4 (e, e) ≤ 3.
For our next bound, let us denote by d(e1 , e2 ) the distance (length of shortest path) between starting
vertices of e1 and e2 , measured in G. We also denote diam(G) = max d(e1 , e2 ) and diam(Ei ) =
e1 ,e2 ∈E

max d(e1 , e2 ). (For sanity of notation, we define diam(Ei ) so that diam(Ei ) ≥ 1 even if Ei is a loop.)

e1 ,e2 ∈Ei

The following Lemma relates cycle diameter with our analysis.
Lemma 5.9. For any integer j and edge e ∈ Ei , we have: δj (e, e) = O(diam(Ei )) ≤ O(diam(G)).
Proof. Assume j > 0 and fix an integer r > 0. Observe that d(e, ϕr (e)) ≤ diam(Ei ), thus we have
δr+d(e,ϕr (e)) (e, e) ≤ diam(Ei ) + 1. Since for consecutive values of r the value of r + d(e, ϕr (e)) increases
by 0, 1 or 2, either the claim follows, or δj−1 (e, e) ≤ diam(Ei ) + 1. However, since in every vertex there is
a loop, we have δ1 (e, e) ≤ 2 and the claim follows.
17

The following bound on the generalized similarity measure proves useful when considering sufficiently
long ranges of time.
e
Lemma 5.10. For any integer B ≤ m and for any e, we have: minx∈[B,2B] δx (e, e) = O(m/B).
Proof. First, let us assume that there is at least one cycle with number of arcs not more than B. Thus,
by a reasoning similar to one from Theorem 5.7, for any cycle E1 and arc e1 ∈ E1 there exists a cycle
E2 having at most B arcs and that ∆(E1 , E2 ) ≤ m
B . For any e2 ∈ E2 there is integer B ≤ x ≤ 2B
such that δx (e2 , e2 ) = 0 (it suffices for x to be a multiplicity of |E2 |). Thus for any e1 ∈ E1 , we have
δx (e1 , e1 ) ≤ 2m/B. Since e1 was picked arbitrarily, the claim follows.
If every cycle has at least B arcs, then the number of cycles satisfies g ≤ m/B. Thus the claim follows
from Lemma 4.4.
Finally, we obtain the following O(1) bound on the generalized similarity measure of the RR dynamics
in trees. We remark that this bound holds even though trees are bipartite.
Lemma 5.11. If G is a tree, then for any e and positive integer B, we have: minx∈[B,2B] δx (e, e) = O(1).
Proof. Cycles in E are DFS traversals of some subtree of G. We can safely analyse each such subtree
separately. Take such subtree T , and fix B ≤ 2|T |. (The size here is measured in number of edges.) We
pick arbitrary root of T , and we consider subtrees denoted Tv , that is rooted in some vertex v containing
everything “below” v, plus the edge connecting v to its parent. One of two cases occurs: (1) there is v such that
2|Tv | ∈ [B, 2B], or (2) there is v with children w1 , w2 , . . . such that 2|Tv | > 2B and 2|Tw1 |, 2|Tw2 |, . . . < B.
In the first case, the cycle that takes part in Tv is of size 2|Tv |, thus we have for some x ∈ [B, 2B] that
δx (e0 , e0 ) = 1, for some e0 in this cycle, thus also for every edge in this cycle.
In the second case, assume that w1 , w2 , . . . are in the order in which the cycle visits those vertices. Since
|Tw1 | + |Tw2 | + . . . = |Tv | − 1 ≥ B, and each of |Twi | is smaller than B/2, we know there prefix sum
such that 2|Tw1 | + 2|Tw2 | + . . . + 2|Twj | ∈ [B, 2B]. Once again we argue that there is a self-intersection of
appropriate length, and the claim follows.

5.4

Cumulated Load Discrepancy of RR

Lemma 5.6 provides us with bounds on the cumulated load discrepancy of the RR dynamics in terms of
the generalized similarity measure δT (e, e). Introducing Lemmas 5.5, 5.9, and 5.7, we directly obtain the
following claims.
Proposition 5.12. The cumulated load discrepancy of RR dynamics in its recurrent state can be upperbounded as:
e
• O(gcd(k,
m)).
• O(diam(G)).
e √n).
• O(

18

5.5

Idleness of RR

Lemma 5.6 also provides a way of upper-bounding the idleness of the RR dynamics in terms of the generalized
similarity measure δT (e, e). Indeed, we have the following claim.
Lemma 5.13. If T >

m
k

· δT (e, e) for some particular value of T , then idle(e) ≤ T .

Proof. By Lemma 5.6, we obtain CtT (e) ≥
choice of t, the claim follows.

k
m

· T − δT (e, e) > 0. Since this bound holds regardless of the

The following claims are now obtained directly, by combining Lemma 5.13 for an appropriately choe m · gcd(k, m))),
sen value of T with specific bounds on δT (e, e), given by Lemma 5.5 (putting T = O(
k
√
e m · n)), Lemma 5.8 (putting
Lemma 5.9 (putting T = O( m
·
diam(G))),
Lemma
5.7
(putting
T
=
O(
k
k
T = 4), 5.11 (putting T = arg minx∈[c·m/k,2c·m/k] δx (e, e) for arbitrary e and c = O(1) being the bound
√
e
from Lemma 5.11), and Lemma 5.10 (putting B = O(m/
k)).
Proposition 5.14. For k ≤ m, the RR dynamics satisfies the following bounds on idleness:
e m · gcd(k, m)).
• idle(G) = O(
k
• idle(G) = O( m
k · diam(G)).
e m · √n).
• idle(G) = O(
k
• idle(G) ≤ 4 if k > 34 m.
• idle(G) = O( m
k ), on a tree.
√
e m · k).
• idle(G) = O(
k

6

Conclusion

The obtained results show that the RR dynamics achieves almost optimal time-averaging behavior for a
vast majority of parameter values. This has implications for the considered patrolling and load-balancing
problems, as shown in Table 1, most notably in the case when m and k have no large common divisors.
The case of an underlying Eulerian circulation has been fully resolved, and the mixing properties of the
associated walks along Eulerian circuits are well understood. For the non-Eulerian case, it is an open question
whether improved generalized δ-distance bounds can be obtained, independent of the number of cycles g of
the considered circulation, with consequent improved bounds on the performance of the RR dynamics.

Acknowledgments
We thank Jurek Czyzowicz and Jukka Suomela for fruitful discussions. We also thank an anonymous referee
for valuable comments.

19

References
[1] Y. Afek and E. Gafni. Distributed algorithms for unidirectional networks. SIAM J. Comput., 23(6):1152–
1178, 1994.
[2] N. Agmon, S. Kraus, and G. A. Kaminka. Multi-robot perimeter patrol in adversarial settings. In ICRA,
pages 2339–2345, 2008.
[3] H. Akbari and P. Berenbrink. Parallel rotor walks on finite graphs and applications in discrete load
balancing. In SPAA, pages 186–195, 2013.
[4] H. Akbari, P. Berenbrink, and T. Sauerwald. A simple approach for adapting continuous load balancing
processes to discrete settings. In PODC, pages 271–280, 2012.
[5] A. Almeida, G. Ramalho, H. Santana, P. A. Tedesco, T. Menezes, V. Corruble, and Y. Chevaleyre.
Recent advances on multi-agent patrolling. In SBIA, pages 474–483, 2004.
[6] P. Bak, C. Tang, and K. Wiesenfeld. Self-organized criticality: An explanation of 1/f noise. Physical
Review Letters, 59:381–384, 1987.
˛
N. Hanusse, D. Ilcinkas, R. Klasing, and A. Kosowski. Euler tour lock-in
[7] E. Bampas, L. Gasieniec,
problem in the rotor-router model. In DISC, pages 423–435, 2009.
[8] P. Berenbrink, R. Klasing, A. Kosowski, F. Mallmann-Trenn, and P. Uznański. Improved analysis of
deterministic load-balancing schemes. In PODC, pages 301–310, 2015.
[9] A. Björner, L. Lovász, and P. W. Shor. Chip-firing games on graphs. European Journal of Combinatorics,
12:283–291, 1991.
[10] J. Chalopin, S. Das, P. Gawrychowski, A. Kosowski, A. Labourel, and P. Uznański. Limit behavior of
the multi-agent rotor-router system. In DISC, pages 123–139, 2015.
[11] Y. Chevaleyre. Theoretical analysis of the multi-agent patrolling problem. In IAT, pages 302–308, 2004.
[12] J. Cooper and J. Spencer. Simulating a random walk with constant error. Combinatorics, Probability
and Computing, 15:815–822, November 2006.
[13] J. Czyzowicz, A. Kosowski, E. Kranakis, and N. Taleb. Patrolling trees with mobile robots. In FPS,
volume 10128 of Lecture Notes in Computer Science, pages 331–344. Springer, 2016.
[14] R. Dandekar and D. Dhar. Proportionate growth in patterns formed in the rotor-router model. Journal
of Statistical Mechanics: Theory and Experiment, 2014(11):P11030, 2014.
[15] D. Dereniowski, A. Kosowski, D. Pajak,
˛ and P. Uznański. Bounds on the cover time of parallel rotor
walks. In STACS, pages 263–275, 2014.
[16] B. Doerr and T. Friedrich. Deterministic random walks on the two-dimensional grid. Combinatorics,
Probability and Computing, 18(1-2):123–144, 2009.
[17] Y. Elmaliach, N. Agmon, and G. A. Kaminka. Multi-robot area patrol under frequency constraints. Ann.
Math. Artif. Intell., 57(3-4):293–320, 2009.
20

[18] Y. Elmaliach, A. Shiloni, and G. A. Kaminka. A realistic model of frequency-based multi-robot polyline
patrolling. In AAMAS (1), pages 63–70, 2008.
[19] R. Elsässer and T. Sauerwald. Tight bounds for the cover time of multiple random walks. Theor. Comput.
Sci., 412(24):2623–2641, 2011.
[20] A. S. Fraenkel. Economic traversal of labyrinths. Mathematics Magazine, 43:125–130, 1970.
[21] T. Friedrich, M. Gairing, and T. Sauerwald. Quasirandom load balancing. In SODA, pages 1620–1629,
2010.
[22] T. Friedrich and T. Sauerwald. Near-perfect load balancing by randomized rounding. In STOC, pages
121–130, 2009.
[23] L. Gasieniec
˛
and T. Radzik. Memory efficient anonymous graph exploration. In WG, pages 14–29,
2008.
[24] A. Granville. An introduction to additive combinatorics. In Additive Combinatorics, CRM Proceedings
and Lecture Notes, pages 1–27. American Mathematical Society, 2007.
[25] N. Hazon and G. A. Kaminka. On redundancy, efficiency, and robustness in coverage for multiple
robots. Robotics and Autonomous Systems, 56(12):1102–1114, 2008.
[26] A. Holroyd and J. Propp. Rotor walks and Markov chains. Algorithmic Probability and Combinatorics,
pages 105–126, 2010.
[27] M. A. Kiwi, R. Ndoundam, M. Tchuente, and E. Goles. No polynomial bound for the period of the
parallel chip firing game on graphs. Theor. Comput. Sci., 136(2):527–532, 1994.
[28] R. Klasing, A. Kosowski, D. Pajak,
˛ and T. Sauerwald. The multi-agent rotor-router on the ring: a
deterministic alternative to parallel random walks. In PODC, pages 365–374, 2013.
[29] A. Kosowski and D. Pajak.
˛ A case study of cover time for the rotor-router. In ICALP, pages 544–555,
2014.
[30] A. Machado, G. Ramalho, J.-D. Zucker, and A. Drogoul. Multi-agent patrolling: An empirical analysis
of alternative architectures. In MABS, pages 155–170, 2002.
[31] F. Pasqualetti, A. Franchi, and F. Bullo. On optimal cooperative patrolling. In CDC, pages 7153–7158,
2010.
[32] V. Priezzhev, D. Dhar, A. Dhar, and S. Krishnamurthy. Eulerian walkers as a model of self-organized
criticality. Phys. Rev. Lett., 77(25):5079–5082, Dec 1996.
[33] Y. Rabani, A. Sinclair, and R. Wanka. Local divergence of markov chains and the analysis of iterative
load-balancing schemes. In FOCS, pages 694–703, 1998.
[34] A. Ramachandran and A. Schild. Sandpile prediction on a tree in near linear time. In SODA, pages
1115–1131. SIAM, 2017.
[35] T. Sauerwald and H. Sun. Tight bounds for randomized load balancing on arbitrary network topologies.
In FOCS, pages 341–350, 2012.
21

[36] T. Shiraga, Y. Yamauchi, S. Kijima, and M. Yamashita. Total variation discrepancy of deterministic
random walks for ergodic markov chains. In ANALCO, pages 138–148, 2016.
[37] R. Subramanian and I. Scherson. An analysis of diffusive load-balancing. In SPAA, pages 220–225,
1994.
[38] T. Tao and V. H. Vu. Additive Combinatorics. Cambridge University Press, 2006. Cambridge Books
Online.
[39] V. Yanovski, I. A. Wagner, and A. M. Bruckstein. A distributed ant algorithm for efficiently patrolling a
network. Algorithmica, 37(3):165–186, 2003.

A

Proof of Proposition 3.4

Let x, y ∈ A and ξ ∈ Spec 1−ε (B − A). Then there exists a phase θ ∈ R/(η·Z) such that
X
Re
e(ξ · z + θ) ≥ (1 − ε)|B − A|,
z∈B−A

thus
X

(1 − Re e(ξ · z + θ)) ≤ ε|B − A| ≤ εK|B|.

z∈B−A

Since the summand is non-negative, and B − A contains b − x,
X
|1 − Re e(ξ · (b − x) + θ)| ≤ εK|B|
b∈B

and by Cauchy-Schwarz
X

|1 − Re e(ξ · (b − x) + θ)|1/2 ≤ ε1/2 K 1/2 |B|.

b∈B

√
From the elementary identity |1 − e(α)| = 2|1 − Re e(α)|1/2 we conclude that:
X
√
|1 − e(ξ · (b − x) + θ)| ≤ 2ε1/2 K 1/2 |B|.
b∈B

A similar expression is obtained for x replaced by y. By the triangle inequality we conclude that
X
√
|e(ξ · (b − y) + θ) − e(ξ · (b − x) + θ)| ≤ 2 2ε1/2 K 1/2 |B|.
b∈B

The left hand side is equal to:
X
|e(ξ · (b − y) + θ)| · |e(ξ · (x − y)) − 1| = |B| · |e(ξ · (x − y)) − 1|,
b∈B

thus we have:
|e(ξ · (x − y)) − 1| ≤

√
8εK.

Since we picked ξ ∈ Spec 1−ε (B − A) and x, y ∈ A arbitrarily, the claim follows.
22

