ABD 寄存器

一次写返回，意味着足够多副本已经保存“不早于这次写”的状态。下一次读不必联系同一批副本：任意两个大小为 $q$ 的集合相交，因为 $2q>n$。这是法定人数系统公理库法定人数系统Quorum system · Quorum family以相交的副本子集族在部分参与者之间传递一致性证据的模型。在证明中承担的工作。

然而，读可能撞见尚未完成的写：某个新值才传播到一个副本，读者就选中了它。此时写者没有建立多数证据。读者若立刻返回，后继读可能完全错过这个值。写回让读者在公开结果前，亲自把“此版本已经被观察到”的证据传播到多数。它帮助尚未完成的写成为后继观察必须尊重的历史。

服务器只接受更高版本，使迟到消息不能撤销这份证据。旧版本请求仍须确认：某个读者正在传播版本 $7$，服务器已到版本 $9$，它已满足“至少为 $7$”的义务；拒绝回复反而可能让该读者无限等待。

多写者增加的难点是：一个刚开始工作的写者，私有计数器可能远远落后于已经完成的读写。ID 可以打破两个并发写者选择同一计数时的平局，却不能让“后来才调用”的写自动排在前面所有完成操作之后。写前查询负责接收多数中已有的标签下界，再把计数加一；读后写回负责让一个已公开的读结果也拥有这样的多数下界。两者共同把客户端之间的实时先后传到服务器状态中。

这与逻辑时钟公理库逻辑时钟Logical clock · Lamport clock为事件赋整数时间戳并保证因果先后蕴含时间戳递增。的标量加身份形式相似，但标签生成的事件不同：此处的计数来自一次 quorum 查询，而非每发生本地事件就加一。标签较小的并发写完全可能较晚返回。证明所需的只是实时先后必然得到相应标签不等式，不需要由标签反推消息因果或墙钟时间。

三个副本上的新旧倒退 ​

令 $n=3,f=1,q=2$，初值为 $0$。写者调用 $W=\mathrm{write}(1)$，版本为 $1$，目前只有 A 收到更新，B、C 的更新仍在途中。副本状态为

若删掉读的写回阶段，$R_1$ 查询 A、B，取最大版本后返回 $1$。等 $R_1$ 返回，$R_2$ 才调用，查询 B、C，返回 $0$。两个读都联系多数，而且都可能与尚未返回的 $W$ 重叠；这仍不能成为原子历史：$R_1=1$ 要求 $W<R_1$，实时顺序要求 $R_1<R_2$，而 $R_2=0$ 要求 $R_2<W$，三者成环。

真实 ABD 在 $R_1$ 返回前向全体写回 $(1,1)$。设 A、B 的确认先到，便有 A、B 的版本都至少为 $1$。此后 $R_2$ 查询 B、C 时，B 的回复至少为版本 $1$，所以 $R_2$ 不可能选中版本 $0$。若 B 在确认后、$R_2$ 查询前崩溃，$R_2$ 就不能再用 B 的回复凑齐本轮多数，只能由 A、C 回应，其中 A 同样带着证据。

从相交证明到完整原子历史 ​

关键不变量有两个：每个副本版本单调不降；每个非初始 $(t,v)$ 都来自唯一写操作，读者只能复制它。假设某传播阶段已得到多数 $Q$ 的确认，传播版本为 $t$；之后才开始的查询得到多数 $Q^{\prime }$ 的回复。取 $s\in Q\cap Q^{\prime }$。服务器 $s$ 先处理旧传播并确认，再处理后发起的新查询，故新回复版本至少为 $t$，查询最大值也至少为 $t$。这里同时使用了集合相交、请求的因果先后和状态单调性。若把以前缓存的回复冒充新查询回复，或允许服务器版本倒退，交集公式便救不了证明。

给每个完成读赋予它选中的版本，每个写赋予自己产生的版本。上面的引理说明：写返回后才开始的读，其版本不小于该写；读返回后才开始的读，其版本不小于前读，因为前读也完成了传播。还有两种实时关系：先写后写的版本严格增加；若一个读返回后才调用某写，该写版本也严格大于读版本，因为读到的版本已经由单写者产生，而新调用尚未发生。

因此可为每个有限历史构造合法顺序：保留全部完成操作，以及作为完成读来源的未完成写；给这些未完成写补上响应，删除其他 pending 操作。将写按版本递增排列，把版本 $t$ 的所有读放在产生 $t$ 的写之后、下一更高版本写之前，同版本读按实时先后排列；版本 $0$ 的读放在初始化之后。四种实时关系都由前述不等式保持，每个读前面最近的写也恰好具有版本 $t$。这就得到寄存器顺序规格的线性化见证，而不只是“每个读各自合理”。

尤其不能因为写者未收到多数确认，就从历史中删除已经被完成读观察到的写。上例允许把 pending 的 $W$ 补全后排在 $R_1$ 前；这是历史的 completion，不是假称真实写者已经返回。

六个操作：迟到确认与崩溃写的来源 ​

仍取三个副本 A、B、C 和 $q=2$。两位写者身份为 $1,2$，令

下表用 $0$ 表示初始整对 $({\tau }_0,\mathrm{zero})$，用 $a,b,c$ 分别简记 $(a,\alpha ),(b,\beta ),(c,\gamma )$。每格都表示服务器处理了本行消息之后的状态；未列出的消息可以继续在途中。读者独立于两位写者。

两个初始查询都只看到计数 $0$，所以第一批写的计数相同，身份决定 $a<b$。而 $W_1^{\prime }$ 的查询看到计数 $1$，故生成 $(2,1)$，它大于 $(1,2)$，不能仅按身份比较。时刻 10 的 ACK 同样值得检查：B 并没有写入 $\alpha$，但它保存 $b>a$，所以满足 $W_1$ 的传播下界。A 的旧确认也仍然有效，因为 A 此后只会升高标签。

把崩溃写 $W_2$ 在数学历史末尾补上响应，得到完整线性化顺序

$W_1$ 虽然在 $R_1$ 之后才实际返回，两者却重叠，允许如此排序。$W_2$ 的写值已经被完成的 $R_1$ 读出，必须保留来源写；补全响应并不声称崩溃客户端真的恢复返回。表中三个读分别读到最近前驱写的 $\beta ,\beta ,\gamma$，而 $W_1$ 的值可以在没有读返回它的情况下被下一写覆盖。

MWMR 的不变量与完整线性化证明 ​

同一标签只携带一个写值 ​

服务器标签单调不降，直接来自 UPDATE 只接受严格更大标签。每个正标签最初由一次写产生，读者只转发原有整对；因此只要证明不同写不会生成同一标签，就能归纳得出“同一标签永远对应同一值”。不同身份的写有不同第二分量。对同一身份的两次连续写，前次已经返回才会调用后次；前次确认多数与后次查询多数相交，交点在确认时已达到前次标签，以后不会降低。因此后次查询得到的最大计数不小于前次计数，加一后严格更大。跨越任意多次同身份写也同理。初始标签由初始化单独提供，不会被普通写生成。

这也解释了相等标签 UPDATE 不必替换值：相等标签的合法消息携带相同值，保留原状态不会丢失另一项写入。该结论依赖消息不能伪造、同一写者不并行复用身份，而不是仅靠字典序的定义。

多数如何把下界传给下一次查询 ​

设某操作的传播阶段以标签 $\tau$ 收到多数 $P$ 的确认，随后该操作返回；另一操作在它返回后才调用，查询阶段从多数 $Q$ 获得回复。取交点 $s\in P\cap Q$，有如下消息先后链：

因此 $s$ 的新回复至少含标签 $\tau$，查询选出的最大标签也至少为 $\tau$。匹配操作身份保证这里确实是新查询的回复。若交点在处理本轮 QUERY、发出回复之前已经崩溃，它便不能贡献本轮回复；若它发出回复后才崩溃，已发出的匹配回复仍可计入 $Q$，发送时的标签下界已足够支撑证明。因此，证明并未要求旧多数永远全部存活。

给每个完成读赋其选中标签，给每个已经生成标签的写赋其新标签。若 $o_1$ 返回后 $o_2$ 才调用，上述引理得到全部四种实时关系：

最后一行正是多写者情况下不能借用“唯一写者早已生成该版本”来证明的地方：承担这项工作的机制变成了写前查询。

从标签构造整个历史的顺序见证 ​

取任意有限历史，保留全部已完成操作。对每个读到非初始标签的完成读，再保留生成该标签的唯一来源写；若来源写 pending，就在历史末尾给它补上响应。删除其余 pending 操作，包括未完成读。来源写可能只传播到一个副本便崩溃，这不会改变上述选择。

将所有保留写按标签严格递增排列。每个读放在同标签来源写之后、下一更大标签写之前；初始标签的读放在所有普通写之前。同标签的读按原实时偏序的任意线性扩张排列。因为写标签唯一，这条规则不会在两个同标签写之间发生歧义。

检查实时顺序即可确认构造有效。不同标签操作的实时边由四种不等式保持；同标签读之间的边由线性扩张保持；同标签的写在读之前，而该读不可能在来源写调用前就返回，因为其标签尚未产生。补全的写没有原始返回，所以不会凭空产生一个必须排在后来调用之前的返回事件；但若某完成操作先于来源写调用，其标签关系仍由相同查询引理约束。这样所有原实时边都保留，每个读的最近前驱写又恰好是同标签来源写，满足线性一致性公理库线性一致性Linearizability每次操作可放置在调用与返回之间的单点，使历史等价于满足实时顺序的顺序规范。的顺序寄存器规格。

这是整个历史的线性化证明，不必把每次查询中某条消息的处理瞬间指定成固定线性化点。特别是并发写的标签顺序可以与响应顺序不同，只要没有倒置非重叠操作的实时边。

三处删减分别破坏什么 ​

只用私有计数器加身份，删去写前查询。 让身份 2 的首写以 $(1,2)$ 写入 $\beta$，更新全体并完成。随后身份 1 才进行自己的首写，以私有计数产生 $(1,1)$ 并写入 $\alpha$。所有副本都保留较高的 $(1,2)$，但仍正确确认旧更新，于是第二写完成。再调用读，它返回 $\beta$。三个操作不重叠，顺序规格却要求读到最近写的 $\alpha$。两个标签一直唯一；失败的是标签没有保持实时先后，不能靠 ID 打破平局修复。

删去读后写回。 让一个新写只把 $(a,\alpha )$ 送到 A 就崩溃，B、C 仍为初态。$R_1$ 查询 A、B 返回 $\alpha$，之后调用的 $R_2$ 查询 B、C 返回初值。这正是前面 SWMR 新旧倒退反例在二元标签下的同一机制：任何 completion 都必须同时满足 $W<R_1<R_2<W$，无法消除环。写者拥有多少身份不改变读结果公开前需要传播证据的事实。

仅在标签真正替换时 ACK。 某低标签传播仍在途中，更高并发写先更新全部正确副本。低标签请求到达后没有任何副本替换状态，若因而都不 ACK，正确客户端就永远等不到多数。单调性仍在，却失去了终止；相等标签也应确认，否则读者把刚查到的标签写回原副本便可能被无谓阻塞。

终止与通信成本 ​

至少 $n-f\ge q$ 个副本正确。正确客户端逐一发出请求后，这些副本最终收到、处理并响应；因此 SWMR 写的一个传播阶段、两种读的查询与写回阶段，以及 MWMR 写的查询与传播阶段都能完成。并发更新不会使等待条件失效，因为较旧更新也收到确认。这个终止论证不需要辨认谁崩溃，更不需要给消息延迟设超时上界。

在不重传的上述可靠消息接口下，每阶段最多 $n$ 个请求和 $n$ 个响应，SWMR 写最多 $2n$ 条消息，两种读与 MWMR 写均最多 $4n$ 条消息，均为 $O(n)$；迟到响应也计入其所属阶段。每个副本存一对版本和值，客户端还需至多 $O(n)$ 个回复身份及查询结果。版本号随写次数增长，因此这不是固定比特空间算法；$k$ 次写后的版本字段需要 $O(\log (k+1))$ 比特，消息还包含值和请求身份。两个通信阶段也不等于两段有界墙钟时间：异步模型只给最终完成，没有统一响应时限。

MWMR 标签还包含写者身份，且请求身份不能复用；本页没有提供固定比特空间的循环回收办法。若 $n\le 2f$，本协议无法同时满足严格多数相交和任意 $f$ 次崩溃后的可用性。永久隔离在少数分区中的客户端也不能完成这些阶段，这超出了可靠最终交付的前提。

寄存器接口的边界 ​

ABD 说明可靠消息、正确多数和读后写回足以构造读写对象；写前查询使这套证据传递进一步覆盖多写者。它没有实现任意对象上的原子读改写，也不把多个寄存器的一组读自动变成快照。本页的一阶段写依赖唯一写者，双阶段写则允许多个良构客户端并发写；有界版本、恢复和重配置仍各需独立协议。

自测：在三副本例子中，把 $R_1$ 的写回确认集合改为 A、C，随后 $R_2$ 查询 A、B，会从哪个交点继承证据？若写者在只更新 A 后崩溃，正确读者还能完成吗？检查标准：交点是 A；只要正确副本仍不少于两个且通信最终交付，读者可以传播已见到的合法版本并完成，不必等待原写者复活。