Dijkstra 自稳定令牌环

普通节点只会复制颜色，不会产生新颜色。根负责在整圈追上自己以后换一种颜色，再让这个新值沿环向后传播。

损坏状态可以有很多颜色边界，因而有多个特权。关键是根最终会使用一种在当前起点的所有普通节点中都不存在的颜色。这个颜色只能从根出发依次传播；当它到达最后节点时，中间节点已经全部被它覆盖，多余边界便消失。

令牌不是额外存储的布尔量，而是相邻寄存器关系。恢复完成后，唯一使能节点执行一步，特权交给下一个节点，因而能支撑互斥公理库互斥Mutual exclusion临界区任意时刻至多容纳一个进程；完整问题通常另规定进入进展条件。访问的轮转。但从任意坏态开始的恢复阶段，可能确实有多个特权，不能在那时就宣称互斥。

四节点从四个特权开始 ​

取n=K=4，配置按(x₀,x₁,x₂,x₃)排列。起始(0,1,2,0)中，根0使能，节点1与2也使能，节点3因0≠2也使能，实际共有四个特权。按下表调度：

第二次更新后已经进入L，不必等到所有寄存器相同才算合法。表中全相同状态只是特权位于根的一种合法形状。

总有特权，合法集闭包 ​

若所有普通节点都不使能，便有 $x_0=x_1=\cdots =x_{n-1}$，根必使能。因此任意配置都不会无动作可做。

若唯一特权在根，所有值相同；根换色后，只在节点1产生一个不同值边界。若唯一特权在普通节点i，则所有其他普通相邻对相等，且根条件为假；i复制前驱后，特权移到i+1，或在i=n−1时回到根。这证明L的闭包公理库不变式与归纳不变式Invariant · Inductive invariant · Strengthened invariant区分所有可达状态上成立的性质与由初始性和一步闭包直接证明的归纳不变式。，并且合法阶段每一步都推进唯一特权。

为什么任意中央调度都收敛 ​

先证明根不可能从某时刻起永远不动。假设根固定，那么节点1至多再改变一次；节点2至多比节点1多改变一次，依次可知所有普通节点的总更新次数有限。它们最终全等于根，只有根使能，中央daemon必须选根，矛盾。因此无限执行中根会无限次换色。

在任意起点，n−1个普通节点至多占用n−1种颜色。K≥n保证存在一种颜色c没有出现在任何普通节点。普通节点只能复制，因此在根第一次持有c以前，它们也不能凭空产生c。若根起点已经持有c，就从这里开始；否则根逐次模K递增，最终第一次写入c。

此后根在最后节点也变c以前不能再动。c必须沿0、1、…、n−1依次传递；一旦某个前缀都为c，该前缀在根不变时不会退回旧色。最后节点首次得到c时全环同色，已经属于L。于是收敛不是依赖某个幸运调度，而是由复制方向与根换色强制完成。

原子模型不能随意改动 ​

本页一次动作同时读取相关旧值并写本地，且中央daemon每次只动一个进程。若把它拆成相隔很久的读写，或允许多个节点基于同一个旧配置同时更新，就改变了状态转移关系，不能直接沿用上面的唯一特权移动证明。

特殊根也是可信输入。所有节点改用相同复制规则，会让全相同配置没有任何特权；这不是在匿名环上顺便解决了选主，而是换成了另一个不能继续服务的协议。

每次动作只读一个前驱并更新一个本地寄存器，为O(1)寄存器操作；每节点需 $O(\log K)$ 位，整网 $O(n\log K)$ 位。墙钟恢复时间还取决于调度速度。

上述证明还能给一个宽松步数界。根固定的任一区间内，普通节点i至多更新i次，所以总共至多 $n(n-1)/2$ 次；再加一次根动作，便开启下一区间。至多K次根递增会遇到选定的新颜色，再经过一个固定根区间完成覆盖，因此有 $O(K{n}^2)$ 的简单恢复步数上界。本页不把它称为最优界。

合法后只有一个节点使能，调度器没有跳过它而选择别人的机会，故令牌持续环行。算法恢复的是可运行的唯一特权，而非全网静止；这一点与静默树协议的终点完全不同。