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 处理拜占庭故障;不可把所有协议一起称为“任意故障下不阻塞”。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。