← COMP5567 全部讲次
R01

Lab Test 复习资料|含 3PC、BFT、VR、Paxos

现有材料范围内的非官方复习,含英文术语、成立条件与自拟练习解析。

手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。

2026-11-10 · 并入 PBFT 讲义与 Lab 4 版 · 状态推演与英文解释

测验类型与范围边界

非官方 Lab Test 复习资料,不是 Midterm 真题。 现有课程信息列 Lab 10 Test:11-11,20:20-21:20,一小时、占 10%。最新考试安排与范围以讲师通知为准。Lab Test 的开闭卷尚未确认;期末开卷不能推导这次也开卷。

本册覆盖 2PC 实验(Lab 1)、3PC 实验(Lab 2)、VR 实验(Lab 3)、L06 的 2PC/3PC、L07 的 BFT、L08 的 VR 与 Paxos、Tutorial 1 的时钟,以及 HotStuff Part 1/2 的状态推演。L09 的 PBFT 与 PBFT 实验(Lab 4)放在复习资料 2,Lab 1 程序的实测结果放在复习资料 3。HotStuff 采用课程教学演示口径,不冒充所有同名变体的规则。课表列出主题不等于已给出考题范围。

推荐每次先写三件事:故障模型(crash / Byzantine)、网络假设、当前状态与收到的证据。然后逐事件更新表格,最后检查 safety 与 liveness。只背“多数通过”会把原子提交和拜占庭共识混在一起。

Lamport 与向量时钟

本册练习明确采用“每个本地事件/发送先加一,接收先合并再给自身分量加一”的约定。Lamport 接收更新 L←max(L,L_msg)+1。若 a happens-before b,则 L(a)<L(b);反向不成立,小编号本身不能证明因果关系。

向量时钟接收时逐分量取 max,再只增加接收进程自己的分量。在完整且正确记录事件的标准模型里,a 严格先于 b 对应 V(a)≤V(b) 逐分量成立且至少一个严格小于;若两向量互不支配,则相应事件并发。

补充·自拟例:P2 的向量为 (0,1,0),收到 (1,0,0),合并为 (1,1,0),给第二分量加一后为 (1,2,0)。不是把所有分量都加一。Vector timestamp 也不能与课程因果广播的 delivered 计数器混用;后者按协议的交付规则更新。

2PC 的决策与阻塞

Coordinator(协调者)发 PREPARE;participants(参与者)回答 YES/NO;正常提交要求固定参与者集合全部 YES,协调者形成 COMMIT 决定。有人 NO,则可决定 ABORT。这不是多数投票协议,两个 YES 不能覆盖一个 NO。

YES 表示已准备好接受最终决定,并非已经提交。可靠的崩溃恢复依赖适当的持久化日志等前提;课堂 socket 程序展示消息流,不足以自动证明持久化恢复已实现。

看到的证据 合理动作 为什么
协调者未作决定、尚未收齐 YES 可按协议超时决定 ABORT 尚未达成提交前提
任意参与者明确 NO 决定 ABORT 全员同意条件失败
参与者已 YES,未获最终决定 查询可靠决定或等待 其他人可能已收到 COMMIT,不能仅凭本地超时自行 ABORT
已有可靠的 COMMIT 决定 恢复后继续传播/执行该决定 不能因部分节点超时把已决定结果改成 ABORT

实验原页回查:5567-Lab 1 for 2PC.pdf p.12 是消息规则,p.38 是全员无回应练习,p.39 是 YES/NO/Timeout 混合练习。分析超时要先写“协调者尚未决定”还是“参与者已经 YES”;两种状态不可混答。Lab 1 四个演示情形、两个练习的实测结果和程序与 L06 的出入见复习资料 3:2PC 实验。

3PC 加入 pre-commit 阶段,非阻塞结论依赖同步性、故障和无分区等假设。它不是“多一个阶段就能在任意异步分区下安全且不停机”的通用解法。Safety 是不出现坏结果,liveness 是在约定条件下最终能推进;暂时停住不等于发生安全违例。

3PC 实验:决策与超时

L06 的 3PC 消息顺序是 CanCommit? → Yes/No → PreCommit → ACK → DoCommit → ack(L06 p.30–31)。PreCommit 在全体 Yes 之后才发,作用是告诉每个参与者“结果是提交”;参与者回 ACK,不再表态,也还不做不可撤销的事。任一 No、任一阶段等回复超时,协调者向全体发 abort(p.31–32);参与者等不到协调者时,选出恢复协调者,按参与者报告的状态决定(p.32–33)。

恢复协调者看到的状态 决定 L06 依据
有参与者已提交 向其余参与者重发 commit p.33 情形 ①
有人收到 PreCommit(Prepared),无人提交 补发 PreCommit,收齐 ACK 后提交 p.33 情形 ②、p.37
没人收到 PreCommit abort 或重启 p.33 情形 ③、p.35

Lab 2 程序是 1 个协调者加 P1–P3,有两处和 L06 不同,答题要分开写。第一,程序把 PreCommit 做成第二轮 yes/no 投票,可以投 no,超时也按 no 计(Lab 2 p.11、p.21);L06 里这一步只有 ACK。第二,协调者恢复时程序只看自己记下的阶段和 CanCommit 票,参与者状态只打印、不参与决定(p.22、p.25)。

Lab 2 情形 程序结果(实测) 对应 L06
Case I:三轮全 yes 提交 正常流程
Case II:CanCommit 2/3 跳过 PreCommit,直接中止 任一 No 即中止(p.31)
Case III:PreCommit 两 yes 一 no 2/3,中止 没回 OK 按崩溃处理,中止(p.32)
Case IV:协调者在 CanCommit 阶段崩溃 恢复后中止 无人 Prepared,abort(p.35、p.40)
练习 1:P3 在 CanCommit 不投票 约 60 秒后自动投 NO,中止 超时即中止
练习 2:P3 在 PreCommit 不投票 计数停在 2/3,60 秒后判 NO,中止 超时即中止
练习 3:协调者在 PreCommit 阶段崩溃 全体 PREPARED,恢复后提交 全体 Prepared 可提交(p.37、p.40)

课件 Case III 的步骤把 PreCommit 阶段的命令写成 cancommit 前缀,照抄时 PreCommit 计数一直是 0/3,60 秒后超时中止;改成 precommit 前缀才得到 2/3(Lab 2 p.21 实测)。练习 3 的标题写“发出 PreCommit 前崩溃”,实测打印的是 phase 2 崩溃,即 PreCommit 阶段(p.25)。

练习 3 还有一个课件没有的变式(实测):P3 在 PreCommit 投 no 后协调者崩溃,恢复时程序只看到 CanCommit 全 yes,照样发 COMMIT;P1、P2 写入数据,P3 拒绝,协调者等 ACK 超时后记 ABORTED。三方结局不一致,原子性被破坏。按 L06 p.33 情形 ②,应先补发 PreCommit、收齐 ACK 再提交,P3 回不了就整体中止。

对比项 2PC 3PC
阶段 Prepare/投票 → Commit 或 Abort CanCommit → PreCommit → DoCommit
提交条件 全体 Yes 全体 Yes,2/3 照样中止
投了 Yes、收不到决定的参与者 只能等待或查询,阻塞(L06 p.23) 有超时;可选恢复协调者,按状态推出结果(p.32–33)
成立前提 持久化日志、崩溃故障 同步网络、协调者是唯一崩溃者、无分区(p.35–40)
网络分区 阻塞,但不会分歧 可能一边提交、一边中止(p.34)

Lab 2 程序没有持久化,在本机上运行,演示不了网络分区;3PC 的非阻塞结论只能从 L06 的假设推,不能从这个程序推。

BFT:拜占庭将军的下界

L07 课件讲拜占庭将军问题、口头消息算法 OM(m)、签名消息算法 SM(m)。拜占庭故障节点可以任意行为,包括对不同的人说不同的话。两个条件(L07 p.9):Agreement,所有忠诚将军执行同一计划;Validity,指挥官忠诚时,忠诚副官都执行他的命令。

结论 内容 依据
口头消息下界 n ≥ 3m+1;3 个将军对付 1 个叛徒无解 L07 p.11–13
例:10 位将军 3m+1 ≤ 10 的最大 m 是 3,最多容忍 3 个叛徒 p.9
OM(m) 消息量 O(nᵐ),共 m+1 轮;n=4、m=1 共 9 条,n=7、m=2 共 156 条 p.19
签名消息 SM n ≥ m+1;叛徒无法伪造别人的签名 p.20–24
网络假设 OM 与 SM 都假设同步网络 p.24

PBFT 的门槛、换视图、检查点和 Lab 4 程序实测见复习资料 2:PBFT 与 Lab 4。逐个 case 的操作步骤和终端截图见 Lab 4 笔记。

VR:正常操作、换视图与恢复

VR(Viewstamped Replication)用 2f+1 个副本容忍 f 个崩溃,每一步要 f+1 个回应,主节点自己算一个(L08 p.7)。理由是多数集必相交:(f+1)+(f+1)=2f+2>2f+1(p.19)。节点数为偶数时按“超过半数”算,4 个节点要 3 个(p.17 Exercise 1)。

子协议 消息(L08) 要点
正常操作(p.14) ⟨request op,c,s,v⟩ → ⟨prepare m,v,n⟩ → ⟨prepareok v,n,i⟩ → ⟨reply v,s,x⟩ 主节点收齐 f+1 个(含自己)后执行并回复;s 是客户端给请求的编号,n 是主节点分配的全局操作编号(p.12)
换视图(p.15) ⟨doviewchange v,l,k,i⟩ → 新主节点收齐 f+1 个 → ⟨startview v,l,k⟩ 客户端超时或联系不上主节点时触发;新主节点的选法课件未讲
恢复(p.16) dorecoveryrequest(v,i) → 等 f+1 个 dorecoveryresponse(v,l,k) 补齐日志后回来当普通副本

k 是多数副本都已完成的最新操作编号(p.13):三个副本分别到 op 9、op 10、op 8,至少到 op 9 的有两个,构成多数,k=op 9;到 op 10 的只有一个。这一页右侧图注和左侧列表对不上,以列表为准。

Lab 3 程序:5 个节点,node0 是初始主节点,f=2,提交和换视图都要 3 个 yes,含发起者自己(Lab 3 p.3)。演示结果(实测):Case 1、2 alice 存 50 再取 20,余额 30;Case 3 四个备份全投 no,第 3 张 no 到达即中止;Case 4 node0 崩溃,node1 发起换视图,view=1,primary=1;Case 5 新操作编号接着排到 op 4,跨视图连续;Case 6 node0 恢复,重放 op 1、2、4 后成为备份。

项目 L08 理论 Lab 3 程序
备份的回复 只回 prepareok(p.14) 投 yes/no;投 no 的备份照样执行提交(p.20 实测)
超时 客户端超时触发换视图(p.15) 没有超时,票数不过线就一直挂着(p.22 变式实测)
新主节点 未讲选法(p.15) 新视图号 % 5,与发起者无关;node2 发起时当选的仍是 node1(p.3 变式实测)
换视图投 no 无此动作 被静默丢弃,不中止(p.23 实测)
新日志 按 k 确定已提交操作(p.13) 取最长的一份(读代码;演示中各节点日志一样长,差别未实测)
恢复等几个回应 f+1 个(p.16) 用第一个到达的回应(p.25、p.27 实测);第一个回应来自落后节点的情形未实测

VR 和 3PC 解决的问题不同(L08 p.20):VR 让一组副本按同一顺序执行同一串操作,主节点拿到 f+1 个确认就执行,少数副本无权否决;3PC 让一次分布式事务全体提交或全体中止,任何一个 No 都能否决。Lab 3 程序沿用 CanCommit、yes/no 的说法,外形像 3PC,答题按 L08 写 prepareok。

Paxos:prepare 与 accept

Paxos 在不可靠通信下就一个值达成共识,用 2f+1 个 acceptor 容忍 f 个崩溃,提案要其中 f+1 个接受;proposer 只有兼任 acceptor 时才计入法定人数(L08 p.22)。它优先保证一致,可用性不总能保证。

阶段 消息 规则(L08 p.25)
Phase 1 prepare(n) → promise proposer 选唯一编号 n 发给多数 acceptor;acceptor 承诺不再接受编号小于 n 的提案,并附上自己接受过的编号最大的提案
Phase 2 accept(n,v) → accepted 收到多数 promise 后发 accept;v 取 promise 里编号最大的提案的值,都没有才用自己的值;acceptor 只要没向更大编号承诺过就接受
Learn accepted → learner learner 看到多数 acceptor 接受同一个 v 就采纳

例(p.30–31):X 用编号 1 让 B、C 接受了 99,99 此时已被多数接受。A 想提 42,用编号 2 发 prepare,B、C 的 promise 都附上 (1,99),A 只能发 accept(2,99)。编号变大,值不变。

Exercise 2(p.32):acceptor A 已回 promise(5)。之后 accept(3,v) 被拒绝,3<5;accept(6,v2) 被接受,6>5,即使 A 没见过 prepare(6)。比较对象是已承诺的最大编号。

两个 proposer 轮流用更大编号发 prepare,会把对方的 accept 一直挡掉,形成活锁(p.33)。活锁不破坏安全性,因为一直没有值被选定。解法是选一个 leader 只由它提案,或者连续发 prepare 时加指数增长的等待。

Single-Paxos 每个值都要跑一次 prepare;Multi-Paxos 选定 leader 后,后续每个值只跑 accept 阶段,三个值分别需要 3 次和 1 次 prepare(p.34–36)。Exercise 3(p.38):3 个 acceptor 崩一个,accept 阶段和 learner 都等 2 个回应,协议照常推进。

HotStuff 的投票与证书

课件演示为 n=4、f=1、quorum=3。两组三票在四个节点中至少重叠 2 人,超过最多 1 个恶意节点,因此交集中至少一人诚实。还需要身份验证、同 view 不重复投票以及跨 view 的锁规则;集合相交不是完整安全证明。

补充通式:阈值 q 的交集下界为 2q−n,须大于 f;同时为了不依赖故障节点,还需 q≤n−f。常见 n=3f+1 时 q=2f+1。若总节点数改变,不能不检查交集就照搬阈值。

状态 含义 不等同于
highQC 已知最高 view 的有效 QC 最新收到的任意提案
lockedQC 限制后续投票的锁依据 已提交位置
committed block 不应再被冲突历史替换的提交位置 第一次获得 QC 的块

safeNode 核心:提案延伸锁定块,或携带的有效 justify QC 的 view 严格高于锁的 view。还须检查当前 view、指定 leader、父块和 QC 关联,以及本 view 尚未投票。Strictly higher 是 >,不是 ≥;“能过锁条件”也不等于“所有检查都通过”。

Timeout 触发换 view 的流程,不是清空锁和已提交历史的许可证,也不是对方确实作恶的证明。若只有两票,演示应停在未达阈值状态,不能临时把 quorum 改为 2。

Three-chain 与交易执行

以下只采用本课保守演示:B1→B2→B3 是直接父子链,view 连续且均取得对应 QC。收到 QC(B3) 时提交祖父 B1。先检查 parent、有效认证、连续 view,再更新状态,不是看见任意三张 QC 就提交。

新证据 highQC lockedQC commit
起点 B0 B0 B0
QC(B1) B1 B0 B0
QC(B2) B2 B1 B0
QC(B3) B3 B2 B1

若 view 为 1、2、4,即使父子链相连,也不能直接用本演示的连续三链条件提交 B1;需要后续满足规则的证据。这里不进一步猜某个未给出的实现会怎样更新每一字段。

交易依次经历 admission、mempool、proposal、certification、ancestor commit、execution、receipt。余额只在新提交块执行时改变,QC 本身不是执行回执。空块仍可推动先前有交易块的提交。

State machine replication 要求同初态、同确定性规则和同提交顺序。课件例 Alice、Bob、Charlie 各 100,先 Alice→Bob 80 再 Alice→Charlie 80,则第一笔后为 20、180、100,第二笔余额不足而失败,终态不变。两笔都能通过基于旧余额的入池检查,不等于两笔都能执行成功。

处理过同一 transaction id 时返回旧回执,不再次扣款;但 id 去重不自动等于完整用户授权和防重放。废弃未提交分支中的交易可在新分支重新包含,不能把“曾提案”当成“已执行”。

实验练习与英语答题

按本课材料做四类纸面或教学环境练习:全员响应、一个节点不响应、只有两票、leader 超时换 view。每次记录收到的消息、前状态、条件判断、后状态;课程 starter 是否满足预期须另行实际运行,本册不把截图中的测试数量当本轮执行结果。

2PC 可再练 YES/YES/NO 和 YES/NO/Timeout;HotStuff 可练正常三链和跳 view;交易层可练重复 id、余额不足和废弃提案。先预言结果,再观察程序;若不一致,先查实现版本和前提,不马上判课件错误。

英文答题句型:“The quorum is insufficient, so progress stops; this does not by itself violate safety.” 或 “The replica has voted YES but has not learned the decision, so timeout alone does not justify aborting.” 重点是 because、under the stated assumptions、not sufficient、strictly higher。

先做题再看答案

英文自测 1:时钟、2PC、HotStuff · 英文自测 2:3PC、BFT、VR、Paxos · 英文自测 3:PBFT 与 Lab 4

回查与后续补齐

回查 L02 与 Tutorial 1 的时钟、L06 的 2PC/3PC(p.23、p.29–40)、2PC Lab p.13–16、p.19–34、p.38–40;3PC Lab p.11、p.20–25;L07 p.9–24;L08 p.7、p.12–20、p.22–38;VR Lab p.3、p.20–27;L09 p.6–25;PBFT Lab p.3–5、p.14–29;HotStuff Part 1 p.7、p.12、p.17-19;Part 2 p.8-18。页码均为 PDF 页序。

后续核对:正式 Lab Test 范围和开闭卷要求以讲师通知为准;VR 程序“取最长日志”和“恢复时第一个回应来自落后节点”两点没有实测;PBFT 程序另补测了两种情形:有节点崩溃时检查点停在 3/4、不写文件也不超时;换视图后由副本当主节点时,它自己数出 5/4,详见 Lab 4 笔记。旧课程信息中的概括图不可替代协议假设:Paxos/VR/Raft 是典型崩溃容错协议,PBFT/HotStuff 处理拜占庭故障;不可把所有协议一起称为“任意故障下不阻塞”。

下一页 →
R02 Lab Test 复习资料 2|PBFT 与 Lab 4

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。