← COMP5567 全部讲次
R05

期末复习资料|Final Review:课程地图、四个例子和 2025 卷形式

非官方复习:按讲师期末复习课整理课程结构、L1–L11 提纲与本站讲义入口、四个把知识点串起来的例子、原子提交与共识的关系,以及 2025 年期末卷的题型和分值。

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

2026-11-15 · 按 Final Review 课件整理

范围与读法

非官方期末复习资料,不是今年的考题。 考试日期、考场、范围和是否开卷以讲师通知为准。本页按 Prof. Bin Xiao 的 Final Review 课件整理:先看课程结构,再按讲次回到本站讲义,最后看 2025 年卷子长什么样。

课件 31 页,分四块:课程结构图和每讲一页提纲;四个现实例子;原子提交与共识的关系;2025 年期末卷 Part C 的题面截图。中间两页是讲师招 Guided Study 和 Dissertation 学生的介绍,和考试无关,本页不收。

课程结构:三条线

结构图把十一讲分成三块。读的时候按三条线串:

线 讲次 一句话
分布式系统基础 L2 → L3 → L6 先给事件排先后,再管消息按什么顺序交付,最后让一笔事务全提交或全中止
共识 L7 → L8 → L9 从会撒谎的将军讲起,到容忍崩溃的 VR、Paxos,再到容忍拜占庭的 PBFT
区块链系统 L1、L4、L5、L10、L11 比特币、以太坊、HotStuff、Solana,把前两条线的东西装进真实系统

结构图上给几讲写了关联说明:L2 是 Event ordering(例如向量时钟);L3 是 Message correct order(例如用向量时钟实现的 CO-URB,以及 TOB);L6 是 Commit/Abort a Tx(例如 3PC)。L6 那格原话还有一句「based on TOB for orders」,L6 讲义本身没有把 3PC 建在全序广播上,这句只当结构图上的关联说明读。

L1–L11 提纲与本站讲义

课件每讲一页提纲,只列小节名,不给权重。下面把提纲和本站对应的讲义页对上。

L1 区块链导论:区块链的整体图景、区块结构、共识协议、分层结构。 L01a 共享账本、L01a-2 区块头与挖矿、L01b 篡改与最长链、L01b-2 坏节点与分层

L2 分布式系统导论:关键要素、同步模型、时间与顺序、逻辑时钟(Lamport、向量)、CAP。 L02a 分布式系统是什么、L02a-2 同步模型与 FLP、L02a-3 安全性、活性与 CAP、L02b-1 happens-before、L02b-2 Lamport 时钟、L02b-3 向量时钟

L3 分布式广播:广播原语(Best-effort、Reliable、Uniform RB);交付顺序(FIFO-URB、CO-URB、TOB、FIFO-TOB)。 L03a-1 可靠性分三级、L03a-2 URB 协议、L03b-1 FIFO、L03b-2 因果序、L03b-3 全序、L03b-4 gossip

L4 比特币:区块信息、交易与 UTXO;挖矿过程与目标阈值;Merkle 树、双花、PoW 与矿池、P2P 与 gossip。 L04a UTXO 与 coinbase、L04a-2 区块头与难度、L04b 分叉、双花与过半算力攻击、L04b-2 Merkle、矿池与 P2P

L5 PoS 与以太坊:PoW、PoS、以太坊 Casper 协议(LMD GHOST 投票、检查点与 FFG 投票)。 L05a PoW 与 PoS、L05a-2 Nothing at Stake 与罚没、L05b 信标链与 LMD GHOST、L05b-2 检查点与最终性

L6 原子提交:2PC 及其恢复;3PC 及其恢复。 L06a 原子提交、L06a-2 2PC 流程、L06a-3 2PC 阻塞、L06b 3PC 与恢复、L06b-2 分区弱点

L7 拜占庭容错:两将军问题;口头消息算法 OM、签名消息算法 SM。 L07a 两将军与拜占庭将军、L07b 3m+1 下界、L07c OM、L07d OM 的代价、L07e SM

L8 VR 与 Paxos:VR 的正常操作、换届、副本恢复;单值 Paxos、Multi-Paxos。 L08a VR 正常操作、L08a-2 VR 换届与恢复、L08b Paxos 两阶段、L08b-2 活锁与 Multi-Paxos

L9 PBFT:正常操作、视图切换;经典共识协议小结。 L09a 舞台与角色、L09b 正常操作、L09c 视图切换、L09d 检查点与协议对照

L10 HotStuff:HotStuff、门限签名。 L10a Basic HotStuff、L10b 换 leader、L10c 为什么三轮、L10d 门限签名、L10e Chained HotStuff

L11 Solana:区块链时代的协议;Solana 的 PoS、PoH、TowerBFT。 L11a 总览与最终性、L11b leader 轮值表、L11c PoH、L11d Tower BFT 投票、L11e Tower BFT 锁定

四个把知识点串起来的例子

课件挑了四个现实场景,各对一讲。每个例子要会的是那条判定规则。

向量时钟:协同编辑(L2)。Alice 和 Bob 离线编辑同一份文档「Hello」:Alice 在后面插入「, world」,Bob 插入「!!!」。Alice 那次编辑的时钟是 [A:1, B:0],Bob 的是 [A:0, B:1]。重新联网同步时两边互不小于对方,判为并发,系统检测到冲突,按合并策略处理,得到 Hello, world!!!(或另一种拼法,取决于策略)。没有时钟、只按「最后写的赢」,就会丢掉其中一次编辑。

要会的规则:一个向量逐分量都不大于另一个、且至少一位更小,两者才有先后;否则就是并发。Lamport 时钟只能排出全序,看不出两次编辑其实互不知道。

FIFO-URB:分布式聊天(L3)。要求每个人自己发的消息按发送顺序出现。每个发送者给自己的消息编序号:Alice 先发「Hi」(seq=1),再发「How are you?」(seq=2)。网络让 Bob 先收到第二条,FIFO-URB 先把它缓存,等「Hi」到了再按序交付两条。

FIFO 只管同一个发送者。Bob 回复 Alice 这种跨发送者的先后要因果序(CO),要所有人看到同一个顺序得用全序广播(TOB)。

原子提交:跨行转账(L6)。Alice 从 Bank A 转 $100 给 Bank B 的 Bob,两家银行在不同服务器上:A 扣款、B 入账,必须一起提交或一起中止,不能只做一半。用 2PC 或 3PC 协调。课件的类比是一群朋友买团体票:要么人人付钱拿票,要么谁都不买。

共识:配置中心(L8、L9)。etcd、Consul 这类分布式键值存储,一组服务器存一个大型 Web 服务的配置。改一个键(例如 “max_connections” 改成 1000)时,所有服务器必须对新值达成一致,用 Paxos、VR、PBFT 一类共识协议。类比是一群朋友定去哪吃饭,最后必须是同一个地方。

原子提交与共识

课件 p.20 讲两者的关系,分三层:

  1. 关系:原子提交可以看作共识的特例,一组节点对一个决定(commit 或 abort)达成一致;也可以用共识来实现原子提交,所有参与者跑一次共识决定 commit 还是 abort。
  2. 实际系统里分层叠用:共识保证每个分片(shard)内的日志一致,原子提交保证一笔事务在所有相关分片上一起提交。
  3. 代价:每笔事务都跑一次共识更贵、更复杂;只协调一组资源管理器上的单笔事务,原子提交协议更简单、更高效。

两者的差别看 L06a 的对照:原子提交里任一参与者投 No、或在决定形成前失败,事务就对全体中止,每个人都有否决权;共识只要求正确节点决定同一个值,允许一定数量的节点故障,其余节点照样推进。所以「原子提交是共识的特例」要带条件读:它多了一条约束,全票 Yes 才能 commit。

课件这页有一处错。 课件举 Google Spanner 为例,说它在每个 shard 内用 Raft 复制日志、跨 shard 用 2PC。Spanner 论文(Corbett et al., OSDI 2012)里 shard 内复制用的是 Paxos。用 Raft 做分片内复制、2PC 跨分片的是 CockroachDB、TiDB 一类系统。课件要讲的分层关系本身没错,答题时举例别写 Spanner 用 Raft。

2025 年期末卷的形式

课件最后十页是 2025 年期末卷的截图。卷面信息:

项 内容
时长 3 小时
开卷方式 只准带纸质笔记和书
题量 共 23 题,全部作答
Part A Q1–10,判断题(T or F),共 10 分
Part B Q11–15,单选题,共 10 分
Part C Q16–23,简答和画图,每题 10 分,共 80 分
合计 100 分

全卷 13 页,注明部分页被略去,Part A、B 的题目没有放出来,本页也不补、不猜。课程信息里期末占总评 70%;今年的时长、开卷规则以讲师通知为准。

Part C 八道大题和讲次的对应:

题 讲次 题型
Q16 L2 Lamport 时钟、向量时钟 填表计算
Q17 L3 URB 重画流程图
Q18 L3 CO-URB 填交付顺序、m.past、delivered 向量
Q19 L6 3PC 画时序图(含恢复)
Q20 L8 VR 画时序图(含副本恢复)
Q21 L7 OM、SM 简答
Q22 L9 PBFT 画图并计票
Q23 L4、L5 PoW 与 PoS 简答

L1、L10、L11 在 Part C 没有单独出题;Part A、B 是否考到看不到。

截图不全。 课件里 Q18 少了第 (4) 问,Q21、Q23 少了第 (3) 问,只看复习课的截图会以为这三题少一问。完整题面在卷子原件里。

逐题的题面转述和参考解答:2025 期末真题解析(一):Q16–Q18、(二):Q19–Q20、(三):Q21–Q23

复习顺序建议

按 2025 年卷子的题型,时钟和 CO-URB 是一步一步算的填表题,最容易拿分也最容易因为一格算错连环扣分,建议先把 L02b-2、L02b-3、L03b-2 的例题自己重算一遍。3PC、VR、PBFT 是画图题,要会的是每一轮发给谁、收齐几个才往下走、崩溃后谁接手。OM/SM 和 PoW/PoS 是简答题,要能用英文写出步骤和理由。

以上是按去年卷子推的复习重点,今年的范围和题型以讲师通知为准。

这组材料已读完,可以回课程页选择配套资料或练习:COMP5567 课程页。

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