← COMP5567 全部讲次
Q03

Lab Test 英文自测|S23-S31:PBFT、Lab 4 与 Lab 1

非官方自拟练习:PBFT 的 prepare 失败、commit 的必要性、视图切换、检查点,以及 Lab 4、Lab 1 程序的计票、超时与崩溃情形,题干英文、解析中文附页码。

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

非官方自拟练习,考试安排与范围以讲师通知为准。 先用英文作答,再逐题展开解析。

范围与作答约定

本页 S23–S31 接着英文自测 2 编号:S23–S28 覆盖 L09 的 PBFT 和 PBFT 实验(Lab 4),知识点见复习资料 2;S29–S31 是 2PC 实验(Lab 1)的程序题,知识点见复习资料 3。涉及 Lab 程序输出的题,解析里标明实测、读代码或未实测;页码均为 PDF 页序。

作答时先写故障模型(Byzantine)和 f 的取值,再写理论答案;Lab 程序和讲义不一致时两边都写,并说明以哪一边作答。

题目与解析

S23 · PBFT prepare failure

n=4, f=1. R1 is the primary. R2 sends a matching PREPARE(X, d), R3 stays silent, and R4 sends PREPARE(X, d′) with a different digest. Does R1 become prepared? Is safety or liveness affected?

S23 · 查看答案与解析

No; safety holds, liveness is lost for this round. 匹配 (X, d) 的只有 R1 自己和 R2,2 < 2f+1 = 3,进不了 prepared,也就不会 commit 和回复(L09 p.14)。一个沉默加一个作恶超过了 f=1 的预算,系统停住而不是出错,之后靠重传或视图切换恢复。

S24 · Why PBFT needs commit

Suppose replicas execute an operation as soon as they are prepared, skipping the commit phase. Describe how a Byzantine primary plus a view change could make two honest replicas execute different operations at the same sequence number.

S24 · 查看答案与解析

The primary lets only one replica collect a prepared certificate, then the view change loses that evidence. L09 p.21:A 作恶,只让 C 收齐 seq 10 上 x 的证书,C 执行 x;新主节点 B 收到 A、B、D 的 VIEW-CHANGE,里面没有 x 的证书,seq 10 改分给 y,B、D 执行 y。加上 commit 后,执行要 3 个匹配 COMMIT,其中至少 2 个来自已 prepared 的诚实副本,它们与新主节点收的 3 份 VIEW-CHANGE 至少重叠 2 个,x 必然被带进新视图。

S25 · PBFT view change

n=4 and the primary of view 0 stops responding. Which replica is the primary of view 1, how many VIEW-CHANGE messages does it need, and what does its NEW-VIEW message contain? Who is the primary of view 4?

S25 · 查看答案与解析

R2; 2f+1 = 3; NEW-VIEW(v+1, V, O); R1 again. p = v mod n,1 mod 4 = 1,编号 1 的副本是 R2(L09 p.15)。R2 收齐自己、R3、R4 的 3 个 VIEW-CHANGE 后发 NEW-VIEW:V 是这 3 个 VIEW-CHANGE,O 是新视图要处理的 pre-prepare,已 prepared 的请求保留原序号(p.16)。4 mod 4 = 0,view 4 回到 R1。Lab 4 Case 6 实测:主节点依次 P1、P2、P3、P0,最后 view 4。

S26 · Lab 4 commit count

In the Lab 4 program, all nodes vote yes in the prepare phase. In the commit phase P1 and P2 type ack abort, and P3 sends ack to P0/P1/P2 commit. What does P0 count, and what happens to the transaction?

S26 · 查看答案与解析

2 of 4, below the threshold of 3, so the transaction aborts on every node. P0 数自己 1 票加 P3 的 commit,P1、P2 的 abort 不算(读代码)。Lab 4 Case 4 实测:P0、P1、P2 都是 2/4,P3 是 1/4,全部中止,余额不变。

S27 · Lab 4 crashed replica

P3 crashes before a deposit. P1 and P2 vote yes, then P2 and P3 type ack commit. What happens, and what changes if P1 acks instead of P3?

S27 · 查看答案与解析

It aborts; with P1’s ack it commits. 崩溃节点忽略收到的消息,P3 没收到 pre-prepare,敲 ack commit 只打印「No tx to ack」,P0、P1、P2 的 commit 只有 2/4(Lab 4 Case 5,实测)。改成 P1 ack,commit 达到 3/4,提交,alice 100(实测)。P3 recover 后从主节点拿回完整交易记录。课件 p.25 那一行写的是 P3。

S28 · Checkpoint rule

With f=1, when does a PBFT checkpoint at sequence 20 become stable, and which log entries may be discarded? How does the Lab 4 program differ?

S28 · 查看答案与解析

After 2f+1 = 3 matching CHECKPOINT messages; entries before 20 (≤ 20 in the paper). 每个副本各自收 3 个序号和摘要都相同的 CHECKPOINT 后把 20 号标为稳定,第 4 个节点落后或作恶不影响(L09 p.19)。Lab 4 程序只有主节点能发起,要等全部 4 个节点报告才写出最终文件,不比较摘要(读代码;4 个节点都在线的 Case 7 实测成功)。

S29 · Lab 1 voting timeout

In the Lab 1 program, P1 crashes before a transaction starts, and P2 and P3 do nothing. Describe what the coordinator prints over 60 seconds and the final outcome. Is aborting safe here?

S29 · 查看答案与解析

0/3 votes, abort; safe. 约 30 秒收到 P2、P3 的自动 NO,60 秒打印 P1 超时、按 NO 处理,Vote result: 0/3 agreement,进入 ABORT(Lab 1 p.33,实测)。协调者还没收齐 YES、没作决定,超时中止不会和任何已提交节点冲突,对应 L06 p.23 的“投票前崩溃当作 NO”。

S30 · Lab 1 ack abort

All three participants vote YES. P1 then types ack abort while P2 and P3 type ack commit. What does the program record, and why is this not a legal 2PC branch?

S30 · 查看答案与解析

The coordinator records COMMITTED (2/3 confirm), but P1 has no data. 实测:P2 的 data 有这笔交易,P1 的为空,账本不一致(Lab 1 p.23)。按 L06,决定在收齐 YES 时已经形成,参与者只能执行它并回 ack,不能在第二阶段改投;缺 ACK 应重发决定。

S31 · Lab 1 recovery

P1 recovers while the coordinator is still waiting for ACKs of an aborting transaction. Which records does P1 get, and why does this not demonstrate log-based recovery?

S31 · 查看答案与解析

Only finished transactions; the aborting one is missing. 实测 P1 只拿到已结束的两条历史,正在中止的那笔不在里面,协调者最后报 P1 ACK 超时才记为 ABORTED(Lab 1 p.34)。程序没有持久化,crash 只是内存标志位,恢复是向协调者要历史;L06 要求参与者重启后先读自己的日志。

下一页 →
Q04 2025 期末真题解析(一)|Q16–Q18:逻辑时钟、URB 与 CO-URB

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