← COMP5567 全部讲次
Q02

Lab Test 英文自测|S11-S22:3PC、BFT、VR、Paxos

非官方自拟练习:3PC 实验、拜占庭容错与 PBFT 阈值、VR 实验、Paxos 两阶段,题干英文、解析中文附页码。

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

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

范围与作答约定

本页 S11–S22 接着英文自测 1 编号,覆盖 3PC 实验(Lab 2)、L06 的 3PC、L07 的 BFT、L08 的 VR 与 Paxos、VR 实验(Lab 3)。PBFT 的完整题目在英文自测 3。涉及 Lab 程序输出的题,解析里标明实测、读代码或未实测;页码均为 PDF 页序。

作答时先写故障模型(crash / Byzantine)和网络假设,再写理论答案;Lab 程序和讲义不一致时两边都写,并说明以哪一边作答。

复习资料 · 英文自测 1 · 英文自测 2

题目与解析

S11 · 3PC PreCommit

In the lecture version of 3PC, what does a participant send after receiving PreCommit? How does the Lab 2 program handle the same step differently?

S11 · 查看答案与解析

An ACK; the program turns it into a second yes/no vote. L06 p.30:PreCommit 在全体 Yes 之后发出,参与者只回 ACK,不再表态。Lab 2 程序里参与者敲 precommit vote yes 或 no,超时也按 no 计(Lab 2 p.11、p.21,实测)。考试按 L06 写消息序列。

S12 · 3PC coordinator recovery

The coordinator crashes after every participant has acknowledged PreCommit (all are PREPARED). After recovery, should the transaction commit or abort? What if no participant had received PreCommit?

S12 · 查看答案与解析

Commit; abort. 全体 Prepared 说明所有人都投过 Yes 且知道结果是提交,恢复后可以提交(L06 p.33 情形 ②、p.37、p.40);没人收到 PreCommit 时没人 Prepared,abort 不会和已提交节点冲突(p.33 情形 ③、p.35)。Lab 2 练习 3 与 Case IV 分别实测到这两种结果(p.25、p.22)。

S13 · 3PC versus 2PC

Why does 3PC block less than 2PC, and under what network condition can 3PC still end with some participants committed and others aborted?

S13 · 查看答案与解析

Timeouts plus the PreCommit state let a recovery coordinator infer the outcome; a network partition breaks this. 2PC 中投了 Yes 的参与者收不到决定只能等(L06 p.23)。3PC 多出 Prepared 这一状态,恢复协调者按参与者状态就能推出结果(p.32–33)。这依赖同步网络、无分区等前提;分区时两边各自推断,可能一边提交、一边中止(p.34)。Lab 2 程序演示不了分区。

S14 · OM and SM bounds

With oral messages, can 6 generals tolerate 2 traitors? With signed messages, what is the bound? What network assumption do both algorithms make?

S14 · 查看答案与解析

No; n ≥ m+1; synchronous network. 口头消息要 n ≥ 3m+1,m=2 时需要 7 人,6 人不够(L07 p.11–13)。签名消息只要 n ≥ m+1(p.20–24)。两者都假设同步网络(p.24)。

S15 · PBFT thresholds

PBFT runs on n=7 replicas. What is f? How many matching prepare messages make a replica prepared, how many matching commits are needed before execution, and how many matching replies does the client wait for?

S15 · 查看答案与解析

f=2; 5 matching prepares; 5 matching commits; 3 matching replies. n=3f+1=7 得 f=2;2f+1=5,f+1=3(L09 p.13 给出 f=1 的 3、3、2,通式相同)。L09 让主节点也发 PREPARE,所以写 5 个匹配 prepare;按原论文写成 pre-prepare 加 4 个 prepare 也对,两种写法都是 5 票。

S16 · VR quorum and Lab 3 votes

A VR group has 5 replicas. How many crash failures can it tolerate, and how many confirmations, counting the primary, are needed to commit? In the Lab 3 program, node1 and node3 vote no while node2 and node4 vote yes. Is the operation committed, and do node1 and node3 apply it?

S16 · 查看答案与解析

f=2, 3 confirmations; committed, and both apply it. 2f+1=5 得 f=2,f+1=3 含主节点(L08 p.7)。程序里主节点加 node2、node4 共 3 个 yes 即提交,投 no 的 node1、node3 也执行了 COMMIT(Lab 3 p.20,实测)。L08 里备份只回 prepareok,没有 no 这一选项(p.14)。

S17 · VR view change

Three replicas report logs ending at op 9, op 10 and op 8 during a view change. Following L08, what is k? In the Lab 3 program, node0 (primary of view 0) crashes and node2 issues start-view-change. Which node becomes the new primary?

S17 · 查看答案与解析

k = op 9; node1. 至少到 op 9 的副本有两个,构成多数(L08 p.13)。程序的新主节点是新视图号 % 5,新视图号为 1,所以是 node1,发起者 node2 仍是备份(Lab 3 p.3,变式实测)。L08 没讲新主节点的选法。程序选新日志时取最长一份,按此推它会用到 op 10 的日志,这一点只来自读代码,未实测。

S18 · VR recovery

A recovering replica receives its first recovery response from a replica that is behind. Under L08, may it rebuild its log from that single response? What did the Lab 3 program do?

S18 · 查看答案与解析

No; the program used the first response. L08 p.16 要等 f+1 个回应,只问一个可能问到落后副本。Lab 3 程序采用第一个到达的回应,其余只打印不处理(p.25、p.27,实测;两次分别用了 node1 和 node2 的回应)。第一个回应来自落后节点会怎样,未实测。

S19 · VR versus 3PC

Both VR and 3PC count replies from other nodes. State the different problem each protocol solves, and explain why a minority “no” cannot stop a VR operation.

S19 · 查看答案与解析

VR orders operations on replicas; 3PC makes one transaction atomic. L08 p.20:VR 让副本按同一顺序执行同一串操作,3PC 让一次事务全体提交或全体中止。VR 主节点拿到 f+1 个确认就执行,任意两组 f+1 必相交(p.19),少数派副本只能跟随;3PC 任一 No 都会中止。

S20 · Paxos accept rule

An acceptor has replied promise(5). It then receives accept(3,v) and later accept(6,v2). How does it respond to each?

S20 · 查看答案与解析

Reject accept(3,v); accept accept(6,v2). 3<5,A 已承诺不接受更小编号;6>5,A 没向更大编号承诺过,即使没见过 prepare(6) 也接受(L08 p.25 第 4 条、p.32)。

S21 · Paxos value choice

Proposer A sends prepare(2) and receives promises from B and C, both reporting an accepted proposal (1,99). A wanted to propose 42. What does A send in Phase 2, and why?

S21 · 查看答案与解析

accept(2,99). promise 附带的编号最大的提案是 (1,99),A 必须沿用 99(L08 p.25 第 3 条、p.30–31)。99 已被多数接受,任何更大编号的提案在 Phase 1 都会碰到接受过它的 acceptor。

S22 · Paxos livelock

Two proposers keep issuing higher prepare numbers, and neither collects a majority of accepts. Is safety violated? Name two remedies.

S22 · 查看答案与解析

No; elect a single leader, or add exponential back-off between prepares. 活锁时一直没有值被选定,自然不会选出两个值,受损的是可用性(L08 p.22、p.33)。

下一页 →
Q03 Lab Test 英文自测|S23-S31:PBFT、Lab 4 与 Lab 1

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