03 April 2015

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.


Lothar Kiefer said...

It is obvious that kids need better rules for the beginning of their games. As pointed out, the well known method of syllable pointing is not random. So the kids introduce stochastic influences. The chant „ene-mene-muh-and-out-are-you“ (7 pointings) also can be used in the form „e-ne-me-ne-muh-and-out-are-you“ (9 pointings) ( https://www.youtube.com/watch?v=mBFfFPGedLs ). By these two possibilities the result of the ritual is not predictable, but the probability to be the first seeker or the first tagger is not equal to all kids.
Unfortunately the method of Herman is not much better. In most cases, it doesn´t provide an equal probability to all kids.
So in the interest of all kids in the world, Maria Bruna, Radu Grigore, Stefan Kiefer, Joel Ouaknine, and James Worrell should continue and improve their efforts to create a method of equal probabilities with an expected time not longer than 4/27*N*N.

Radu Grigore said...

Thanks, Lothar! I'll make sure everyone knows we still have work to do.

Stefan Kiefer said...

If every kid starts with a chocolate coin, the protocol gives every kid the same chance. If there is an even number of kids, then the number of chocolate coins is even and Herman's protocol no longer works. But one could modify it as follows: if a kid has two chocolate coins, only one coin is eaten. This works for any number of kids, but I'm not sure about the expected runtime.

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.