Herman 随机自稳定令牌环

形式陈述

Herman协议在没有特殊根的同步奇数环上实现随机自稳定。固定奇数n≥3，节点按0到n−1编号，每个节点保存一个比特x[i]，读取自己与前驱的本轮旧值。若 $x[i]=x[i-1]$ ，节点i持有一枚逻辑令牌。

本页采用“无令牌者保持比特”的表示：

text

每一同步轮，所有节点读取旧配置后同时更新：
  若x[i] != x[i-1]：保持x[i]
  若x[i] == x[i-1]：
    独立掷公平硬币
    以1/2概率翻转x[i]，以1/2概率保持

各次硬币是相互独立的Bernoulli(1/2)选择。令牌节点翻位相当于把令牌传给后继，保持相当于留在原位；一个留下的令牌与前驱传来的令牌相遇时，两枚一起消失。合法集L为恰有一枚令牌的全部比特配置。

同步旧值与同时更新是定义的一部分。逐个更新数组却让后面的节点读取前面刚改的新值，不是这份协议。文献和工具中另有每轮对全部比特再取反的等价令牌表示，其非令牌节点会复制前驱；不能把两种位规则各抽一半组合。

直觉

环上的比特不直接表示令牌，相等边界才表示。沿闭环走一圈，比特改变次数必为偶数；n为奇数，因此相等边界数n减去偶数仍是奇数，至少为1。

每枚令牌独立选择留或向前一步。它们不会分裂，也不会凭空增加；相撞只删除两枚。因此令牌总数始终为正奇数，可能从5降到3再降到1，却不会降到0。

达到一枚令牌以后仍继续运行。它可暂留，也可前进，合法集保持闭包。所谓“稳定时间”是首次进入单令牌集合的时间，不是程序停止执行的时间。

例子与边界

从x=00000开始，每个相邻比特都相同，令牌位于{0,1,2,3,4}。第一轮只让节点0翻位，其余令牌节点保持，得到10000；令牌位于{2,3,4}。原节点0的令牌前进到1，与1留下的令牌一起消失。

第二轮只有节点2、3、4掷币；让2翻位，3、4保持，无令牌的0、1保持旧位，得到10100。此时只有节点4与其前驱3的比特相等，剩下一枚令牌。

第一轮指定结果概率为 $2^{-5}$ ，第二轮为 $2^{-3}$ ，这条两轮恢复轨迹概率为 $2^{-8}$ 。它只是一个正概率见证，不是所有硬币结果都会两轮恢复。例如每轮都让所有令牌保持，坏配置可以一直不变。

三比特环只有000和111含三枚令牌，其余六个配置都含一枚。在000或111中，三节点本轮都独立随机选择保持或翻位，八个新配置等概率。因此一轮以6/8=3/4的概率稳定，以2/8=1/4的概率仍留在三令牌集合。

令T为从000开始首次稳定所需轮数，则

\Pr(T>t)=4^{-t},\qquad \mathbb E[T]=1+\tfrac14\mathbb E[T]=\tfrac43.

所以对任意有限t，仍有正概率尚未稳定，没有固定最坏轮数；但永不稳定的概率为 $\lim_{t\to\infty}4^{-t}=0$ 。期望4/3轮也不意味着每条轨迹至多两轮。

从任意多令牌配置，选择沿前进方向相邻的两枚令牌，让前一枚持续前进，后一枚及其他令牌保持。至多n轮，两枚就相遇湮灭；这个有限硬币安排具有正概率。重复至多(n−1)/2次，可到单令牌配置。

更定量地，取 $L=n(n-1)/2$ 。可以在至多L轮中安排足够的碰撞，每轮至多指定n次公平硬币，因此从任何配置在接下来L轮内稳定的概率至少有统一正下界 $q=2^{-nL}$ 。这个界很宽松，但不依赖起始坏态。

利用新硬币的独立性和马尔可夫链的逐段条件概率，可得

\Pr(T>kL)\le(1-q)^k, \qquad \mathbb E[T]\le L/q<\infty.

右侧随k趋于0，证明概率一稳定，并给有限期望的粗界。它不是高效的O(n²)分析；更精细的令牌间距势函数与碰撞计算属于后续研究。

推论与应用

每节点每轮只读一个前驱比特，执行常数次局部操作，并在持令牌时取一个随机位；输出存储整网为n位。通信在这里是同步邻居读取模型，若用消息模拟每轮读，则还要支付同步与可靠通信的实现成本。

奇数前提不能省。偶数环的0101…有零枚令牌，所有节点按本页规则永久保持，无法恢复成唯一令牌。类似地，若各节点使用同一枚共享硬币，所有相同比特可能永远一起翻或一起不翻，多个令牌就一直保留；独立随机性不是可替换的装饰。

单令牌合法阶段不静默，但以概率一会不断向前并访问每个节点。指定令牌永远不前进的硬币序列存在，却概率为0。故应把确定性闭包、概率一收敛、期望时间和概率一轮转分别陈述，而不是统称“随机所以公平”。

单元终点把确定性Dijkstra环与本页并排：前者有特殊根、中央逐步调度，后者无特殊根、同步独立硬币。比较的首先是模型与量词，再是位数和恢复速度。

参考资料

Stefan Kiefer, Andrzej S. Murawski, Joël Ouaknine, James Worrell and Lijun Zhang, “On Stabilization in Herman’s Algorithm”, ICALP, 2011，§2：奇数环、相同比特令牌表示、非令牌保持与两两湮灭
Ted Herman, “Probabilistic Self-Stabilization,” Information Processing Letters 35(2), 1990, 63–67，原始协议；本页不引用后续文献某一版本的最优常数作为已证明结论
PRISM项目，Randomised Self-Stabilising Algorithms，工具的等价令牌模型与全初态检查；其位更新约定与本页区分，本文未声称运行PRISM