法定人数系统

形式陈述 ​

给定副本集合公理库集合Set由确定成员组成的数学对象；成员关系而非表示顺序决定集合。 $U$，法定人数系统是一个非空集合族 $\mathcal{Q}\subseteq 2^U$，其中每个 $Q\in \mathcal{Q}$ 称为一个 quorum。若所有承担冲突操作的 quorum 都满足

$$Q_1\cap Q_2\ne \varnothing ,$$

则任意两次此类操作都共享至少一个参与者，旧证据与新证据因而有机会相遇。系统还需满足相对于故障集合 $F$ 的可用性：故障发生后至少存在一个 $Q\in \mathcal{Q}$ 使 $Q\cap F=\varnothing$，否则相交性虽保住了安全，操作却无法完成。

复制寄存器常把读集合族 ${\mathcal{Q}}_r$ 与写集合族 ${\mathcal{Q}}_w$ 分开。若每次从 $N$ 个副本中读 $r$ 个、写 $w$ 个，为使每次读与最近写相交以及任意两次写相交，需要

$$r+w>N,2w>N.$$

这两式只给出相交的组合条件；版本号、写入顺序和并发冲突处理仍需协议定义。在最多 $f$ 个 Byzantine 节点的模型中，交集非空不够，因为唯一交点可能说谎；若要保证交集中至少一个正确节点，就须令相关 quorum 的交集大小大于 $f$。

直觉 ​

quorum 的作用是避免每次操作都等待全体副本，同时又不让关键证据彼此错过。一次写只接触部分节点，后续读取也只接触部分节点，但两组人必然有重叠，于是至少有人见过新状态。它建立的是“证据交接通道”，不是自动的一致性算法：交点上的节点需要保存什么、如何比较版本、何时承诺，都要由上层协议补齐。

安全与可用性在这里拉向相反方向。quorum 越大，两个集合越容易产生足够大的交集，也越能排除矛盾决定；与此同时，一次操作要等更多节点，故障或分区时更难凑齐。quorum 系统的设计就是在给定故障模型下选择这条边界，而不是机械地取简单多数。

例子与边界 ​

设 $N=5$，选择 $r=3,w=3$。任意读集合与写集合大小之和为 $6>5$，故至少共享一个副本；任意两个写集合也至少共享一个副本。一次操作只需三个响应，所以两个副本不可用时仍可能完成。若读写集合都只取两个，则集合 $\{1,2\}$ 与 $\{3,4\}$ 可以完全分离，读者可能看不到已完成写入的任何见证。

网络分区时，两个分区不可能都包含同一多数 quorum。较小分区停止服务，保住了双方不能各自形成冲突决定的安全性；若强行允许两边都继续写，则必须接受冲突合并或放弃强一致保证。这里的取舍来自集合相交事实，不是通信库的偶然行为。

在 $N=3f+1$ 的常见 Byzantine 配置中，大小 $2f+1$ 的两个 quorum 至少相交 $f+1$ 个节点，即使其中 $f$ 个都是 Byzantine，仍留有一个正确节点。这个计数绑定于“最多 $f$ 个 Byzantine 故障”的假设；换成崩溃故障、认证广播或不同提交规则后，阈值必须重新推导，不能把 $2f+1$ 当作 quorum 的定义。

推论与应用 ​

Paxos公理库PaxosPaxos consensus通过相交 quorum、递增 ballot 与已接受值继承规则，在崩溃故障下为单个共识实例选择唯一值。 与 Raft公理库Raft 共识协议Raft consensus algorithm以任期、选主和复制日志实现崩溃容错共识的协议。 利用多数集合的相交性，让不同轮次或任期的决定通过共同节点传递；读写复制可用不对称的 $r,w$ 调整读延迟与写延迟。PBFT公理库实用拜占庭容错Practical Byzantine Fault Tolerance · PBFT在部分同步网络与至多 f 个拜占庭副本下使用 3f+1 副本实现状态机复制的协议。 等 Byzantine 协议则要求交集不仅存在，还含足够的正确见证者。加权投票、网格 quorum 与分层 quorum 表明，简单多数只是集合族的一种选择。

对具体协议，验证 quorum 不能只检查集合大小。还应写清哪些操作族必须互相相交、故障后哪些 quorum 仍可达、交集里需要多少正确节点，以及节点保存的证据是否跨轮次有效；缺少任一项，相交公式都不足以推出协议安全。

参考资料

• David K. Gifford, “Weighted Voting for Replicated Data,” Proceedings of the 7th ACM Symposium on Operating Systems Principles, 1979, pp. 150–162。
• Dahlia Malkhi and Michael Reiter, “Byzantine Quorum Systems,” Distributed Computing 11, 1998, pp. 203–213。