Schneider 1990：副本确定性、输出一致与状态机方法，不是又一份 Paxos

破除误解#

误解二：多放几台、跑同一份程序，输出自然会一致。 确定性不是“源码相同”。命令必须是确定性程序：下一步状态与输出，只由当前状态和这条请求决定，不由调度、本地钟、传感器的偶然读数或伪随机种子的私有抽签决定。请求还必须以同一相对顺序进入各非故障副本。缺了任何一条，副本就会在客户看不见的地方分叉，再把分叉后的回答交出去。教程把这种“同一初态、同一请求序列，则同一输出”称为副本确定性；把客户因此看见彼此不矛盾的回答，称为输出一致。多机是手段，不是那条定理。分布式系统 里高可用常被听成副本数量；这篇对象更窄：能被当成单机服务引用的，是已经按同一全序处理过同一串请求的那些非故障副本。

误解三：超时就是容错；谁先超时谁就决定下一请求，或者用超时把慢节点判死。 教程单开一节谈超时，恰恰因为超时是副本分叉最常见的入口。各机本地的等待、线程抢占、读钟时刻，都是未进入公共请求序列的隐式输入。若命令是否执行取决于“我这台是否已经等够”，各副本会在不同墙钟、不同负载下走出不同命令流。教程的主张不是把计时器拧到某一毫秒，而是：凡是会影响下一状态的超时，必须变成经副本协调之后的显式请求，或必须相对于全体同意的时间概念发生，而不能留在各机私有的调度里。如何填写超时、如何用等待把某副本从服务里挤出去，都不在纸上的装置里。

误解四：输出一致就是客户对副本回答做多数表决；寄存器仿真、复制日志，都是状态机方法的别名。 故障停止模型里，非故障副本若已处理同一序列，任取一份输出即可，因为它们本应相同；表决不是这条路径的本质。拜占庭模型里客户才需要足够多份相同结果，好让正确回答压过至多 t 份任意内容——那是输出收集，仍以副本确定性为前提，不是用投票替代全序。ABD 要的是邮路上的原子寄存器：读写靠时间戳与多数派相交，并不把任意命令收进同一条状态机。复制日志是后来系统把“请求全序”落成一条可追加记录的工程形态；教程没有写日志格式，也没有授权把寄存器、日志与状态机三个词叠成一个操作对象。

确定性状态机、请求全序与副本输出#

状态机在教程里是一份状态加上一组命令。每条命令由确定性程序实现，原子地改写状态变量并产生输出。输出完全由它处理过的请求序列决定，与墙钟、与系统里同时发生的其他活动无关。客户发出请求，服务交回输出。正确性口径是：尽管有故障，对外仍像只有一台这样的状态机。复制是为了让这台逻辑机器在部分副本失效后仍能回答；复制本身不改变命令的含义。客户看见的是命令与应答，不是一条可供人改写的日志。教程把“谁把请求送进副本集合”写成协调问题的入口，并不把发送路径写成可采购的传输层，也不把状态机收成程序员去实现的日志状态机。

副本协调被写成两条必须同时成立的要求。一致性（agreement）：每个非故障副本都收到每一个请求。顺序（order）：非故障副本按同一相对顺序处理它们收到的请求。顺序还须与潜在因果相容：客户若在看见某次应答之后才发出下一请求，则后一请求不得排在前一请求之前。两条要求分开写，是因为散布请求与给请求编号不必是同一套手续。教程不把其中任何一条写成可部署的广播库。

请求带着全序的唯一标识。逻辑钟方案沿用兰波特 1978 年的先后：进程给事件贴时间戳，无因果箭头的事件仍被排成一种全体相同的先后。同步实时钟方案假定钟差与信道延迟有上界，用真实时间戳当标识。无论哪一种，副本都不能在请求一到就执行。请求必须先稳定：该副本可以确信，不会再有标识更小、因而应当排在它前面的请求随后抵达。逻辑钟下，这份确信来自已经看见足够多来源的更大时间戳；实时钟下，来自本地钟已经越过该时间戳加上延迟上界。稳定是执行许可，不是磁盘命令，也不是一份教人如何拖延他人请求的接口。

故障模型分成两条，人数条件也分开写。故障停止：节点按停机失效，不撒谎；容忍 t 个停机，t+1 份副本即可留下至少一份正确状态。拜占庭：副本可以对不同听众交出两套话；输出侧要让正确回答占优，通常写成 2t+1 份以便多数来自正确副本，而请求散布所引用的交互一致性，在口头消息下回指向 拜占庭将军 的 3t+1。教程把散布交给已有结果，不在这二十一页里重写口头消息算法。客户取输出时，故障停止路径信任任一非故障副本的回答；拜占庭路径等待足够多份相同结果。输出一致是确定性加全序的推论，不是另起一套与状态无关的投票器。

副本崩溃、修复后再加入、以及增加新副本，被写成配置变更：新来者必须先获得当前状态，才能参加此后的请求处理。空白内存不得冒充上一届的记忆。网络若分裂，唯一全序的服务不能在两个分区里同时推进——否则各分区会各自延长请求序列，愈合时无法收成一台状态机。教程承认可在多数派一侧继续的服务是子集，并不把任意服务在分区下的可用性写成免费承诺。这些是正确性边界，不是机架布局，也不是把分区当成可攻击接口来拆的说明。

论文表明了什么，以及它没有表明的东西#

它表明容错服务可以先写成一台确定性状态机，再问副本如何对请求取得一致与全序。副本确定性把“同一初态加同一请求序列”收成输出相同的充分条件；输出一致是客户侧看到的那件事。一致性与顺序必须分开满足，稳定是顺序能被安全执行的界线。故障停止与拜占庭在人数、散布和取输出的方式上不是同一套算术。超时与本地钟若保持为私有输入，确定性立刻失效。分区下，需要唯一全序的服务不能两边同时立法。崩溃终将可被检测、拜占庭人数按模型封顶、钟差与延迟在实时钟方案里有界，是假设，不是现场统计。

它没有生产系统的吞吐曲线，没有选举毫秒分布，也没有把三副本与五副本画成可外推的容量规划。综述组织的是已有手续的位置：散布、编号、稳定、取输出、再加入，而不是一次新的测量。它没有证明自己与后来刊出的 Paxos、Viewstamped 或 PBFT 形式等价——那是更晚对照文献的事。它不给出复制日志的编码，不给出超时配方，也不处理开放成员网络。兰波特 1978 年的多机实现与 1984 年“用时间代替超时”的 TOCS 长文是这条装置的前身；本页的对象是 1990 年把它们收成教程的那一篇，不是把前身兑成操作单。

分布式系统 里，复制常被听成“多放几台就行”。这篇对象更窄：能继续代表这项服务说话的，是已接收同一串请求、并按同一相对顺序处理到稳定前缀的非故障副本；客户能够引用的输出，是这份前缀上确定性命令交出的结果。把它读成 Paxos、Viewstamped 或 PBFT 的部署说明，或读成如何编写一条复制日志，都离开了纸上的装置。

跨域连接#

• 认识论：副本确定性是一条关于证据的主张：若非故障副本已经知道同一初态与同一请求序列，它们就应当知道同一串输出。教程把尚未稳定的请求排除在可引用的知识之外——更小标识仍可能抵达，副本还不能声称自己知道下一步命令。工程事故常发生在把某台内存里未经全序确认的效果，当成已经可向全体引用的事实。容错服务的证据标准是“请求序列已被非故障副本共同接收并按同一相对顺序处理”，不是“我这台已经跑完了”。这不是把认识论标签贴到机柜上，而是指出：对外可引用的服务状态，必须是公共请求前缀上的推论，而不是私有调度的偶发结果。
• 知识：稳定是一份知识声明：该副本可以确信，不会再有应当排在当前请求之前的请求到来。逻辑钟方案里，确信来自已经看见足够多来源的更大时间戳；实时钟方案里，确信来自本地钟越过时间戳加上延迟上界。两种写法问的都是：你凭什么把“可能还没齐”改写成“可以执行”。恢复后的副本必须先获得当前状态才能重新参加；空白内存不能冒充已有知识。教程没有把知识写成可拷贝的快照格式，也没有教人如何用一份过期状态冒充当前服务。
• 模态逻辑：确定性说的是必然：同一初态与同一请求序列下，输出不可能不同。可能性出现在请求尚未全序之时——不同副本仍可能按不同相对顺序处理，于是可能交出不同输出。副本协调把“可能各走各的顺序”收成“必须同一相对顺序”。Agreement 让每个非故障副本都接到请求，否则有人可能永远看不到这次命令；Order 让相对顺序成为全体非故障副本的必然事实。超时若留在各机私有的可能世界里，必然性立刻碎掉。这不是在纸上添加克里普克公理，只是借用必然与可能把两条要求说清楚。
• 时间哲学：教程给出两种为请求排全序的时间。逻辑钟不声称抓住“现在”，只给因果上可比较的事件一个全体相同的编号；实时钟方案假定钟已同步、延迟有界，于是“足够晚”可以当作“更早的请求不会再来”的证据。稳定点像一道已经闭合的过去：还可能插入更早位置时，执行许可尚未发出。墙钟上的到达先后不是这份时间；各副本各自看钟，恰恰是确定性要排除的那种流逝。教程不是校时作业，也不把等待写成攻击接口。它表明状态机方法里的时间是为了给请求一个可共享的先后。
• 因果性：客户若在看见 r′ 的应答之后才发出 r，则 r 应当排在 r′ 之后。这是潜在因果对处理顺序的约束。全序可以比因果更细：没有箭头的两请求仍必须被排成同一种先后，否则副本会分叉。网络上的到达先后既不是因果，也不是应当执行的顺序；应当执行的顺序是协议产物。休谟式的“先后相随”在这里不够用。寄存器仿真用时间戳与多数派相交保证线性化，并不要求任意命令进入同一条状态机；那是 ABD 那一页的对象。本页的因果约束只服务于“同一台确定性状态机被复制多份”。
• 概率论：故障在教程里是集合论式的上界：至多 t 个故障停止，或至多 t 个拜占庭。输出侧取一份或取足够多份相同结果，依据的是正确副本是否还在、正确回答能否压过任意内容，不是独立故障乘积公式里的年可用性。文中没有到达过程的拟合，没有把副本数画成可外推的可靠度曲线，也没有把超时分布当成随机数来调。把 t 读成现场故障率，或把表决读成一次统计检验，都离开了 1990 年这篇综述。

参考文献#

• Schneider, F. B. Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial. ACM Computing Surveys 22(4), 1990, pp. 299–319. doi:10.1145/98163.98167（本文对象）
• Lamport, L. The Implementation of Reliable Distributed Multiprocess Systems. Computer Networks 2(2), 1978, pp. 95–114.（状态机方法的前身：可靠多机系统）
• Lamport, L. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM 21(7), 1978, pp. 558–565. doi:10.1145/359545.359563（逻辑钟与潜在因果；教程用来给请求编号）
• Lamport, L. Using Time Instead of Timeout for Fault-Tolerant Distributed Systems. ACM TOCS 2(2), 1984, pp. 160–182. doi:10.1145/2993.2994（同步实时钟下的状态机；教程所本的时间方案之一）
• Schneider, F. B. Fail-stop processors: An approach to designing fault-tolerant computing systems. ACM TOCS 1(3), 1983, pp. 222–238. doi:10.1145/357360.357365（故障停止模型；教程一条故障模型所本）
• Lamport, L., Shostak, R. & Pease, M. The Byzantine Generals Problem. ACM TOPLAS 4(3), 1982, pp. 382–401. doi:10.1145/357172.357176（口头消息与 3t+1；教程把拜占庭散布交给这一结果）

延伸阅读#

• Oki, B. M. & Liskov, B. Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. Proc. 7th ACM PODC, 1988, pp. 8–17. doi:10.1145/62546.62549（主副本与视图戳；早于本教程两年的一种实例，非本文对象）
• Lamport, L. The Part-Time Parliament. ACM TOCS 16(2), 1998, pp. 133–169. doi:10.1145/279227.279229（选定值的 Synod；后刊实例，非本文对象）
• Castro, M. & Liskov, B. Practical Byzantine Fault Tolerance. Proc. 3rd OSDI, 1999, pp. 173–186.（拜占庭状态机复制协议；后刊实例，非本文对象）
• van Renesse, R., Schiper, N. & Schneider, F. B. Vive la Différence: Paxos vs. Viewstamped Replication vs. Zab. IEEE Transactions on Dependable and Secure Computing 12(4), 2015, pp. 472–484.（后来的形式对照，不是把三份兑成一份操作单）
• 与 Paxos、Viewstamped、PBFT 对读：那些页是后来或稍早的协议实例；本页是 1990 年的确定性、全序与输出一致。
• 与 ABD 对读：寄存器仿真要线性化读写，不要任意命令的状态机。
• 与 拜占庭将军 对读：将军问题给出口头消息下的人数界限；本教程在取输出与散布请求时引用它，不重写围城算法。