RIP Herman Conjecture (2005-2015)

In 1990, Herman proposed a sweet self-stabilizing protocol. In 2005, McIver and Morgan conjectured that its running time is $\frac{4}{27} N^2$. Well … they were right.

Do you remember playing tag as a kid? What about hide-and-seek? Of course you do. In these games one kid is special: the one running after others in tag, or the seeker in hide-and-seek. (Although ‘unlucky’ would perhaps be a better word.) The game usually has rules for picking this kid. For example, the seeker is the person first found on the previous round of the game. The problem is that these rules don't apply to the first round. To pick the first seeker (or the first tagger) kids sit around in a circle and perform a well known ritual: They repeatedly recite a chant, for each syllable pointing to the next kid in the circle. Whoever gets the last syllable is out of the circle. The last person to remain is the chosen special person. This algorithm has an obvious problem: You have to choose where you start pointing in the first place, and once you do that the outcome is completely determined. Thus, all appearance of randomness is illusory. It only appears random because the outcome is somewhat hard to figure out quickly. But not impossible: Josephus was able to do it.

It's possible to do better, using a sweet little algorithm of Herman. Kids start standing in a circle, as before. Some of them (maybe all) have chocolate coins. On each round, all kids with chocolate coins throw them. If they get heads, they have to pass the coin to the left. If they get tails, they get to keep the coin. And here comes the sweet part: If a kid has two coins, THEY GET TO EAT THEM! Anyway, since coins only get eaten in pairs, at some point only one coin will be left if you started with an odd number of coins. The kid that holds this last coin is chosen as the seeker (or the tagger).

Obviously, the outcome is random and unpredictable, because it depends on the coin tosses. But, how long does this take? In 1990, Herman showed that the expected time is $O(N^2 \log N)$, where $N$ is the number of kids. (This is independent of the number of chocolate coins you started with. The initial number of chocolate coins could be any odd number $3\le K\le N$.) In 2004, Fribourg et al. improved the upper bound to $2N^2$. In 2005, Nakata improved the upper bound to $0.936 N^2$. Also in 2005, McIver and Morgan showed that the upper bound needs to be $\ge\frac{4}{27}N^2$, and conjectured that it is $\frac{4}{27}N^2$. Subsequently, various papers showed upper bounds of $0.64N^2$, $0.521N^2$, $0.167N^2$, and $0.156N^2$. Now we know that McIver and Morgan were right:

Maria Bruna, Radu Grigore, Stefan Kiefer, Joel Ouaknine, and James Worrell, Proving the Herman-Protocol Conjecture, 2015

Here's how the proof goes.

First, we describe configurations of chocolates by the distances between them. For example, $(1,2,3,4,2,3,1)$ describes the following situation:

The chocolate is brown and the arrow on the right shows from where we start. We call these numbers gaps $(g_0,\ldots,g_6)$, and their sum is $N=16$, the number of kids. After we normalize them so their sum is $1$, we just call them ‘ex’: In this case $(x_0,\ldots,x_6)= \bigl(\frac{1}{16},\frac{2}{16},\frac{3}{16},\frac{4}{16}, \frac{2}{16},\frac{3}{16},\frac{1}{16}\bigr)$. Then we define the function $$ f(x_0,\ldots,x_{K-1}) = \hskip-1em \sum_{\substack{ 0\le i_0\lt i_1\lt i_2\lt K\\ \text{$i_2-i_1$ and $i_1-i_0$ odd}}} \hskip-2em x_{i_0} x_{i_1} x_{i_2} - \hskip-1em \sum_{\substack{ 0\le i_0\lt i_1\lt i_2\lt i_3\lt i_4\lt K\\ \text{$i_4-i_3, \ldots, i_1-i_0$ all odd}}} \hskip-2em 24 x_{i_0} x_{i_1} x_{i_2} x_{i_3} x_{i_4} $$ and show that $4 N^2 f(x_0,\ldots,x_{K-1})$ is an upper bound for the expected stabilization time if the initial configuration is described by $(x_0,\ldots,x_{K-1})$. Finally, we show that in the simplex $$ D \;=\; \{\,(x_0,\ldots,x_{K-1}) \mid \text{$x_0+\cdots+x_{K-1}=1$ and $x_0,\ldots,x_{K-1}\ge0$}\,\} $$ the maximum of $f$ is $1/27$: $$ \max_{{\bf x}\in D} f({\bf x}) = \frac{1}{27} $$

This last part is trickier than it may seem. For details, see the paper.