“Herman协议在没有特殊根的同步奇数环上实现随机自稳定。固定奇数n≥3，节点按0到n−1编号，每个节点保存一个比特x[i]，读取自己与前驱的本轮旧值。若 $x[i]=x[i 1]$，节点i…”
形式陈述
自稳定系统从任意允许的损坏状态开始，在故障停止后最终恢复到合法状态，并在随后执行中保持合法。设C为全配置空间，L⊆C为合法集，→为故障停止后的正常转移关系，D为允许的调度规则集合。
相对于D，自稳定要求两项性质：
- 闭包：若c∈L且c→c′为允许正常步，则c′∈L。
- 收敛：对任意c₀∈C及每条满足D的极大执行，都存在有限位置k，使cₖ∈L。
极大执行是无限执行，或停在没有任何正常动作可执行的配置。不能让调度器在坏态随意停止，再宣称这条有限前缀不需要恢复。若模型允许停顿，应把与进展有关的公平条件明确放入可容许执行。
“任意配置”是任意类型允许的变量取值，不是任意毁坏程序与物理结构。本页的瞬时故障可以改变受保护范围内的状态变量；随后代码、通信拓扑、根身份等已声明的只读输入仍正确，且不再受到故障修改。持续拜占庭行为或不断到来的故障不自动被这个定义覆盖。
直觉
普通不变量证明从一个好初态出发，说明程序不会走坏。自稳定还需要回答：初态已经坏了，程序靠什么走回来？“进了合法区就不出去”与“从每个坏地方都能进去”是两张不同的证明。
调度器决定恢复规则何时执行。中央daemon每次只选一个使能节点；分布式daemon可能同时选多个。弱公平要求持续使能的动作最终执行，强公平还约束反复使能但并非持续的动作。同一份局部代码换调度语义后，收敛结论必须重查。
合法也不等于静止。令牌环的合法状态中仍有一个特权不断传递；静默自稳定树则希望输出寄存器稳定后不再修改。两种服务可以都自稳定，长期行为却不同。
例子与边界
固定路径上的距离修复
先看不需要处理未知拓扑的三节点路径r–a–b。每个节点保存一个距离，取值域为{0,1,2,3}；r是可信指定根。规则是r不为0时设0，a不等于min(3,d[r]+1)时改成该值，b不等于min(3,d[a]+1)时改成该值。每步原子地读邻居并更新本地，中央调度弱公平。
从(d[r],d[a],d[b])=(2,0,0)出发，一条故意绕路的恢复执行为
个别数值先变得更大，最终仍恢复。收敛证明无需猜一个“距离总和每步都下降”的势函数：r修好后永久为0；此后a的错误规则持续使能，弱公平保证它最终变1；a固定后，b最终变2。
合法集L={(0,1,2)}中没有修复动作，故闭包成立。这个分层论证将“前层已经永久正确”作为下一层的依据；它不是从某个幸运调度得到一次成功轨迹，就断言所有可容许执行都成功。
三种不够用的证明
只证明L是归纳不变量不够。给所有坏态添加“只能自环”的规则，L仍闭包，却没有任何坏态能恢复。
只证明“存在一条到L的路径”也不够。若坏态x可选x→x或x→L，不受约束的调度器可永远选自环。必须证明所有规定调度下都恢复，或明确额外公平性会排除哪条无限执行。
收敛不要求所有变量都单调，完整服务也不必终止。可以对坏态阶段构造良基下降量，进入L后继续提供服务；若试图让整个令牌循环都严格下降，会把合法的无限运行也错误排除。
恢复前的输出不能自动信任
某个令牌协议允许坏态存在多个特权，那么从任意初态恢复期间，它并不保证互斥。自稳定保证最终恢复后的服务，不等于从故障发生后的第一步就满足全部安全要求。
应用若不能容忍恢复期错误输出，需要额外的安全包装、可信复位部分或更强的容错规格。也不能把“恢复算法最后正确”解释为它已经撤销故障期间发生的外部副作用。
推论与应用
Dijkstra令牌环用一个特殊根和多值寄存器，从任意环状态恢复唯一特权；Herman协议在同步奇数环上用独立随机位，以概率一恢复单令牌。前者量化全部中央调度，后者还要区分所有硬币序列与概率一事件。
静默自稳定BFS树从任意距离和父指针恢复最短路树，合法后停止修改输出字段。这里的静默是寄存器行为，不意味着每个节点都知道全网已经稳定；知道全局完成仍是另一项信息任务。
设计时应把C、L、故障可修改的字段、正常原子步与daemon写在同一份规格里，再分别给闭包、收敛与恢复成本。只在展示图上画一条“错误→正确”的箭头，还没有回答最难的调度量词。
参考资料
- Edsger W. Dijkstra, “Self-Stabilizing Systems in Spite of Distributed Control”, CACM 17(11), 1974, 643–644：合法状态与中央daemon
- Stéphane Devismes and Colette Johnen, “Silent Self-stabilizing BFS Tree Algorithms Revised”, 2015，§2：配置、极大执行、daemon、异步轮与静默