Generalized solution for the Herman Protocol Conjecture

Abstract

The Herman Protocol Conjecture states that the expected time $\mathbb{E}(\mathbf{T})$ of Herman's self-stabilizing algorithm in a system consisting of $N$ identical processes organized in a ring holding several tokens is at most $\frac{4}{27}{N}^2$. We prove the conjecture in its standard unbiased and also in a biased form for discrete processes, and extend the result to further variants where the tokens move via certain Lévy processes. Moreover, we derive a bound on the expected value of $\mathbb{E}(\hat{I}{\pm }^{\mathbf{T}})$ for all $1\le \hat{I}\pm \le (1-\epsilon {)}^{-1}$ with a specific $\epsilon >0$. Subject to the correctness of an optimization result that can be demonstrated empirically, all these estimations attain their maximum on the initial state with three tokens distributed equidistantly on the ring of $N$ processes. Such a relation is the symptom of the fact that both $\mathbb{E}(\mathbf{T})$ and $\mathbb{E}(\hat{I}{\pm }^{\mathbf{T}})$ are weighted sums of the probabilities $\mathbb{P}(\mathbf{T}\ge t)$.

18 pages, 2 figures, extended and improved version