共识数与 Wait-free 层级

形式陈述 ​

固定异步共享内存模型：进程可能崩溃停止，正确进程持续取得步骤；实现可使用任意多个原子读写寄存器和某种线性一致的对象类型公理库并发对象Concurrent object可被多个线程并发调用并以顺序规格解释操作效果的共享对象。 $T$。$T$ 的共识数 $c(T)$ 定义为：能够用这些对象为 $n$ 个进程wait-free公理库Wait-free 进展Wait-free progress · Wait-freedom · 无等待进展每个正确参与者的每次操作都在有限个自身步骤内完成的个体级非阻塞保证。 地解决共识公理库分布式共识Distributed consensus · Consensus problem多个进程在可能故障和通信延迟下对一个值达成一致的任务。的最大 $n$；若对每个有限 $n$ 都可解决，则记 $c(T)=\mathrm{\infty }$。

这里分类的是对象类型及其完整顺序规格，不是某一个容量有限、随后耗尽的实例。算法可以创建任意多个 $T$ 实例，原子寄存器始终作为辅助；进程必须在有限个自身步骤内决定，即使其他进程在任意时刻停止。若把 wait-free 换成 lock-free、允许阻塞锁，或改变操作返回值，得到的就不再是同一层级。

Herlihy 层级的经典分类包括：原子读写寄存器的共识数为 $1$；test-and-set、swap 与 fetch-and-add 的共识数为 $2$；标准 compare-and-swap（CAS）的共识数为 $\mathrm{\infty }$。数值不是“指令强度分数”，而是一个可实现性边界：共识数至少为 $n$ 的类型可在至多 $n$ 进程系统中，经由 wait-free 通用构造实现任意具有顺序规格的对象；若 $c(A)<c(B)$，就不存在只用 $A$ 与寄存器 wait-free 实现 $B$ 的方法，否则组合该实现与 $B$ 的共识算法便会用 $A$ 解出超过其共识数的共识，产生矛盾。

通用构造的核心是把并发操作转化为一串待决定的状态机步骤。各进程提出下一项操作，利用第 $k$ 个共识对象唯一决定序列位置 $k$ 的内容，再按共同前缀计算返回值；帮助机制确保即使提议者崩溃，其他进程仍可完成已经公布的调用。具体构造还需处理操作描述、响应匹配与空间回收，但定理表达的是对象类型在给定进程数下的普适表达力。

直觉 ​

共识要求多个进程从不同提议中不可撤销地选出同一个值，因此能测量原语“打破对称”的能力。普通读写让每个进程留下信息，却没有一个原子时刻能让竞争者共同认定谁先；CAS 则把“若仍无人决定，就由我写入”压成一次不可分割的条件更新，首个成功者自然成为共同选择。

层级的价值在于把无数实现问题缩成一次比较。若目标类型能解决三进程共识，而手头原语最多只能解决两进程共识，就无需继续寻找 wait-free 实现；不可能性已经来自组合论证。这个结论并不禁止锁实现或较弱进展实现，只精确排除指定模型中的 wait-free 路线。

例子与边界 ​

用 CAS 为任意有限数量进程解决一次共识：共享原子槽 decision 初值为 $\mathrm{\perp }$；进程 $p_i$ 执行 CAS(decision, ⊥, v_i)，随后读取并决定槽中的值。只有一个 CAS 能把 $\mathrm{\perp }$ 替换为提议值，故所有进程读到同一决定；决定值确由某进程提出；每个进程只做常数次原子步骤，其他进程崩溃也不妨碍完成。在标准无限次可用、线性一致 CAS 语义下，这一构造对任意有限 $n$ 成立。

只用原子读写寄存器不能为两个进程 wait-free 解共识。直觉上，在双方仍可能决定不同值的临界配置中，两个进程各自下一步若作用于不同寄存器便可交换次序，若是对同一寄存器的普通读写又有一步会覆盖或无法被另一方区分；由此可构造两个不可区分执行，迫使协议同时保留两种决定可能。正式证明使用 valency，而不是以“读写不够快”作经验判断。

有限位宽、可能回绕的机器 CAS 是否保持抽象类型的全部能力，要看对象规格与可用内存模型。硬件吞吐、缓存争用和 ABA 风险影响实现性能与安全证明，却不改变理想原子 CAS 类型的经典共识数；若接口改成可能伪失败、只比较受限状态或允许非线性行为，就必须重新分类。

推论与应用 ​

共识层级解释了读改写原语公理库读改写原语Read-modify-write operation · RMW在单个原子步骤中读取旧值、计算并写入新值的共享内存操作。之间并非只有性能差异。它为无锁数据结构给出选择下界，也说明为什么从弱原语实现强对象时，算法常不得不降低进展保证、限制参与者数量或引入更强硬件操作。

分类结论不能反向代替具体算法证明。一个原语共识数足够高，只表示存在通用 wait-free 构造；实际队列或栈仍需证明线性一致性、步骤界和内存回收。相反，某对象无法用低层原语 wait-free 实现，也不排除使用互斥锁公理库互斥锁Mutex · Mutex lock · 互斥量以所有权和阻塞语义封装临界区互斥的同步对象。、随机化或特定调度假设得到可用实现。

参考资料

• Maurice Herlihy, “Wait-Free Synchronization,” ACM TOPLAS 13(1), 1991, pp. 124–149。
• Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, rev. 1st ed., Morgan Kaufmann, 2012，Ch. 5。
• Hagit Attiya and Jennifer Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd ed., Wiley, 2004，共享内存可解性相关章节。