2014 年，Diego Ongaro 和 John Ousterhout 在 USENIX ATC 发表《In Search of an Understandable Consensus Algorithm》。论文没有声称 Paxos 是此前唯一正确的协议，而是指出：从 Paxos 的单次决议核心到可实现的复制日志，工程人员仍需补领导者、成员变更、日志压缩和恢复等大量规则。Raft 把“可理解性”本身设为设计目标。
这段历史提醒我们，共识不是一个可以只凭名称采购的组件。“使用 Raft”不自动证明数据库不会丢数据，正如“使用 TLS”不自动证明整个系统安全。
破除误解：共识不是一次多数投票
多数投票只有在参与者集合、轮次和消息含义都已经确定时才简单。分布式环境中，节点会崩溃和重启，消息会丢失、重复、延迟和乱序；节点也无法立即区分对方崩溃、网络分区或只是很慢。
一个单次共识问题通常要求：
- 一致性（Agreement）：正常节点不能决定不同值；
- 有效性（Validity）：决定值必须满足规定的提议约束；
- 完整性（Integrity）：节点不能决定两次；
- 终止性（Termination）：在规定网络和故障假设下，正常节点最终决定。
前三类通常归入安全性：任何有限执行前缀都不能出现坏结果。终止属于活性：好结果最终发生。协议可以始终安全，却在长期分区中停止接受写入。
生产系统更常需要状态机复制：多个副本不是只决定一个值，而是对连续命令的顺序达成一致。共识复制日志；应用还需确定性执行、持久化、快照、客户端去重和成员治理。
先写清系统模型
比较协议前至少要列出：
- 节点是崩溃停止，还是会重启并读取稳定存储；
- 网络是同步、异步，还是最终进入延迟有界的部分同步；
- 成员是否固定、身份是否认证、能否任意加入；
- 容忍多少故障，仲裁集合怎样相交；
- 返回成功前，哪些日志和数据必须持久化；
- 安全性是确定保证，活性是条件保证还是概率保证。
不写这些条件，“容错”“最终确定”和“不会丢数据”都没有完整含义。
FLP 的边界
Fischer、Lynch 和 Paterson 在 1985 年证明：在完全异步消息系统中，只要一个进程可能崩溃，就不存在一个确定性协议能在所有允许执行中同时保证共识安全与终止。
FLP 证明存在一种合法调度让协议一直不决定。它不是说现实系统无法达成共识，也不是说每次异步执行都会卡死。
工程和理论通过改变前提取得进展：
- 增加时序或故障检测假设：Paxos、Raft 在稳定领导者和多数副本能及时通信时取得进展；
- 加入随机性：随机化协议可在明确对手模型下获得概率 1 终止；
- 使用更强原语：共享内存、可信硬件或外部时钟会改变问题模型。
比特币等开放成员协议还涉及链选择、网络传播、算力或权益假设与经济激励，不能简单归为 Ben-Or 随机共识的工程版本。完整理论脉络见 distributed-computing-theory。
Paxos：多数交集与承诺
Paxos 的逻辑角色包括提议者（Proposer）、接受者（Acceptor）和学习者（Learner）；一台服务器可以承担多种角色。
第一阶段：Prepare 与 Promise
提议者选择唯一且递增的编号 \(n\)，向接受者发出 Prepare。接受者若尚未承诺更大编号，就承诺不再接受编号小于 \(n\) 的提案，并返回自己已接受的最高编号和值。
第二阶段：Accept
提议者获得一个仲裁集合的承诺后：
- 若没有接受者报告旧值，可以提出自己的值；
- 若存在旧值，必须提出报告中编号最高的已接受值。
这个选择规则与仲裁交集共同保证：一个值一旦被选定，任何后来被选定的值都与它相同。它不表示网络里不再出现其他提案，也不表示客户端已经知道决定。
Basic Paxos 解决一个槽位。Multi-Paxos 在稳定领导者下复用第一阶段，并对连续槽位复制日志。持久化承诺、领导者恢复、空洞日志、重配置和客户端去重都需要额外协议。
Raft：把可理解性写进设计
Raft 与 Multi-Paxos 提供相近的复制日志结果，但采用更强的领导者结构来缩小状态空间。
领导者选举
节点处于追随者、候选者或领导者状态。选举超时后，候选者增加任期并拉票；同一任期每个节点最多投一票。随机化超时减少同时竞选，但活性仍依赖多数节点最终能稳定通信。
任期不是墙钟时间。它是单调增加的逻辑时代，用于识别过期领导者和消息。
日志复制
客户端命令通常先到领导者，领导者追加日志并复制给追随者。Raft 领导者通过多数复制直接提交当前任期的条目；此前任期条目随当前任期条目一起间接提交。
省略“当前任期”限制的实现，可能把后来会被覆盖的旧条目错误标为已提交。
领导者完整性
候选者只有在日志至少和投票者一样新时才能获得选票。这个规则使包含已提交条目的节点阻止较旧节点当选。
状态机复制还要求命令执行确定性。随机数、墙钟、外部调用或不稳定迭代顺序若未进入日志，不同副本可能拥有相同日志却得到不同状态。
etcd、Consul、TiKV 和 CockroachDB 等系统使用 Raft 或其分片化变体，但产品保证还取决于存储引擎、事务层、快照和配置。
成员变更是安全协议的一部分
直接把三节点配置 {A,B,C} 改为 {D,E,F}，旧多数与新多数可能没有交集，两个配置就可能各自提交冲突日志。
Raft 使用联合共识，使过渡阶段决定同时获得旧配置和新配置的多数支持。实践还要处理学习者、逐节点变更、快照传输和失败回滚。
重配置、日志压缩和灾难恢复必须接受与正常复制同等级的验证。固定成员模型正确，不代表扩展代码仍然正确。
拜占庭容错与开放成员
Paxos 和 Raft 通常处理崩溃故障：节点会停止或重启，但不会故意向不同接收者发送矛盾消息。
在经典部分同步、认证信道模型下，PBFT 类状态机复制通常使用 \(3f+1\) 个副本和 \(2f+1\) 交集仲裁，容忍 \(f\) 个拜占庭副本。崩溃容错通常以 \(2f+1\) 个副本容忍 \(f\) 个崩溃。
这些数字依赖模型。改变同步、认证、可信硬件或最终性假设后，下界和协议会变化。
PoW 与 PoS 还要面对开放成员和女巫攻击，以资源或质押定义投票权，并提供概率最终性或不同形式的经济最终性。其安全条件涉及网络、参与率、攻击成本和客户端规则，不等于把 PBFT 换成代币。
恢复、磁盘与客户端语义
协议论文常把稳定存储视为可靠边界，真实系统还会遇到 torn write、静默损坏、错误刷盘和回滚到旧快照。实现必须说明哪些元数据在回复前持久化，以及损坏时选择停机、修复还是重新加入。
客户端超时后不知道命令是否已提交。若直接重试非幂等命令，日志可能出现两次扣款。常用做法是携带客户端会话与序号，并把去重状态复制到状态机。
共识保证日志顺序，不保证外部副作用恰好一次。发送邮件、调用支付网关等操作仍需要事务发件箱、幂等键或补偿协议。
延迟、吞吐与可用性
稳定领导者下，一条日志通常需要到多数副本的网络往返和规定持久化才能提交。跨地域延迟会提高确认时间，但协议可流水化和批处理多个命令，因此往返延迟不是吞吐的简单硬上限。
热点领导者、网络带宽、磁盘和状态机执行都可能成为瓶颈。领导者故障时重新选举会造成短暂停顿；若多数副本无法通信，系统为保持安全性会停止提交。
无领导者协议或 EPaxos 一类路线可以减少某些热点和广域往返，但会增加依赖关系、冲突处理和实现复杂度。没有脱离工作负载的“最快共识算法”。
怎样验证共识实现
协议名称不是保证。审计应寻找：
- 明确的安全不变量、故障模型和持久化假设；
- 成员变更、快照、重启和版本升级规格；
- 模型检查或机器证明覆盖的具体模型范围；
- 确定性调度、网络分区、磁盘故障和长期随机测试；
- 对执行历史的线性一致性或应用不变量检查；
- 客户端超时、重试与去重的端到端语义；
- 生产监测能否发现任期震荡、提交停滞和副本偏离。
形式模型能发现协议状态机错误，故障注入能发现实现与运维边界问题。两者互补，但都不能替代真实应用不变量。
跨域连接
- 形式化方法与程序验证：共识的错误往往只在极罕见的时序交错下出现，测试与评审几乎不可能覆盖。规约加模型检查能在设计阶段穷尽被建模的状态空间，找出需要几十步轨迹才触发的缺陷——前提是模型确实刻画了真实环境。推论是：协议名称不构成保证，真正要审计的是不变量、故障模型与持久化假设。
- 选举制度：任何两个多数集合必定相交，这条集合论事实就是"不会同时出现两个合法领导者"的全部保证。可检验推论：直接把成员换成互不相交的另一组，新旧多数不再相交，因此必须有一个过渡配置——联合共识就是它的过渡条款。
- 认识论：在异步模型里，任何有限观察都无法区分"节点崩溃了"和"节点很慢"。这不是工程疏漏而是认识论限制，所以故障检测只能以假设的形式被显式加进模型——工程上的超时，就是把这条假设写成了一个数字。所以超时调长会更保守也更慢，调短会更灵敏却更容易误判仍然活着的节点。
- 概率论：不可能性结果排除的是确定性协议在所有允许执行上同时安全并终止。引入随机之后，不终止的执行依然存在，只是概率为零：安全性仍绝对，活性变成概率的。可见"绕过"不可能性，实质是换了前提。
- 机制设计：开放成员协议必须把投票权绑到稀缺资源上，否则身份可以免费复制。这把安全条件从"多数节点诚实"改写成"多数资源诚实"，于是财富或算力的集中度，直接变成协议安全模型里的一个参数。推论是：把共识机制换成代币，并不自动获得经典模型下的容错下界。
参考文献
- Lamport, L. (1998). The Part-Time Parliament. ACM Transactions on Computer Systems, 16(2), 133-169. DOI: 10.1145/279227.279229.
- Lamport, L. (2001). Paxos Made Simple. ACM SIGACT News, 32(4), 51-58.
- Ongaro, D., & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. USENIX ATC, 305-319.
- Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, 32(2), 374-382. DOI: 10.1145/3149.214121.
- Ben-Or, M. (1983). Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols. PODC, 27-30.
- Castro, M., & Liskov, B. (1999). Practical Byzantine Fault Tolerance. OSDI, 173-186.
- Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine Generals Problem. ACM TOPLAS, 4(3), 382-401.
- Gray, J., & Lamport, L. (2006). Consensus on Transaction Commit. ACM TODS, 31(1), 133-160.
- Howard, H., Malkhi, D., & Spiegelman, A. (2016). Flexible Paxos: Quorum Intersection Revisited. OPODIS. DOI: 10.4230/LIPIcs.OPODIS.2016.25.