SuperAPI AI 工具集

abd-quorum-registers

智能体与模型

查看项目

更新于 10-16 03:43

技能介绍

用途:ABD(Attiya、Bar-Noy、Dolev 1995)是在异步消息传递网络上模拟线性一致共享内存寄存器的经典崩溃容错读写协议,用于设计分布式 KV 存储、复制寄存器,以及证明仲裁协议的线性一致性。

三大支柱:一是仲裁交集,任意读仲裁 Q_R 与写仲裁 Q_W 满足 Q_R ∩ Q_W ≠ ∅,多数派仲裁下崩溃容错 f < n/2,拜占庭容错需 n ≥ 3f + 1;二是时间戳 ⟨ts, writer_id⟩ 给写入建立全序;三是读后写回,读者在返回前将最高时间戳的值写回完整仲裁,防止新旧倒置。

协议阶段与复杂度:SWMR 写为 1 RTT、2n 消息;SWMR 读分查询与写回两阶段,2 RTT、4n 消息;MWMR 写为 2 RTT、4n 消息,读与 SWMR 相同。相关资料给出上述复杂度均为最优。线性一致性证明骨架含写入全序、仲裁交集见证、新鲜度保证、写回防倒置、实时顺序和每时间戳单值六项。

限制与扩展:分区下线性一致性不可能(CAP);MWMR 快速 1-RTT 读在 n > 5 时不可能;寄存器无法实现等待无关共识(共识数为 1);需要领导者状态机复制应改用 Paxos/Raft,追求可用性最终一致应改用 CRDT。扩展包括 Coded ABD(纠删码降低复制开销)、RAMBO(可重配置仲裁)、Fast reads、拜占庭 ABD 与多对象原子快照。

该技能提到 Trit 0(ERGODIC)属性和 GF(3) 三重组守恒等元数据,但这些并非 ABD 协议本身的算法内容;具体安装命令资料未提供。