Garcia-Molina 1982：编号更高的进程怎样在超时假设下抢走协调者

破除误解：编号更大不是票数更多，超时也不是已经证明对面死了#

第一层误解把选举听成多数投票。教室里的投票先有一份固定名单、一轮清楚的含义、以及「过半即过」的算术。加西亚-莫利纳给的不是那张票。进程并不对某个提案举手，它们只比较事先写好的标识。标识是全序上的一个点，不是一票的权重。编号 17 并不比编号 3 多十四张赞成；它只是在全序里排得更靠后，因而在「最高者任职」这条规则下排得更靠前。没有相交的多数集合，也没有「两批 \(n-t\) 必须叠在一起」的几何。把 bully 读成「早期的 Paxos」或「简化的 Raft」，等于把全序比较偷换成仲裁。仲裁是后来共识文献的安全骨架；1982 年这篇要的是：在超时能够检出停机的前提下，活着的人里谁最大。

第二层误解把超时听成已经核验的死亡证明。论文允许进程用等待来判断对方是否还在应答。这句话成立，当且仅当消息延迟与处理时间被模型写成有界：超过那条界仍不回来，才被当成崩溃。完全异步里没有这条界。FLP 三年后会证明，没有上界时，确定性协议连「选定一个值并且每个合法调度都结束」都做不到；慢与死在观察上形状相同。Bully 并没有反驳那条定理，因为它从未待在那个模型里。它预先接受了「等待足够久就可以下结论」。把这篇读成「异步里也能靠编号选出唯一协调者」，是把假设读成了发现。本页因此不写间隔、阈值或重试曲线。计时器拧到哪一毫秒，是把抽象往一台机器上安装时才会出现的合同，不是 1982 年证明里的参数。

第三层误解把后来的选主装置提前写进这篇论文。钱德拉–图埃格 的故障检测器把「谁可能已经停机」写成一份允许犯错的预言接口，分级谈的是完备性与准确性，对象是共识可解性的最弱信息，不是一份编号比较程序。视图戳复制的换届要保住已被多数派知道的效果；Raft 的任期用来拒绝过期领导者的日志；Zab 的 epoch 用来给原子广播划世代。这些都是别的对象页。它们可以在教科书目录里和 bully 前后出现，并不因此变成同一套报文。把「选一个领导者」五个字当成可替换零件，会把 1982 年的全序加超时，与 1988 年以后的多数加视图混成一句口号。口号省事，模型不同。

第四层误解看见「霸道」两个字，就读成一份教人怎样打断别人选举、怎样把超时调乱、怎样强迫换届的操作单。论文的「bully」是一条关于优先级的比喻：恢复后的高号进程不必尊重低号协调者已经在任的事实，它按规则把座位拿回来。比喻停在算法内部的优先级，不延伸成对选举过程的干扰清单。本页写的是装置在何种假设下声称什么，不写如何让假设在现场失效。把恢复后的抢位读成攻击步骤，类型就错了：它是模型里已经写明的接管规则，不是一份侵入指南。

装置：编号全序、向上问询、超时即视为停机#

装置从一份固定、有限、彼此知道对方标识的进程集合出发。每个进程持有一个互不相同的整数，全体整数构成全序。协调者的规格很短：在算法当前当作「活着」的那些进程里，编号最大者任职。活着不是形而上学判断，而是装置自己的分类：尚未被超时判为停机、并且仍在按规则应答的进程。崩溃被写成停止发送；本页的故障不是伪造、不是对两名听众说两套话。拜占庭口头模型是另一条轴。

观念上的报文只有三类，写的是角色，不是可粘贴的帧格式。进程 \(P\) 若断定当前协调者已经停机，就向所有编号比自己更高的进程发出选举询问。若在模型给定的时限内没有任何人应答，\(P\) 把自己写成最高的活人，再向编号更低的进程宣告自己是协调者。若有更高编号的进程应答，\(P\) 停止争夺：应答者会自己发起一轮向上的询问。收到来自低号进程的询问时，高号进程先应答「我还在」，再——若自己尚未在选举中——向比自己更高的标识重复同一套询问。恢复也走同一扇门：一个刚活过来的进程并不先承认现任协调者，它直接开始选举；若它的编号在所有应答者之上，它把宣告发给所有低号进程，现任者即使工作正常也必须让位。这就是「霸道」在纸面上的全部意思：全序里的更大者不必等待更小者任满。

一个最小画面就够把全序和多数分开。设四个进程编号为 0、1、2、3，3 号正在任职。3 号停机之后，1 号先察觉沉默。1 号只问 2 号与 3 号。3 号不应答。若 2 号仍在，它应答 1 号，并自己去问 3 号；3 号仍不应答，2 号宣告任职。1 号并不因为「先发现故障」而获得座位，先发现只启动比较，比较的键是编号。若 2 号当时也已停机，1 号的向上询问全部落入时限，1 号宣告任职。之后若 3 号恢复，它向更高标识询问——没有人比它更高——于是它直接宣告，2 号或 1 号让位。全程没有「过半同意」。两个人活着时，较小者永远不能靠拉票打败较大者。这与多数交集刚刚相反：多数装置里，标识大小不决定谁的值被锁住；bully 里，标识大小就是规格本身。

超时在装置里的位置必须说清楚。它不是优化，也不是实现细节。没有「等待足够久就可以把沉默当成停机」，向上询问不会结束，宣告不会发生，恢复后的高号进程也无法确信自己已经是最高活人。论文把这条等待写成模型许可的推断，等价于给系统一只足够准的失败检测器：活人终将在时限内被听见，死人终将因超时被划出比较范围。钱德拉–图埃格 后来会把这类推断收成接口，并允许误报；1982 年的写法更硬，它按同步界来用超时。界若被违反——消息只是慢，并未丢失，进程也并未崩溃——装置可能把活人当成死人，于是两个进程都认为自己赢得了宣告。那不是论文证明的性质，而是假设撤掉之后装置不再担保的现象。指出这条边界，是为了标明对象停在何处，不是为了布置一条让宣告分裂的路径。

同文的邀请算法处理的是另一幅现场：网络可能裂成几块，每一块里的人无法把选举询问送到块外。霸道规则在那种现场会选出多个互不相认的协调者，因为每一块里的「最高活人」都是局部的。邀请把已经形成的小组当成可以合并的单位，用邀请而不是用编号欺压来重连。本页承认它存在，是为了划界：bully 预设你能够把询问送给所有更高编号的进程。连通性不成立时，对象换了，规则也换了。不要把邀请的合并读回霸道的抢位，也不要把分区修复写成一份可执行的重连剧本。

代价写在计数里，不写在机柜图里。若当前最高的活人自己启动选举，向上询问的集合是空的，宣告只需发给所有更低者，报文随进程数线性增长。若最低号进程启动、而几乎所有更高者都还活着，询问会一层层向上传，每个人都向自己之上的标识说话，最坏情况下报文数随 \(n\) 的平方增长。论文关心的是：在超时界成立时，最高活人终将任职，而不是把平方写成可接受的服务指标。进程集合事先已知、标识事先唯一，也是装置的前提。成员加入、离开、标识回收，属于后来的成员变更文献。1982 年的集合是固定名单上的全序，不是一张可以当场改写的花名册。

它表明了什么，以及它没有表明什么#

它表明：在延迟有界、停机可被超时切开、进程集合固定且标识全序的模型里，不必引入多数交集，也可以指定一个唯一的协调者规则——活着的人里编号最大者任职。它表明「谁先发现故障」并不赋予任职权，发现只启动比较。它表明恢复不是回到旧座位那么简单：高号进程按同一规则把低号协调者挤走，可用性会为了优先级被主动打断。它还表明 1982 年的分布式计算已经把选举写成一种控制层装置，而把选举与「对客户值达成一致」分成两件事。三年后的 FLP 会让后一件事的难度被看清；bully 预先走的是「给时间」那一扇门，不是「给硬币」或「给一份会犯错的怀疑预言」。

它没有表明完全异步里确定性选主必然终止。去掉超时界，沉默不再是可判定的停机，装置退回 FLP 已经划过的那条线。它没有给出对客户命令的共识，因而既不是 Paxos，也不是 视图戳复制，更不是 ZooKeeper 或 etcd 里后来那些带世代编号的选主。它没有在分区下保住「全世界只有一个协调者」：那是邀请算法的问题意识。它没有把故障检测器的完备性与准确性写成分级定理，没有给出 \(\Diamond W\) 或 \(\Omega\) 的最弱性。它也没有规定生产系统该把哪一只计时器拧到哪里。本页因此停在 1982 年那条全序规则：编号是优先级，超时是假设，协调者是比较的结果，不是投票的结果。

跨域连接#

• 认识论：异步观察里，沉默不是关于「对面已死」的现成知识。延迟与崩溃产生形状相同的证据，主体没有上帝视角把两者切开。加西亚-莫利纳改的不是观察本身，而是主体被允许使用的手段：模型预先发给他一条时间上界，让「等够了」在界内成为合法推断。这与把本地等待提升为公共知识不是同一回事。一个人因超时而停止等待，并不等于所有人都已经知道那个人死了，更不等于系统已经把死亡写成不可撤回的事实。工程事故常发生在把「我等够了」误认成「我们都知道他死了」。Bully 的宣告是一次关于任职的公开断言，但它的证据仍是局部的超时。承认证据是局部的，才不会把同步假设误当成已经共享的死亡证明。
• 时间哲学：完全异步拒绝一个全体共享的「此刻」，缺席因此不是可观察的现在，而是可能仍在未来才到达的延迟。超时把「未来会不会到来」改写成「超过这条界就当作不会到来」。奥古斯丁问现在有没有厚度；这里的现在被模型切出一截有限的等待，等待结束就被当作已经发生的事件。麦塔加特的 B 系列是先于与后于的固定关系；超时并不生产物理上的先后，它生产的是协议自己愿意承认的截止。把截止理解成墙上的某一秒，会把模型里的界还原成民用时。论文从未测量振荡器，它只要求存在一条足够管住延迟的界。界是逻辑时间里的许可，不是发现出来的宇宙时刻。
• 合法性：政治正当性问的是统治是否值得服从，而不是谁的编号更大。韦伯把合法性与强制分开：军队在手仍可能在认可抽空后垮掉。Bully 走的是另一条路。任职资格事先写在全序里，恢复后的高号进程不必取得低号进程的同意，低号协调者即使正在工作也必须让位。这更接近一种预先颁布的身份等级，而不是同意、商谈或多数认可。把进程选举听成一次小型民主，会把全序误认成民意。编号不是选票，让位也不是因为失去了被统治者的信任。政治里「选举」指向授权与可问责；这里的 election 只指向：在超时界内，把最高活人标成协调者。两个词共用一个英文，对象不是同一种承认。
• 集合论：标识的比较是全序上最普通的运算：任意两个不相等的整数都能比出大小，因此「当前活人集合里的最大元」在集合非空时唯一存在。唯一性来自全序，不来自投票。多数装置用的是另一套外延对象：大于一半的子集两两相交，相交锁住值。Bully 的活人集合一旦被超时划定，最大元就已经被全序钉死，没有平局需要用进程名再打破。超时若把活人划出这个集合，最大元会指向另一个元素——不是全序坏了，是参与比较的子集被写错了。把编号画成机架位置或可用区名单，会把全序误认成布线。序是标识上的关系，拓扑只改变哪些询问暂时到得了；到得了与否改变经验频率，不改变「最大元任职」这句外延陈述。
• 知识：每个进程关于「谁是协调者」的信念，开始时只是自己的超时与自己收到的宣告。宣告试图把局部结论写成别人可以引用的任职事实，但它依赖别人也承认同一条超时界、同一份标识全序。公共知识更远：所有人都收到了同一份宣告，也不等于所有人都知道别人已经收到。低号进程让位，是因为它按规则把高号宣告当成更新自己信念的许可，不是因为它亲知了高号进程的存活。停摆的钟可以碰巧指对时刻；一次碰巧没有误报的超时，也可以碰巧选出真正的最高活人。规格要的是界成立时的必然，不是碰巧选对。把「我看见宣告」当成「我已经知道全世界都承认他」，会把私人证据提升为大家都知道的花名册。

参考文献#

• Hector Garcia-Molina, "Elections in a Distributed Computing System", IEEE Transactions on Computers C-31(1), 1982, pp. 48–59. DOI: 10.1109/TC.1982.1675885. —— 本文对象：超时可检出停机时的霸道选举，以及同文中面向分区的邀请算法（本页不把后者当对象）。
• 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. —— 用以标明完全异步里慢与死不可分；bully 预先给出的正是论文所缺的时序界。
• Tushar Deepak Chandra & Sam Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems", Journal of the ACM 43(2), 1996, pp. 225–267. DOI: 10.1145/226643.226647. —— 故障检测器抽象，用以对照：怀疑名单是接口与分级，不是编号比较程序。
• Brian M. Oki & Barbara Liskov, "Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems", Proceedings of the 7th ACM Symposium on Principles of Distributed Computing (PODC), 1988, pp. 8–17. DOI: 10.1145/62546.62549. —— 用以标明视图变更是另一套装置，不是 bully 的换名。
• Cynthia Dwork, Nancy A. Lynch & Larry Stockmeyer, "Consensus in the Presence of Partial Synchrony", Journal of the ACM 35(2), 1988, pp. 288–323. DOI: 10.1145/42282.42283. —— 部分同步下共识可终止，用以对照「给时间」这扇门后来怎样被写进共识，而不是写进 1982 年的全序选举。

延伸阅读#

• Andrew S. Tanenbaum & Maarten van Steen, Distributed Systems: Principles and Paradigms. —— 教材中对 bully 的转述最为常见，便于对照教科书简化与 1982 年原文的模型假设，不是本页的对象文本。
• Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996. —— 把领导者选举放进同步 / 异步模型与消息复杂度的系统论述，用来标明本页停在加西亚-莫利纳那一条全序规则。
• Diego Ongaro & John Ousterhout, "In Search of an Understandable Consensus Algorithm", Proceedings of the 2014 USENIX Annual Technical Conference, 2014, pp. 305–319. —— Raft 的任期与多数选主，用来对照：后来的可理解共识把领导者写成日志安全的一部分，不是编号欺压。
• Patrick Hunt, Mahadev Konar, Flavio P. Junqueira & Benjamin Reed, "ZooKeeper: Wait-free Coordination for Internet-scale Systems", Proceedings of the 2010 USENIX Annual Technical Conference, 2010. —— 协调内核与原子广播上的选主，用来对照 ZooKeeper 页的对象，避免把 Zab 读回 1982 年。