Proving the Herman-Protocol Conjecture
Maria Bruna1 , Radu Grigore2 , Stefan Kiefer3 , Joël Ouaknine3 , and
James Worrell3
1
2
3

Mathematical Institute, University of Oxford
School of Computing, University of Kent
Department of Computer Science, University of Oxford

arXiv:1504.01130v3 [cs.DS] 27 Apr 2016

Abstract
Herman’s self-stabilization algorithm, introduced 25 years ago, is a well-studied synchronous
randomized protocol for enabling a ring of N processes collectively holding any odd number
of tokens to reach a stable state in which a single token remains. Determining the worst-case
expected time to stabilization is the central outstanding open problem about this protocol. It is
known that there is a constant h such that any initial configuration has expected stabilization
time at most hN 2 . Ten years ago, McIver and Morgan established a lower bound of 4/27 ≈ 0.148
for h, achieved with three equally-spaced tokens, and conjectured this to be the optimal value
of h. A series of papers over the last decade gradually reduced the upper bound on h, with
the present record (achieved in 2014) standing at approximately 0.156. In this paper, we prove
McIver and Morgan’s conjecture and establish that h = 4/27 is indeed optimal.
1998 ACM Subject Classification F.1.2 Modes of Computation
Keywords and phrases randomized protocols, self-stabilization, Lyapunov function, expected
time
Digital Object Identifier 10.4230/LIPIcs.ICALP.2016.XXX

1

Introduction

The notion of self-stabilization was introduced in a seminal paper of Dijkstra [10], and rose to
prominence a decade later, following (among others) an invited talk of Lamport during which
he pointed out that “self-stabilization [is] a very important concept in fault tolerance” [21].
Both self-stabilization and fault tolerance have since become central themes in distributed
computing (see, e.g., [11]), as recently witnessed by the award of the 2015 Edsger W. Dijkstra
Prize in Distributed Computing to Michael Ben-Or and Michael Rabin for “starting the field
of fault-tolerant randomized distributed algorithms” in the early 1980s.
In this paper, we examine an early self-stabilization algorithm known as Herman’s
Protocol [18], whose exact mathematical analysis has proven remarkably challenging over the
two-and-a-half decades since its inception. This algorithm considers a ring of N processes
(or nodes), where each process either holds or doesn’t hold a token. Starting from any initial
configuration of K tokens, where K is required to be odd, Herman’s algorithm proceeds
as follows: at each time step, every process that holds a token either keeps it or passes it
to its clockwise neighbor with probability 1/2. All updates happen synchronously, and if a
process finds itself with two tokens (having simultaneously kept one and received one from
its counterclockwise neighbor) then both tokens are annihilated. It is straightforward to see
that, starting from an odd number of tokens and following this procedure, almost surely only
one token eventually remains, at which point the ring is said to have stabilized.
Herman’s original paper [18] presents the algorithm in a form amenable to implementation.
Each process possesses a bit, which the process can read and write. Each process can also
© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:1–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

read the bit of its counterclockwise neighbor. In this representation, having the same bit
as one’s counterclockwise neighbor is interpreted as having a token. At each time step,
each process compares its bit with the bit of its counterclockwise neighbor; if the bits differ,
the process keeps its bit, whereas if the bits are the same, the process flips its bit with
probability 1/2 and keeps it with probability 1/2. It is straightforward to verify that the
bit-flipping version is an implementation of the token-passing version: in particular, a process
flipping its bit corresponds to passing its token to its clockwise neighbor. If the number of
processes is odd, by construction this bit representation forces the number of tokens to be
odd as well, which justifies the assumption that K, the number of tokens, is always odd.
In this paper we make no assumption about the parity of the number of processes, as we
abstract from the bit implementation, and simply assume that the number of tokens is odd
throughout.
Herman’s original paper [18] showed that the expected time (number of synchronous steps)
to stabilization is O(N 2 log N ). The same paper also mentions an improved upper bound
of O(N 2 ) due to Dolev, Israeli, and Moran, without giving a proof or a further reference.
In 2004, Fribourg et al. [15] established an upper bound of 2N 2 , and the following year
Nakata [23] gave a tighter upper bound of 0.936N 2 and exhibited an initial configuration
with expected stablization time Ω(N 2 ). At the same time and independently, McIver and
Morgan showed in [22] that the initial configuration consisting of three equally-spaced tokens
4
has an expected stabilization time of exactly 27
N 2 , and conjectured that this value is an
upper bound on the expected time to stabilization starting from any initial configuration
with any (odd) number of tokens. The conjecture is intriguing since increasing the initial
number of tokens might be thought to lengthen the expected time to stabilization, due to
the larger number of collisions required to achieve stabilization.
Nevertheless, McIver and Morgan’s Herman-Protocol Conjecture is supported by considerable amount of experimental evidence [4], and in the intervening years a series of papers
have gradually reduced the upper bound on the constant h such that stabilization from any
initial configuration takes expected time at most hN 2 : upper bounds of approximately 0.64,
0.521, 0.167, and 0.156 are given respectively in [20, 12, 13, 17], the last one provided last
year by Haslegrave, and coming relatively close to McIver and Morgan’s lower bound of
4/27 ≈ 0.148.
In this paper, we prove McIver and Morgan’s conjecture and establish that h = 4/27 is
indeed optimal. Writing Tz for the stabilization time starting from an initial configuration z,
4
we seek to prove that ETz ≤ 27
N 2 . To this end, one of the key ideas is to work with
a Lyapunov function V (z) in lieu of the (more complicated) function ETz . The domain
of the function V is continuous: a domain element describes a configuration in terms of
the distances between adjacent tokens. Combinatorial arguments exploiting the highly
symmetrical structure of V (z) enable us to establish that, for an arbitrary configuration z,
we have ETz ≤ V (z), with equality holding for all three-token configurations. Finally, in
what constitutes the most technically challenging part of this paper, we combine induction
4
on the number of tokens with analytical techniques to show that V is bounded by 27
N 2.
4
2
Taken together, we obtain ETz ≤ 27 N , entailing the Herman-Protocol Conjecture.
The case of there being an even number K of tokens is equally natural from a mathematical
point of view, although it does not correspond to a concrete bit-flipping protocol. It was
established in [13] that the worst-case configuration in this variant is the equidistant two-token
configuration, with an expected stabilization time of 12 N 2 ; the analysis underlying that result
is considerably simpler than what is required in case the number of tokens is odd, as in the
present paper.
© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:2–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

Herman’s protocol is also related to the notion of coalescing random walks [2, 7, 1]. There,
one considers multiple independent random walks on Zd (or on the vertices of a connected
graph). When two walks meet, they coalesce into a new random walk. A protocol for
self-stabilizing mutual exclusion based on such random walks was proposed in [19]. The
expected coalescence time was studied in [6, 24, 5].
It is interesting to note that Herman’s ring is closely related to widely-studied models
of random walks and Brownian motion in statistical physics. Observe that by a simple
modification of the formalism, one may equivalently view Herman’s model as a ring in which
tokens randomly move in discrete step in any direction, with pairwise collisions leading to
annihilation; this precisely corresponds to Fisher’s vicious drunks model [14] (with periodic
boundary conditions). Similar models have been studied in chemical physics [9, 3, 27] and
statistical mechanics [16, 25, 26], among others.
The rest of the paper is organized as follows. In Section 2 we review previous results in
the literature that are relevant to our proof. In Section 3 we outline the structure of our
proof, identifying two key lemmas, Lemma 8 and Lemma 9. Those are proved in Appendix A
and Section 4, respectively.
Another solution of the conjecture, using different techniques, is independently shown
in [8].

2

Relevant Previous Results

For the rest of the paper we fix the number N of processes. We assume that the number K
of tokens is odd, and both N and K are at least 3.
Processes are numbered from 1 to N , clockwise, according to their position in the ring.
A configuration with K tokens is formalized as a function z : {1, . . . , K} → {1, . . . , N } with
z(1) < · · · < z(K), where the ith token (i ∈ {1, . . . , K}) is held by the processor with the
number z(i). We write ZK for the set of configurations with K tokens, and Z for the set of
all possible configurations, that is, Z = Z1 ∪ Z3 ∪ Z5 ∪ . . .
For a fixed initial configuration z = z0 we write (zt )t≥0 for the stochastic process of
configurations emanating from z. The stabilization time Tz is the smallest t ≥ 0 such
that zt ∈ Z1 , i.e., the time until only one token is left. In this paper we focus on the
expectation ETz . It is shown in [22] that if N is odd and a multiple of 3, then there is a
configuration z ∈ Z3 (with the 3 tokens maximally separated in an equilateral triangle) such
4
that ETz = 27
N 2.
In this paper we show:
I Theorem 1. We have ETz ≤

4
2
27 N

for all z ∈ Z.

Equivalently, the Herman conjecture states that for all odd K ≥ 3 and all z ∈ ZK we have
4
ETz ≤ 27
N 2 . Only the case K = 3 was previously known [22].
The following proposition has been used in a similar form in various papers on Herman’s
protocol, for instance in [22, Lemma 5]. It bounds the stabilization time by a Lyapunov
function V .
I Proposition 2 (Bound by a Lyapunov function). Given z ∈ Z, denote by z 0 ∈ Z the random
successor configuration of z. Let V : Z → R be a function with
E(V (z 0 ) | z) ≤ V (z) − 1
0 ≤ V (z)

for all z ∈ Z \ Z1 , and

(1)

for all z ∈ Z1 .

(2)

Then ETz ≤ V (z) for all z ∈ Z. In particular, V (z) ≥ 0 for all z ∈ Z.
© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:3–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

Although this result is not new, we give a short proof based on a martingale argument. The
proof is inspired by [17], and may provide some intuition.
Proof. Let z ∈ Z. Consider the stochastic process (zt )t≥0 of configurations emanating
from z = z0 . Define Wt := V (zt ) + t. By (1) the process (Wt )t≥0 is a supermartingale. The
stabilization time Tz = Tz0 is a stopping time with finite expectation, and the differences
|Wt+1 − Wt | are bounded as the Markov chain reachable from z has finitely many states.
Hence, the optional stopping theorem applies, yielding EWTz ≤ EW0 = V (z). By definition
of Wt we have EWTz = EV (zTz ) + ETz . Since zTz ∈ Z1 , we have ETz ≤ EWTz by (2). By
combining the previous two inequalities, we obtain ETz ≤ V (z).
J
Following [13, 17] we associate with a configuration z ∈ ZK the gap vector g(z) =
(g0 , . . . , gK−1 ) ∈ NK by setting g0 := N + z(1) − z(K), and gi := z(i + 1) − z(i) for
i ∈ {1, . . . , K − 1}. Then g(z)/N lives in the so-called standard (K − 1)-simplex D(K) ,
defined by

D(K) := x = (x0 , . . . , xK−1 ) ∈ [0, 1]K | x0 + · · · + xK−1 = 1 .
(K)

Towards a suitable Lyapunov function V we define the cubic polynomial f3
by
X
(K)
f3 (x) :=
xi0 xi1 xi2 .

: D(K) → [0, ∞)

0≤i0 <i1 <i2 <K
i2 − i1 , i1 − i0 odd
(5)

For instance, we have f3 (x) = x0 x1 x2 + x0 x1 x4 + x0 x3 x4 + x1 x2 x3 + x2 x3 x4 .
The following lemma was implicitly proved in previous works:
I Lemma 3 (Lyapunov function V3 [13, Page 240, Proof of Theorem 1] and [17, Theorem
(K)
4]). Let V3 : Z → [0, ∞) be defined by V3 (z) := 4N 2 f3 (g(z)/N ) for z ∈ ZK . Denote by
0
z ∈ Z1 ∪ Z3 ∪ . . . ∪ ZK the random successor configuration of z ∈ ZK . Then E(V3 (z 0 ) | z) =
(K)
V3 (z) − K−1
for all z ∈ ZK . Hence, by Proposition 2, ETz ≤ 4N 2 f3 (g(z)/N ).
2
(K)

For K = 3 Lemma 3 gives ETz ≤ 4N 2 f3 (g(z)/N ) = N4 g0 g1 g2 . In fact, for K = 3 it was
shown before in [22] that ETz is identically equal to N4 g0 g1 g2 , providing an exact formula
for the expected stabilization time of configurations with three tokens. Lemma 3 suggests
analyzing f3 :
I Lemma 4 (Maximum of f3 [13, Proof of Theorem 2], [17, Theorem 3]). For all K ≥ 3 odd
we have




1
1
1
1
(K)
(K)
max f3 (x) = f3
,...,
=
1− 2 .
x∈D
K
K
24
K
By combining Lemmas 3 and 4 one obtains ETz ≤
in [13]. A slightly better bound is given in [17].

3

N2
1
6 (1 − K 2 ),

which is the bound obtained

Proof of the Herman Conjecture

The function V3 from Lemma 3 leaves room for improvement since E(V3 (z 0 ) | z) = V3 (z)− K−1
2 ,
which is strictly less than V3 (z) − 1 for K > 3. The idea for obtaining an optimal bound
is to decrease the gap between K−1
and 1, by decreasing the Lyapunov function V . One
2
2
could think that the scaled function K−1
V3 is also a Lyapunov function satisfying (1), but
© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:4–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

this is not true; in particular, note that the number of tokens K might be different for a
configuration z and its successor z 0 . Since scaling does not work, we decrease the Lyapunov
function by subtracting a quintic polynomial, as follows. Define a quintic polynomial
(K)
(K)
f5 : D(K) → [0, ∞), similar to f3 :
(K)

f5

X

xi0 xi1 xi2 xi3 xi4
0≤i0 <i1 <···<i4 <K
i4 − i3 , . . . , i1 − i0 odd

(x) =

(3)

(5)

(7)

For instance, f5 (x) = 0, f5 (x) = x0 x1 x2 x3 x4 , and f5 (x) = x0 x1 x2 x3 x4 + x0 x1 x2 x3 x6 +
x0 x1 x2 x5 x6 + x0 x1 x4 x5 x6 + x0 x3 x4 x5 x6 + x1 x2 x3 x4 x5 + x2 x3 x4 x5 x6 . We also define a
polynomial f (K) : D(K) → [0, ∞):
(K)

f (K) (x) := f3

(K)

(x) − αf5

(x)

with α := 24

(3)

For example, f (5) (x) = x0 x1 x2 + x0 x1 x4 + x0 x3 x4 + x1 x2 x3 + x2 x3 x4 − αx0 x1 x2 x3 x4 .
Throughout the paper we use α in the expression of f (K) for notational convenience. From
(K)
now onwards we may drop the superscript K from the domain D(K) of the functions f3 ,
(K)
f5 and f (K) to avoid notational clutter when K is understood.
The following properties of f are fundamental:
I Lemma 5 (Symmetry and continuity properties). The function f has the following properties.
(a) It is symmetric with respect to rotation:
f (x0 , . . . , xK−1 ) = f (x1 , . . . , xK−1 , x0 )
(b) It is continuous: For K ≥ 5 we have
f (K) (x0 , 0, x2 , x3 , . . . , xK−1 ) = f (K−2) (x0 + x2 , x3 , . . . , xK−1 ).
Analogous properties were shown for f3 in [13]. Their proof carries over to f5 and hence to f .
The following lemma uses f to define a tighter Lyapunov function.
I Lemma 6 (Lyapunov function V ). Define V : Z → [0, ∞) by V (z) := 4N 2 f (g(z)/N ). Let
z ∈ Z and denote by z 0 the random successor configuration of z. Then E(V (z 0 ) | z) ≤ V (z)−1.
Hence, by Proposition 2, ETz ≤ 4N 2 f (g(z)/N ).
We remark that a similar Lyapunov function has been investigated in [13, Equation (15)],
but did not lead to a proof of the Herman conjecture. It seems that V (z) needs to be chosen
with great care, since even slight variations do not work.
Lemma 6 suggests analyzing f :
I Lemma 7 (Maximum of f ). For all K ≥ 3 odd we have
max f (K) (x) =
x∈D

1
.
27

With this in hand our main result follows:
Proof of Theorem 1. Immediate by combining Lemmas 6 and 7.

J

It remains to prove Lemmas 6 and 7.
© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:5–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

3.1

Proof of Lemma 6

Towards Lemma 6 we show:
I Lemma 8 (Lyapunov function V5 ). Define V5 : Z → [0, ∞) by V5 (z) := 4N 2 f5 (g(z)/N ).
Let K ≥ 5 and z ∈ Z and denote by z 0 the random successor configuration of z. Then


1 (K − 1)(K − 3) 1
g(z)
−
E(V5 (z 0 ) | z) = V5 (z) +
(K
−
3)f
.
3
32
N2
2
N
The proof in Appendix A requires an analysis of correlations among the changes in gaps
between tokens in each step of the protocol. Using Lemma 8 one can readily prove Lemma 6:
Proof of Lemma 6. For K = 3 the statement follows from Lemma 3. For K ≥ 5 we have:
E(V (z 0 ) | z) = E((V3 (z 0 ) − 24V5 (z 0 )) | z)
0

0

= E(V3 (z ) | z) − 24E(V5 (z ) | z)
K −1
3 (K − 1)(K − 3)
= V3 (z) −
− 24V5 (z) −
2
N2

 4
g(z)
+ 12(K − 3)f3
N


K −1
g(z)
≤ V (z) −
+ 12(K − 3)f3
2
N
K −1 K −3
+
≤ V (z) −
2
2
= V (z) − 1

by the definitions
linearity of expectation

Lemmas 3 and 8
since K ≥ 3
Lemma 4

J

3.2

Proof of Lemma 7

Towards Lemma 7 we show:
I Lemma 9 (Local maxima of f ). Let K ≥ 5 and odd. There is no v ∈ D(K) in the interior
1
of D(K) such that v is a local maximum and f (K) (v) > 27
.
The proof in Section 4 involves a combinatorial analysis of inequalities arising from conditions
on the derivatives of f (K) . Using Lemma 9 one can readily prove Lemma 7:
Proof of Lemma 7. We proceed by induction on K. For the induction base we have K =
(3)
3. It is straightforward to check that the maximum of f (3) (x) = f3 (x) = x0 x1 x2 is
1
f (3) ( 13 , 13 , 13 ) = 27
.
For the induction step we have K ≥ 5. Let v ∈ D(K) with f (K) (v) = maxx∈D(K) f (K) (x).
1
If v is in the interior of D(K) , then by Lemma 9 we have f (K) (v) ≤ 27
. If v is at the
boundary of D(K) , then vi = 0 for some i. By Lemma 5(a) we can assume that v1 = 0.
Using Lemma 5(b) the statement follows from the induction hypothesis.
J

4

Proof of Lemma 9

In this section we prove Lemma 9. In Section 4.1 we state several properties that an interior
local maximum of f (K) would have to satisfy. In Section 4.2 we prove Lemma 9 for K = 5
for a first taste of the general argument. In Section 4.3 we prove Lemma 9 for K = 7 to
illustrate some fine points that occur only for larger values of K. In Section 4.4 we state some
combinatorial facts needed for the general case. Finally, in Section 4.5 we prove Lemma 9.
© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:6–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

4.1

Properties of an Interior Local Maximum

The following lemma is obtained by considering first and second derivatives of f evaluated
at an interior local maximum.
I Lemma 10. Let v be a local maximum of f (K) in the interior of D(K) and define c ∈ R by
X
X
c =
vi 2 − α
vi2 vi3 vi4 .
(4)
1<i2 <K
i2 even

1<i2 <i3 <i4 <K
i2 , i4 even
i3 odd

This expression holds for the same value of c if the indices are rotated by an arbitrary k: for
all j the index ij becomes (ij + k) mod K. Further, we have
X

vi 3 vi 4 ≤

3≤i3 <i4 <K
i3 odd
i4 even

1
.
α

(5)

Again, this inequality also holds when indices are rotated.
For example, for K = 7 we have c = v2 + v4 + v6 − α(v2 v3 v4 + v2 v3 v6 + v2 v5 v6 + v4 v5 v6 ) =
v1 + v3 + v5 − α(v1 v2 v3 + v1 v2 v5 + v1 v4 v5 + v3 v4 v5 ).
Proof of Lemma 10. The idea of the proof is as follows. We pick a particular direction in
D(K) , namely d = (−1, 0, 1, 0, 0, . . . , 0), and consider the function f (v + d) as a univariate
function of . Since v is a local maximum, the first derivative must be zero and the second
derivative must be nonpositive. Exploiting the fact that vi > 0 for all i holds in the interior,
we obtain (4) and (5), respectively. See Appendix B for the detailed proof.
J
(K)

Let Sj
(K)

Sj

(x) denote the scalar product of x with a copy of itself rotated j times:

(x) :=

K−1
X

xi xi+j

i=0

In all formulas it will be the case that the subscript of S is odd. Also, the superscript will be
omitted when unimportant or understood from context.
I Corollary 11. Let v be a local maximum of f (K) in the interior of D(K) . Then the following
inequality holds:
X
1≤i<K−2
i odd

K −i−2
Si (v)
2

≤

K
α

For example, for K = 11 we have 4S1 (v) + 3S3 (v) + 2S5 (v) + S7 (v) ≤ 11/α.
I Lemma 12 (Bound for f5 ). Suppose that v ∈ D(K) satisfies f (K) (v) >
1
216 .
Proof. By Lemma 4 we have f3 (v) ≤
1
216 .

1
24

1
27 .

Then αf5 (v) <

and hence αf5 (v) = f3 (v) − f (v) <

1
24

−

1
27

=
J

© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:7–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

4.2

Proof of Lemma 9 for K = 5

Let K = 5. Then
f (x) = f3 (x) − αf5 (x) = x0 x1 x2 + x0 x1 x4 + x0 x3 x4 + x1 x2 x3 + x2 x3 x4 − αx0 x1 x2 x3 x4
Towards a contradiction, suppose that there is a local maximum v with f (v) >
interior of D. By (4), the value

1
27

in the

c = v2 + v4 − αv2 v3 v4

(6)

is invariant under rotations. Indeed, v2+k + v4+k − αv2+k v3+k v4+k ≡ c for all k, but we
shall avoid explicitly mentioning rotations, for notational simplicity. Summing (6) over all
K rotations we obtain:
5c = 2 − αf3 (v)

(7)

By (6) we have v0 v1 c = v0 v1 v2 + v0 v1 v4 − αf5 (v) and, summing over all K rotations,
cS1 (v) = 2f (v) − 3αf5 (v)

(8)

Moreover,
Cor. 11

cS1 (v)

≤

5c (7) 2
2
=
− f3 (v) =
− f (v) − αf5 (v).
α
α
α

Combining this with (8) gives:
2
α

≥

3f (v) − 2αf5 (v)

Lemma 12

≥

3
1
−2·
27
216

This implies α ≤ 216/11 ≈ 19.6, which is a contradiction as required (since α = 24).

4.3

J

Proof of Lemma 9 for K = 7

Let K = 7. Towards a contradiction, we suppose again that there is a local maximum v
1
with f (v) > 27
in the interior of D. By (4), all K rotations of the following hold with the
same c ∈ R:
c = v2 + v4 + v6 − α(v2 v3 v4 + v2 v3 v6 + v2 v5 v6 + v4 v5 v6 )

(9)

Summing (9) over K rotations we obtain:
7c = 3 − 2αf3 (v)

(10)

By (9) we have
v0 v1 c = v0 v1 v2 +v0 v1 v4 +v0 v1 v6 −α(v0 v1 v2 v3 v4 +v0 v1 v2 v3 v6 +v0 v1 v2 v5 v6 +v0 v1 v4 v5 v6 ) (11)
and
v0 v3 c = v0 v3 v4 + v0 v3 v6 − αv0 v3 v4 v5 v6 + v0 v2 v3 (1 − α(v3 v4 + v3 v6 + v5 v6 ))
≥ v0 v3 v4 + v0 v3 v6 − αv0 v3 v4 v5 v6

(12)

where the last inequality is by (5). Summing (11) and (12) over K rotations we obtain:

c 2S1 (v) + S3 (v) ≥ 4f3 (v) − 9αf5 (v) = 4f (v) − 5αf5 (v)
(13)
© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:8–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

Further we have:

c 2S1 (v) + S3 (v)

Cor. 11

≤

7c (10) 3
3
=
− 2f3 (v) =
− 2f (v) − 2αf5 (v)
α
α
α

Combining this with (13) gives:
3
α

≥

6f (v) − 3αf5 (v)

6
1
−3·
27
216

Lemma 12

≥

This leads to α ≤ 14.4, which is a contradiction as desired.

4.4

J

Combinatorial Lemmas

In order to generalize the proofs from Sections 4.2 and 4.3 to any odd K, we state some
combinatorial lemmas in this subsection. They are proved in Appendix C.
In order to generalize (7) and (10) we show the following lemma:
I Lemma 13. We have:
K−1
X

X

xi00 +k xi01 +k xi02 +k =

k=0 1<i00 <i01 <i02 <K
i00 , i02 even
i01 odd

K −3
2

X

xi0 xi1 xi2 =

0≤i0 <i1 <i2 <K
i2 − i1 , i1 − i0 odd

K − 3 (K)
f3 (x)
2

For example, if K = 5, then we obtain that summing the 5 rotations of x2 x3 x4 gives
(5)
f3 (x). As another example, if K = 7, then we obtain that summing the 7 rotations of
(7)
x2 x3 x4 + x2 x3 x6 + x2 x5 x6 + x4 x5 x6 gives 2f3 (x). These two instances of Lemma 13 help
establish (7) and (10).
In order to generalize the inequality in (12) we need the following lemma:
I Lemma 14. Let v be a local maximum of f (K) in the interior of D(K) . If i1 is odd and
0 < i1 < K, then the following inequality holds:
 X

 X

X
X
v0 vi 1
vi 2 −
αvi2 vi3 vi4 ≥ v0 vi1
vi 2 −
αvi2 vi3 vi4
1<i2 <K
i2 even

1<i2 <i3 <i4 <K
i2 , i4 even
i3 odd

i1 <i2 <K
i2 even

i1 <i2 <i3 <i4 <K
i2 , i4 even
i3 odd
(K)

(K)

The inequality says that if we drop those terms that do not occur in f3 or f5 , then we
(K)
(K)
obtain a lower bound. The proof groups those terms that are not in either of f3 or f5 ,
and then invokes (5) to show that their sum is nonnegative.
In order to generalize (8) and (13) we need Corollary 16 below, which is a consequence of
the following lemma:
I Lemma 15. Let l be an odd, positive integer. Then:
K−1
X
k=0

X
1≤i01 <K−2
i01 odd

K − i01 − 2
2
0

X

xk xi01 +k

i1 <i02 <···<i0l−1 <K
∀j, i0j ≡j (mod 2)

Y

xi0j +k =

1<j<l

=

l − 1
2

K−l



X

l−1
Y

xij

j=0
0≤i0 <···<il−1 <K
ij − ij−1 odd for 0 < j < l

© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:9–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

For example, if K = 5 and l = 3, then we have that summing 5 rotations of x0 x1 x2 + x0 x1 x4
(5)
gives 2f3 (x). As another example, if K = 9 and l = 3, then summing 9 rotations of
(9)
3x0 x1 (x2 + x4 + x6 + x8 ) + 2x0 x3 (x4 + x6 + x8 ) + x0 x5 (x6 + x8 ) gives 6f3 (x).
I Corollary 16. We have:
K−1
X

X

k=0 1≤i1 <K−2
i1 odd

K − i1 − 2
2

(K)

X

x0+k xi1 +k xi2 +k = (K − 3)f3

(x)

i1 <i2 <K
i2 even

and also
K−1
X

X

k=0 1≤i1 <K−2
i1 odd

K − i1 − 2
2

(K)

X

x0+k xi1 +k xi2 +k xi3 +k xi4 +k = (2K − 5)f5

Proof. Instantiate Lemma 15 with l = 3 and, respectively, l = 5.

4.5

(x)

i1 <i2 <i3 <i4 <K
i2 , i4 even
i3 odd

J

Proof of Lemma 9

1
Towards a contradiction, suppose that there is a local maximum v with f (v) > 27
in the
interior of D, i.e., vi > 0 for all i ∈ {0, . . . , K − 1}. Summing up the K rotations of (4) and
using Lemma 13, we obtain:

K −1 K −3
−
αf3 (v)
2
2
P
Multiplying (4) on both sides by 1≤i1 <K−2
Kc =

i1 odd

X

c

1≤i1 <K−2
i1 odd

K − i1 − 2
v0 vi 1 =
2

≥

X
1≤i1 <K−2
i1 odd

X
1≤i1 <K−2
i1 odd

(14)
K−i1 −2
v0 vi 1
2

we obtain:

K − i1 − 2
v0 vi1
2

K − i1 − 2
v0 vi 1
2

!
X

vi 2 −

X

αvi2 vi3 vi4
1<i2 <i3 <i4 <K
i2 , i4 even
i3 odd

1<i2 <K
i2 even

!
X

vi 2 −

i1 <i2 <K
i2 even

X

αvi2 vi3 vi4
i1 <i2 <i3 <i4 <K
i2 , i4 even
i3 odd

using Lemma 14. Summing K rotations of this inequality yields:
c

X

1≤i1 <K−2
i1 odd

K − i1 − 2
Si1 (v) ≥ (K − 3)f3 (v) − (2K − 5)αf5 (v) = (K − 3)f (v) − (K − 2)αf5 (v).
2
(15)

using Corollary 16. Further we have:
c

X
1≤i1 <K−2
i1 odd

K − i1 − 2
Si1 (v)
2

Cor. 11

≤

Kc (14) K − 1 K − 3
=
−
f3 (v)
α
2α
2

Combining this with (15) gives:
K −1
3K − 9
K −1
≥
f (v) −
αf5 (v)
2α
2
2

Lemma 12

≥

K −3 1 K −1 1
· −
·
2
9
2
216

© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:10–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

This implies
α≤

216(K − 1)
< 19.7
23K − 71

Since α = 24, this leads to a contradiction as desired.

5

J

Conclusions

In this paper we have proved the Herman-Protocol Conjecture formulated by McIver and
Morgan in [22] a decade ago, which says that the worst-case initial configuration consists of
three maximally-separated tokens, for N multiple of 3. This follows from our result that the
4
worst-case self-stabilization time is at most 27
N 2 , for any number of processes N and any
odd number of tokens K.
The proof uses a Lyapunov function approach. To do so, we first find a suitable Lyapunov
4
function and then show that its maximum is 27
N 2 . Then we show that this function gives
an upper bound for the self-stabilization time for each possible configuration in Herman’s
algorithm.
Acknowledgements Stefan Kiefer is supported by a University Research Fellowship of the
Royal Society and by EPSRC grant EP/M003795/1. Joël Ouaknine is supported by ERC
grant AVS-ISS (648701).
References
1

2
3
4
5
6
7
8
9
10
11
12
13
14

D. Aldous and J. A. Fill. Reversible Markov chains and random walks on graphs, 2002.
Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/
~aldous/RWG/book.html.
R. Arratia. Limiting point processes for rescalings of coalescing and annihilating random
walks on Z d . The Annals of Probability, 9(6):909–936, 1981.
D. Balding. Diffusion-reaction in one dimension. J. Appl. Prob., 25:733–743, 1988.
PRISM case studies. Randomised self-stabilising algorithms.
http://www.prismmodelchecker.org/casestudies/self-stabilisation.php.
C. Cooper, R. Elsässer, H. Ono, and T. Radzik. Coalescing random walks and voting on
graphs. In Proc. PODC, pages 47–56. ACM, 2012.
D. Coppersmith, P. Tetali, and P. Winkler. Collisions among random walks on a graph.
SIAM Journal on Discrete Mathematics, 6(3):363–374, 1993.
J.T. Cox. Coalescing random walks and voter model consensus times on the torus in Z d .
The Annals of Probability, 17(4):1333–1366, 1989.
E. Csóka and S. Mészáros. Generalized solution for the Herman protocol conjecture. Technical report, arxiv.org, 2015. Available at http://arxiv.org/abs/1504.06963.
P.-G. de Gennes. Soluble model for fibrous structures with steric constraints. J. Chem.
Phys., 48(5):2257–2259, 1968.
E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. Comm. ACM,
17(11):643–644, 1974.
S. Dolev. Self-Stabilization. MIT Press, 2000.
Y. Feng and L. Zhang. A Tighter Bound for the Self-Stabilization Time in Herman’s
Algorithm. Inf. Process. Lett., 113(13):486–488, 2013.
Y. Feng and L. Zhang. A nearly optimal upper bound for the self-stabilization time in
Herman’s algorithm. Dist. Comp., pages 1–12, 2015.
M. E. Fisher. Walks, walls, wetting, and melting. J. Stat. Phys., 34(5-6):667–729, 1984.

© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:11–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

15
16
17
18
19
20
21
22
23
24
25
26

27

L. Fribourg, S. Messika, and C. Picaronny. Coupling and self-stabilization. Dist. Comp.,
18:221–232, 2005.
S. Y. Grigoriev and V. B. Priezzhev. Random walk of annhilating particles on the ring.
Theor. Math. Phys., 146(3):411–420, 2006.
J. Haslegrave. Bounds on Herman’s algorithm. Theoretical Computer Science, 550:100–06,
2014.
T. Herman. Probabilistic self-stabilization. Inf. Process. Lett., 35(2):63–67, 1990.
A. Israeli and M. Jalfon. Token management schemes and random walks yield selfstabilizing mutual exclusion. In Proc. PODC, pages 119–131. ACM, 1990.
S. Kiefer, A. Murawski, J. Ouaknine, J. Worrell, and L. Zhang. On stabilization in Herman’s
algorithm. In Proc. ICALP, volume 6756 of LNCS. Springer, 2011.
L. Lamport. Solved problems, unsolved problems and non-problems in concurrency. In
Proc. PODC, pages 1–11. ACM, 1984.
A. McIver and C. Morgan. An elementary proof that Herman’s ring is Θ(N 2 ). Inf. Process.
Lett., 94(2):79–84, 2005.
T. Nakata. On the expected time for Herman’s probabilistic self-stabilizing algorithm.
Theor. Comput. Sci., 349(3):475–483, 2005.
R.I. Oliveira. On the coalescence time of reversible random walks. Trans. Amer. Math.
Soc., 364(4):2109–2128, 2012.
J. Rambeau and G. Schehr. Distribution of the time at which N vicious walkers reach their
maximal height. Phys. Rev. E, 83, 2011.
G. Schehr, S. N. Majumdar, A. Comtet, and P. J. Forrester. Reunion probability of N
vicious walkers: Typical and large fluctuations for large N . J. Stat. Phys., 150:491–530,
2013.
M. Warner. Aggregation in dense solutions of rods. J. Chem. Soc. Faraday. Trans.,
87(6):861–867, 1991.

© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:12–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

A

Proof of Lemma 8

Let z : {1, . . . , K} → {1, . . . , N } be a K-token configuration on a ring with N processes.
Recall that the associated gap vector g(z) = (g0 , . . . , gK−1 ) ∈ NK is defined by g0 :=
N + z(1) − z(K) and gi := z(i + 1) − z(i) for i = 1, . . . , K − 1.
Given z, consider the gap-increment vector ∆ := g(z 0 ) − g(z), where z 0 is the random
successor configuration of z. This is a random variable taking values in {−1, 0, +1}K where,
for each i ∈ {0, . . . , K − 1}, ∆i = 0 with probability 1/2 (the two tokens adjacent to the i-th
gap both stay or both move clockwise), and ∆i = ±1 with probability 1/4 (one token stays
and the other moves clockwise).
We will need the following two properties (16) and (17) concerning the expectation of
the random variable ∆. First, it is straightforward to verify by direct calculation that for
0 ≤ k < K,
(
0
if k is even

E(∆i ∆i+1 . . . ∆i+k ) =
(16)
1 (k+1)/2
−4
if k is odd
Secondly, suppose that 0 ≤ i1 ≤ i2 < i3 ≤ i4 < K, with i3 6≡ i2 + 1 and i1 6≡ i4 + 1 modulo
K, that is, {i1 , . . . , i2 } and {i3 , . . . , i4 } form two non-adjacent intervals (treating K − 1 and
0 as adjacent). Then
E(∆i1 . . . ∆i2 ∆i3 . . . ∆i4 ) = E(∆i1 . . . ∆i2 )E(∆i3 . . . ∆i4 ) .

(17)

because ∆i1 , . . . , ∆i2 and ∆i3 , . . . , ∆i4 are determined by the movements of disjoints sets of
tokens, and hence are independent.
For a given configuration z we want to compute E[f5 (g(z) + ∆)]. From the definition of
f5 and the linearity of expectation, this is a sum of expressions of the form
E(gi0 + ∆i0 )(gi1 + ∆i1 )(gi2 + ∆i2 )(gi3 + ∆i3 )(gi4 + ∆i4 )

(18)

over the set of indices 0 ≤ i0 < i1 < i2 < i3 < i4 < K of alternating parity.
Expression (18) evaluates to a degree-5 polynomial in the variables g. Observe that
this polynomial has no monomials of even degree. For example, all degree-2 monomials
have coefficients of the form E(∆i ∆j ∆k ) with i < j < k. These coefficients are zero by
(16) and (17). Degrees 0 and 4 are proved similarly.
There is a single degree-5 monomial in (18)—namely gi0 . . . gi4 . Summing all such terms
over indices 0 ≤ i0 < i1 < i2 < i3 < i4 < K of alternating parity yields f5 (g(z)).
Expanding the expression (18) yields degree-3 monomials of the form
gj0 gj1 gj2 E(∆j3 ∆j4 )
for distinct indices j0 < j1 < j2 . The coefficient of such a term is −1/4 if j4 ≡ j3 + 1
or j3 ≡ j4 + 1 and 0 otherwise. Moreover, if j0 , j1 , j2 have alternating parity there are
(K − 3)/2 choices of j3 such that gj0 gj1 gj2 E(∆j3 ∆j3 +1 ) appears in (18). If j0 , j1 , j2 do not
have alternating parity then there are no such terms in (18). We conclude that the sum of
all degree-3 monomials in E(f5 (g(z) + ∆) is
−

(K − 3)
f3 (g(z)) .
8

Finally, consider the degree-1 monomials. These have the form
gj0 E(∆j1 ∆j2 ∆j3 ∆j4 )
© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:13–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

for distinct indices j0 and j1 < j2 < j3 < j4 . By Property (17), such terms are only non-zero
if {j1 , j2 , j3 , j4 } comprises either a single block of adjacent indices or two non-adjacent blocks
of length 2 (considering K − 1 and 0 to be adjacent). In this case E(∆j1 ∆j2 ∆j3 ∆j4 ) = 1/16,
and there are (K−1)/2
= (K − 1)(K − 3)/8 such choices of {j1 , j2 , j3 , j4 } for each choice of
2
j0 . Thus gj0 has total coefficient (K − 1)(K − 3)/128 in E(f5 (g(z) + ∆)). Moreover, since
g0 + . . . + gK−1 = N , the degree-1 terms in E(f5 (g(z) + ∆)) sum to N (K − 1)(K − 3)/128.
In summary, we have proved:
I Proposition 17. For each K-token configuration z,
E(f5 (g(z) + ∆)) = f5 (g(z)) −

K −3
(K − 1)(K − 3)N
f3 (g(z)) +
.
8
128

Lemma 8 follows immediately from Proposition 17 by scaling, since V5 (z) = 4N 2 f5 (g(z)/N ) =
is a linear multiple of f5 (g(z)).

4
N 3 f5 (g(z))

B

Proofs of Properties of an Interior Local Maximum

Lemma 10. Let v be a local maximum of f (K) in the interior of D(K) and define c ∈ R by
X
X
c =
vi 2 − α
vi 2 vi 3 vi 4 .
(19)
1<i2 <K
i2 even

1<i2 <i3 <i4 <K
i2 , i4 even
i3 odd

This expression holds for the same value of c if the indices are rotated by an arbitrary k: for
all j the index ij becomes (ij + k) mod K. Further, we have
X

vi3 vi4 ≤

3≤i3 <i4 <K
i3 odd
i4 even

1
α

(20)

Again, this inequality also holds when indices are rotated.
Proof. We consider the second-order Taylor expansion of f (K) along the direction d =
(−1, 0, 1, 0, . . . , 0) (which is tangent to D(K) ):
f (K) (x + d) = f (K) (x) + Q(x) + 2 R(x) + O(3 ) .
Since v is a local maximum, we have Q(v) = 0 and R(v) ≤ 0. Proving (19) boils down to
calculating Q(x); proving (20) boils down to calculating R(x).
First, we prove (19). Let
f (K) (x0 + , x1 , . . . , xK−1 ) = f (K) (x) + P (x) + O(2 ).
By the chain rule and using the rotational symmetry of f (K) (Lemma 5(a)), we find that
Q(x0 , . . . , xK−1 ) = P (x0+2 , x1+2 , . . . , xK−1+2 ) − P (x0 , x1 , . . . , xK−1 ).
Now recall the definition of f (K) :
X
f (K) (x) :=
xi0 xi1 xi2 −
0≤i0 <i1 <i2 <K
i2 − i1 and i1 − i0 odd

X

αxi0 xi1 xi2 xi3 xi4
0≤i0 <···<i4 <K
i4 − i3 , . . . , i1 − i0 all odd

(21)

© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:14–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

We differentiate f (K) with respect to x0 to obtain
X

P (x) =

x i1 x i2 −

X

αxi1 xi2 xi3 xi4 .
0<i1 <···<i4 <K
i1 , i3 odd
i2 , i4 even

0<i1 <i2 <K
i1 odd
i2 even

(22)

Since v is a local maximum, Q(v) = 0 and we have
X

X

vi1 vi2 −

0<i1 <i2 <K
i1 odd
i2 even

X

αvi1 vi2 vi3 vi4 =

0<i1 <···<i4 <K
i1 , i3 odd
i2 , i4 even

vi1 +2 vi2 +2 −

X

αvi1 +2 vi2 +2 vi3 +2 vi4 +2
0<i1 <···<i4 <K
i1 , i3 odd
i2 , i4 even

0<i1 <i2 <K
i1 odd
i2 even

Observe that the monomials not containing v1 cancel each other out. Dividing by v1 = v1+K
(since v1 > 0), we have
X
vi 2 −

X

αvi2 vi3 vi4 =

1<i2 <K 1<i2 <i3 <i4 <K
i2 even
i3 odd
i2 , i4 even

X

vi1 +2 −

0<i1 <K−1
i1 odd

X

αvi1 +2 vi2 +2 vi3 +2
0<i1 <i2 <i3 <K−1
i1 , i3 odd
i2 even

Now we observe that the right hand side can be obtained from the left hand side by changing
each index i into i + 1. Taking into account rotations of the above equality, we conclude (19).
Next, we prove (20). To do so, we first calculate the terms of order 2 of f (K) (x + d).
Such terms occur only when i0 = 0, i1 = 1, and i2 = 2. In this case, the first sum reduces to
(x0 − )x1 (x2 + ), and the second sum reduces to
α(x0 − )x1 (x2 + )

X

x i3 x i4 .
2<i3 <i4 <K
i3 odd, i4 even

Thus,
R(x) = −x1 + αx1

X

xi3 xi4 .
2<i3 <i4 <K
i3 odd, i4 even

Since the assumed interior local maximum v is in the interior of D(K) , we have that v1 > 0,
and so the condition R(v) ≤ 0 is equivalent to R(v)/v1 ≤ 0:
−1 +

X

αvi3 vi4
2<i3 <i4 <K
i3 odd, i4 even

≤0

Up to trivial rearrangement, we obtained (20).

J

Corollary 11.
Let v be a local maximum of f (K) in the interior of D(K) . Then the
following inequality holds:
X
1≤i<K−2
i odd

K −i−2
Si (v)
2

≤

K
α

© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:15–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

Proof. We sum (20) over all K rotations:
K−1
X
K
≥
α
i=0

=

X

Si (v) =

3≤i3 <i3 +i<K
i odd, i3 odd

K−1
X

vi3 +i vi4 +i =

3≤i3 <i4 <K i=0
i3 odd
i4 even

3≤i3 <i4 <K
i3 odd
i4 even

X

X

vi3 +i vi4 +i =

X

X

Si (v) =

1≤i 3≤i3 <K−i
i odd i3 odd

X

Si4 −i3 (v)

3≤i3 <i4 <K
i3 odd
i4 even

X
1≤i<K−2
i odd

K −i−2
Si (v)
2
J

C

Proofs of Combinatorial Lemmas

We repeat the combinatorial facts of Section 4.4, this time with proofs.
Lemma 13. We have:
K−1
X

X

xi00 +k xi01 +k xi02 +k =

k=0 1<i00 <i01 <i02 <K
i00 , i02 even
i01 odd

K −3
2

X

xi0 xi1 xi2 =

0≤i0 <i1 <i2 <K
i2 − i1 , i1 − i0 odd

K − 3 (K)
f3 (x)
2

Proof. Let us fix 0 ≤ i0 < i1 < i2 < K such that both i2 − i1 and i1 − i0 are odd. We
want to show that the term xi0 xi1 xi2 occurs (K − 3)/2 times in each side of the equality.
The middle and right sides are trivial; it remains to check the left side. Let us now fix an
arbitrary k. For a term on the left hand side to equal xi0 xi1 xi2 , it must be that the sets
{(i00 + k) mod K, (i01 + k) mod K, (i02 + k) mod K} and {i0 , i1 , i2 } are equal. In other words,
once i0 , i1 , i2 , k are fixed, the set {i00 , i01 , i02 } is uniquely determined. Since, i00 < i01 < i02 , the
potential values of i00 , i01 , i02 are also uniquely determined. The remaining question is for how
many k ∈ {0, . . . , K − 1} it is the case that the values i00 , i01 , i02 so determined obey the other
constraints.
There are three disjoint cases: The smallest value in the set {i00 , i01 , i02 }, namely i00 , is
(i0 − k) mod K or (i1 − k) mod K or (i2 − k) mod K. The case i00 = (i1 − k) mod K occurs
exactly when (a) i0 < k < i1 , and (b) k has the same parity as i1 . Let δ0 denote the size of
the gap between i0 and i1 . Then, there are (δ0 − 1)/2 values of k that obey both (a) and (b).
The other two cases are similar, and so we conclude that the term xi0 xi1 xi2 occurs on the
left hand side
δ0 − 1 δ1 − 1 δ2 − 1
K −3
+
+
=
2
2
2
2
J

times.

Lemma 14. Let v be a local maximum of f (K) in the interior of D(K) . If i1 is odd and
0 < i1 < K, then the following inequality holds:
 X
 X


X
X
v0 vi 1
vi 2 −
vi 2 −
αvi2 vi3 vi4 ≥ v0 vi1
αvi2 vi3 vi4
1<i2 <K
i2 even

1<i2 <i3 <i4 <K
i2 , i4 even
i3 odd

i1 <i2 <K
i2 even

i1 <i2 <i3 <i4 <K
i2 , i4 even
i3 odd

© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:16–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

Proof. The proof below is a case analysis of where i1 can be inserted in-between 0 < i2 <
i3 < i4 < K. As noted before, the task is to show that retaining the terms that occur in f5
gives a lower bound. In other words, we want to show that those terms not occurring in f5
have a positive sum. We calculate this sum:
X
X
v0 vi2 vi1 −
αv0 vi2 vi1 vi3 vi4
1<i2 <i1
i2 even

X

=

1<i2 <i3 <i4 <K
i2 <i1



1<i2 <i1
i2 even

X

≥

X

v0 vi2 vi1 1 −

αvi3 vi4



i2 <i3 <i4 <K
i3 odd, i4 even


v0 vi2 vi1 1 −

1<i2 <i1
i2 even

X

αvi3 vi4

by (5)



≥

0

3≤i3 <i4 <K
i3 odd, i4 even

J
Lemma 15. Let l be an odd, positive integer. Then:
K−1
X

X

k=0 1≤i01 <K−2
i01 odd

K − i01 − 2
2
0

X

xk xi01 +k

i1 <i02 <···<i0l−1 <K
∀j, i0j ≡j (mod 2)

Y

xi0j +k =

1<j<l

=

l − 1
2

K−l



X

l−1
Y

xij

j=0
0≤i0 <···<il−1 <K
ij − ij−1 odd for 0 < j < l

The proof is similar to that of Lemma 13.
Proof. Let us fix 0 ≤ i0 < · · · < il−1 < K with odd gaps in-between. We want to show that
the term xi0 . . . xil−1 occurs (l − 1)K/2 − l times on each side of the equation. For the right
side, it is trivial. The general form of a term on the left side is xk xi01 +k xi02 +k . . . xi0l−1 +k . It
must be that k is one of i0 , . . . , il−1 . Let us consider the case k = i0 ; the others are similar.
If k = i0 , then, in fact,
(k, i01 + k, i02 + k, . . . , i0l−1 + k) mod K

=

(i0 , i1 , . . . , il−1 ).

In particular, i01 equals the size of the gap between i0 and i1 . Let us denote this gap by δ0 .
On the left hand side, the term is multiplied by (K − i01 − 2)/2, which is (K − δ0 − 2)/2. The
cases k = i1 , k = i2 , . . . are similar. Because δ0 + · · · + δl−1 = K, we conclude that the term
xi0 . . . xil−1 occurs
K − δl−1 − 2
l−1
K − δ0 − 2
+ ··· +
=
K −l
2
2
2
times on the left side.

J

© Maria Bruna and Radu Grigore and Stefan Kiefer and Joël Ouaknine and James Worrell;
licensed under Creative Commons License CC-BY
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016).
Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi; Article No. XXX;
pp. XXX:17–XXX:17
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

