Herlihy 1991：等待自由怎样按共识数给并发对象分层

破除误解：等待自由不是无锁手册，共识数也不是日志复制#

第一层误解把等待自由听成「代码里不要出现锁这个词」。等待自由是一条关于步数的全称承诺：任意进程完成任意一次操作，只需要它自己的有限多步，不论别人跑得多慢、甚至已经停机。互斥锁直接违反它——持锁者若崩溃，等待者永远进不去。没有中央仲裁者、只用共享变量写下互斥的那一页，对象见 Dijkstra 1965。可是把锁删掉，并不自动得到等待自由。系统里只要「必须有人先做完」这种依赖还在，一个停住的进程仍然能把别人冻住。后来文献把更弱的条件叫做无锁：只要还有进程在跑，系统整体会有人完成操作，但不担保每一个人都完成。无锁允许饿死；等待自由不允许。赫利希 1991 年的对象是后者。

第二层误解把共识数听成 分布式共识算法，或听成 etcd 如何选主。论文里的共识极其窄：\(n\) 个进程各提出一个值，必须决定同一个值，且该值必须是某人所提；实现必须等待自由。装置是共享的并发对象外加原子寄存器，不是消息缓冲，也没有领导者任期。Raft 让跟随者等待领导者；少数派在分区一侧可以很久不提交。那是复制日志的工程合同。本页的层次回答的是：若你手头只有寄存器，两个进程能不能等待自由地达成一致？不能。若你手头有队列，三个进程能不能？不能。若你手头有比较并交换，任意多个进程能不能？能。把共识数读成「请部署一套共识服务」，类型就错了。

第三层误解把这篇与 FLP 收成同一条不可能。FLP 的信道是消息传递，故障是一次干净停机，禁止的是确定性协议在所有合法调度上既一致又终止。本页几乎不谈邮路。进程通过共享对象的调用与返回交换信息，允许任意相对速度，也允许 \(n-1\) 个进程停机。寄存器无法为两个进程解决等待自由共识，这一结论与 FLP 同属「异步加崩溃会卡住确定性一致」，模型却不是同一份。路易与阿布-阿马拉 1987 年已经证明，只靠读写内存达不成不可靠进程之间的协议；赫利希做的是把所有常见对象放进同一把尺，而不是再证一遍消息传递的那条定理。把队列的共识数等于 2 读成 FLP 的推论，会把共享内存的分层误认成网络协议的活性界限。

第四层误解把「比较并交换是万能的」听成芯片必须提供比较并交换，或听成生产代码应当用比较并交换去写每一种数据结构。万能性是一句关于可实现性的定理：若一个对象的共识数至少为 \(n\)，则对任意有顺序规格的并发对象，都存在一种为 \(n\) 个进程准备的等待自由实现。它不指定指令集，不比较哪一种重试更快，也不授权把寄存器上的队列「优化」成比较并交换循环。把万能性读成实现指南，会把存在性证明写成操作单。

共识数层次：寄存器、队列、比较并交换，以及万能性#

等待自由先被写成步数。一次操作的执行是该进程自己的步构成的序列。实现是等待自由的，当且仅当每个进程都能在自己的有限步内完成自己的操作，无论其他进程的调度如何——包括它们永久停住。这条条件立刻包含容错：\(n-1\) 个进程崩溃，剩下那一个仍须完成。它也排除任何必须等待别人先返回的协议。慢与死在本地观察上重合，等待自由的对策不是去分辨它们，而是根本不靠对方的步。

共识被用作探针，不是用作产品。每个进程提出一个输入值，写出一个决定值。一致性要求已决定的值相同；有效性要求决定值必须是某人所提；等待自由要求每个正确进程在自己的有限步内决定。一个对象类型的共识数，是最大的 \(n\)，使得仅用任意多个该类型的对象外加原子寄存器，就能为 \(n\) 个进程给出等待自由的共识。若对任意 \(n\) 都行，共识数是无穷。日常对象从此要回答：它最多能给多少人当一致的公证人。

层次的底端是原子读写寄存器。共识数是 1：一个进程独自读写当然能「达成一致」，两个进程就不行。证明沿用价的语言。配置若所有决定延伸都走向 0，称 0-价；对称地定义 1-价；两种延伸都存在则称二值待定。可以构造二值待定的初始配置。关键是寄存器的步太贫乏：一次写可以被后一次写盖住，一次读不留下别人必须看见的记号。于是存在某个进程的一步，使得跨过它之后配置仍然二值待定，或者落成两个价相反却对另一个进程不可分辨的邻居。等待自由禁止那个进程去等一个可能已经停机的同伴。因此两个进程无法只靠寄存器结束共识。

第二级聚拢了一批看起来很强的原语：测试并设置、交换、取并加、队列、栈。它们的共识数都是 2。两个进程可以用测试并设置选出胜者：先把共享位从 0 打成 1 的人决定自己的输入，后者读到 1 就采用前者的值。队列同样：两人各入队自己的提议，再出队；先入队的那一个值成为决定。三个进程时，这些对象的「一次改变、全体可见」不够用。可以安排调度，使某个进程的关键步留下的痕迹对另外两人不可分辨，而那两人各自单独跑又会走向相反的价。等待自由再次禁止第三人去等可能停机的那一个。于是队列不能为三个进程实现等待自由共识，也就不能等待自由地模拟任何共识数大于 2 的对象。寄存器实现不了等待自由的队列，原因更早：队列已经在第二级，寄存器停在第一级。

中间还有一条随宽度增长的刻度。对 \(n\) 个寄存器做一次原子赋值的对象，共识数是 \(2n-2\)：一次能碰几处内存，决定了你能协调多少人。层次的顶端是比较并交换一类。比较并交换带着一份「仅当当前值仍是我所期望的，才写成新值」的合同，失败者能看见自己没能改写。用它可以实现任意多个进程的等待自由共识：共享单元从空值出发，每人试图把自己的提议写进去；第一个成功的人钉死决定，其余人读到非空就采用那个值。内存到内存的传送与交换、取并连接、粘性字节、增强队列，同属共识数为无穷的一级：进程再多，它们仍然够当等待自由共识的原语。

方向反过来是万能性。若你已经有一个共识数至少为 \(n\) 的对象，那么对任意带顺序规格的并发对象，都存在为 \(n\) 个进程准备的等待自由实现。每个进程把自己尚未完成的操作公布出去。进程们用共识对象对「下一件被收进顺序历史的操作是哪一件」达成一致，于是全体操作被排成一条属于规格的顺序序列。一个跑得快的进程可以替一个尚未返回的进程完成那件已公布的操作——这叫帮助。慢者回来时，自己的操作可能已经被别人写进历史，它只需读出结果。共识保证大家对下一格没有分歧；帮助保证停机者不能把格子永久空着。定理给出存在性，不给出比较并交换该写在哪一行。

层次因此是双向的。向上，低共识数的对象无法等待自由地实现高共识数的对象——对足够多的进程而言。向下，高共识数的对象可以等待自由地实现任意对象，只要进程数不超过它的共识数。比较并交换因此被说成万能；队列对三个及以上进程不是万能。缺的不是队列作为顺序规格的合法性，是等待自由的实现力。把「不能从寄存器做出等待自由的队列」听成「队列这个抽象不合法」，会把 1991 年的进展层次误读成 1990 年的正确性条件。

它证明了什么，没有覆盖什么#

它证明了：等待自由把并发对象排进一条以共识为探针的链；链上每一级都有代表对象，级与级之间有不可实现定理；共识数至少为 \(n\) 的对象对 \(n\) 个进程是万能的。它没有证明消息传递系统里确定性共识能否终止——那是 FLP 的量词。它没有给出副本如何对日志达成一致，也没有把 etcd 的租约读写成等待自由。状态机复制可以使用共识去实现线性化的共享对象，那条路线把活性交给多数派是否同侧，与本页的共享内存层次不是同一对象。

它也没有覆盖 线性化 的定义本身。等待自由实现通常被拿去满足线性化，但线性化可以与锁共存：加锁的队列仍然可以线性化，只是不是等待自由。本页不把正确性条件再讲一遍。它没有覆盖 数据库事务 的可串行化与两阶段锁。锁可以提供隔离，代价正是阻塞；阻塞被本页的条件排除，排除不是一份「如何去掉锁」的迁移指南。它没有覆盖 内存一致性模型：硬件告诉你何时能看见别人的写，不告诉你一种对象最多能给几个人当公证人。比较并交换在芯片上如何侦测缓存行，不属于分层。

后来的弱化标出本页停住的位置。无锁允许系统里总有人前进，却许可个别进程饿死；障碍自由（Herlihy、Luchangco 与 Moir，2003）只要求进程在独自跑足够久时能完成。它们都改了进展合同，因此改的是对象，而不是给 1991 年的共识数表找出反例。把这些弱化读成「等待自由过时了」，会把一条仍然有效的不可实现边界收成风格争论。寄存器依然实现不了两个进程的等待自由共识；队列依然实现不了三个进程的等待自由共识。后来的系统可以选择不再要求等待自由，选择不等于推翻层次。

概念证据到此为止。本页不提供如何布置比较并交换循环、如何在生产队列里避免活锁、如何攻击或绕过互斥的步骤。层次回答的是「不能」，万能性回答的是「存在某种实现」，两句都不是操作单。

跨域连接#

• 认识论：等待自由拒绝一种常见的求知程序——先弄清别人是慢还是已经停机，再决定自己是否继续。完全异步里没有检验这种分界的证据：沉默既可被当成延迟，也可被当成崩溃。赫利希的对策不是收集更多关于他人状态的信念，而是设计一种不依赖那些信念也能完成操作的规则。共识数衡量的，正是一种对象能在多大群体里把「不必知道别人是否还在跑」做成可证的程序。把「我看见对方很久没写」提升为「我知道对方已经死了」，是把欠定证据做成知识。
• 同一性：队列与比较并交换在表面上都是「共享的可变位置」，却不是同一级对象。赫利希给出的同一性标准不看方法名，而看等待自由共识的外延能力：两个类型可替换，仅当它们能在同样规模的进程集合上当公证人。寄存器改不了自己停在第一级这件事，哪怕换一套内部表示。规格若只保证线性化的队列语义，对象在正确性条件的意义上仍是那个队列；一旦问进展，它与比较并交换不再同一。规格若改成允许阻塞，对象就离开本页的尺。
• 自由：等待自由接近一种严格的消极自由：别人的快慢不得成为我完成自己事务的条件。锁把我的进展交给持锁者的意志；持锁者若不再行动，我的自由被无限期没收。帮助机制看起来像介入他人事务，目的却相反——把慢者的未完成操作从「必须等本人回来」里解放出来，使任何人的停机都不能立法规定别人必须等待。干涉在这里不是禁止某一种意见，而是扣留某一次返回。若你要求每个人都不靠别人的步数完成自己的操作，手头的原语必须强到某一级。
• 知识：线性化约束的是「若把观察收成顺序历史，历史必须合法」；等待自由约束的是「我不必先拥有关于他人进度的知识才能写下自己的返回」。共识把一种更强的公共事实引入现场：一旦决定写出，所有正确进程终将持有同一个值。共识数问的是，何种对象能够在不停等同伴的前提下生产这份公共事实。寄存器几乎不能；比较并交换能。把本地写返回误认成「所有人已经按同一顺序知道了这件事」，会把局部证据做成共同知识。本页的层次管的是：这份公共事实在哪些原语上无法等待自由地闭合。
• 涌现：万能性声称，共识对象加上帮助规则之后，任意顺序规格都可以作为并发对象出现。整体性质——任意抽象数据类型的等待自由实现——并不写在比较并交换这一条指令的手册页里。单看一次「若值仍为期望则替换」，你看不见队列、栈或集合。它们是从「对下一格操作达成一致」这条局部规则里长出来的。还原到寄存器则长不出来：第一级太弱，两个进程的共识已经失败。负结果是弱原语的组合仍停在自己的共识数上；正结果是一旦原语跨过那条整数界，等待自由的对象空间对不超过该人数的进程全部打开。打开的是可实现性，不是一份把所有结构都改写成同一条指令的工程命令。

参考文献#

• Maurice Herlihy, "Wait-Free Synchronization", ACM Transactions on Programming Languages and Systems 13(1), 1991, pp. 124–149. DOI: 10.1145/114005.102808. —— 本文对象：等待自由、共识数层次与万能性。
• Maurice Herlihy, "Impossibility and Universality Results for Wait-Free Synchronization", Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, 1988, pp. 276–290. DOI: 10.1145/62546.62593. —— 会议版，层次与万能性的较早陈述。
• Maurice P. Herlihy & Jeannette M. Wing, "Linearizability: A Correctness Condition for Concurrent Objects", ACM Transactions on Programming Languages and Systems 12(3), 1990, pp. 463–492. DOI: 10.1145/78969.78972. —— 前一年的安全性条件，用以标明本页停在进展一侧。
• Michael J. Fischer, Nancy A. Lynch & Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM 32(2), 1985, pp. 374–382. DOI: 10.1145/3149.214121. —— 消息传递模型里的共识不可能，用以对照而非替代本页层次。
• Michael C. Loui & Hosame H. Abu-Amara, "Memory Requirements for Agreement Among Unreliable Asynchronous Processes", Advances in Computing Research 4, 1987, pp. 163–183. —— 读写内存不足以达成协议的前驱结果，寄存器共识数为 1 的背景。