CS 168 · DISCUSSION 12 · GUIDED REASONING WORKBOOK
每道题先确定树是 per-source 还是 shared、join 往哪里走、packet 在哪里复制；AllReduce 则同时追 logical steps 与 underlay link load。
无需离开 CourseStack：先预测，再在表格、时间线或状态空间里完成推导；卡住时逐层打开提示，最后才展开解释与变式。
已阅读 Spring 2026 worksheet 与 official solution；以下是原创等价练习。官方 IDs 用于 coverage，对精确原题请回到页末 PDF。
对应官方 1.1、1.2、1.3、1.4、1.5、1.6、1.7
Why the official problem exists：用 state key、tree root、router support、stretch 与 collective composition 逐项判断，而不是凭术语熟悉度。
比较 DVMRP per-(source,group) tree、CBT shared core tree、application overlay，以及 Reduce→Broadcast 组成的 AllReduce。
先预测：哪种方案通常需要 per-(source,group) forwarding state？
| ID | 先写判断依据 | T/F |
|---|---|---|
| 1.1 | 跨 AS coordination/billing/scaling | ____ |
| 1.2 | DVMRP table key | ____ |
| 1.3 | core tree 是否保证 source shortest | ____ |
| 1.4 | overlay state 在 router 还是 endpoint | ____ |
| 1.5 | ring 能否实现 AllReduce | ____ |
| 1.6 | stretch=overlay/underlay | ____ |
| 1.7 | Reduce + Broadcast | ____ |
先问 state 保存在哪、tree 由谁拥有。
shared tree 减少 state，但可能增加绕路。
依次得到 F,T,F,F,T,T,F。
1.1 F：跨域部署罕见；1.2 T：DVMRP 是 source-specific；1.3 F：core 位置可导致绕路；1.4 F：overlay 用普通 unicast router；1.5 T：ring 是常见实现；1.6 T：越接近 1 越贴近 underlay shortest path；1.7 F：AllReduce 可由 Reduce 后接 Broadcast。
每个答案都能还原为 state placement、path ownership 或 operation dependency。
sender 数从 1 增到 100、group 不变：DVMRP 与 CBT 的 router state 分别按哪个维度增长？
对应官方 2.1、2.2
Why the official problem exists：单独推 source-specific tree 的 RPF 路径与 prune branches。
A、B、C 是 G1 members；D 是 sender。所有数为 link cost。
先预测：D 到 B 的 source-shortest branch？
从 D 构造 shortest-path tree，标 RPF parent；prune 无 member 的 branches。再让 E 加入 G1，重画 D→B branch 并说明它是否改变。
tree root 是 source D，不是某个 core。
membership 只决定哪些 downstream branches 被 prune。
E 的 join 新增通向 R3 的 branch，不重写 D→B 的 shortest path。
D→B 始终是 D–R4–B。E 加入后新增 D–R4–R3–E branch，但 B 所在 branch 的 RPF parent 与 link costs 都没变，因此 D→B 不变。
DVMRP 先由 unicast shortest paths确定 source tree，再用 membership pruning 缩枝。
若 R4–B cost 从 1 增到 9，哪条替代 path 才会改变 D→B？
对应官方 2.3、2.4、2.5、2.6、2.7
Why the official problem exists：逐条追 join 在已有 tree node 停止，以及 sender 经 core 注入后的复制。
初始无 member；边 cost 相同。顺序：C join、B join、A join。
先预测：B join 到达已在树上的 R2 前，经过哪个已有 tree node 可停止？
| event | join/data path | new tree edges |
|---|---|---|
| 2.3 C joins | C→R2 | ____ |
| 2.4 B joins | B→R4→R2 | ____ |
| 2.5 A joins | A→R1→R2 | ____ |
| 2.6 B sends | B→R4→R2, then fan out | 列到 A/C 的 branches |
| 2.7 core=R3 | 重新建树 | 哪段 path 改变？ |
join 朝 core 单播。
遇到已有 tree node 后，通往 core 的 suffix 已存在。
data 先进入 core/shared tree，再沿 member branches 复制。
tree 依次加入 C–R2、B–R4–R2、A–R1–R2。B 的 data 到 R2 后分别走 R2–C 与 R2–R1–A。core 改到 R3 时所有 join 的 shared suffix 和 data detour 都要按到 R3 的 unicast path 重算。
CBT 用 per-group shared state 换取可能依赖 core 位置的 path stretch。
先 A join 再 B join，哪些消息更早停止，最终 edge set 是否相同？
对应官方 3.1、3.2、3.3、3.4、3.5、3.6、3.7、3.8、3.9
Why the official problem exists：把九个连续小问保留为一张 event ledger，而不是压成一个定义。
初始 G1={A,E}；随后 C join。之后 G2={A,B,D}。DVMRP 已在每个指定阶段收敛并完成 prune。
先预测：C 完成 host-to-router join 后，立即知道变化的是谁？
| ID/event | 必须写出的 evidence | 你的结果 |
|---|---|---|
| 3.1 A→G1 | 到 E 的 source-tree links | ____ |
| 3.2 C joins | 立即知情 router | ____ |
| 3.3 E→G1 | 到 A/C 的 pruned tree | ____ |
| 3.4–3.6 B sends | 非 member 可否发送；到 E path；max arrival | ____ |
| 3.7 R2 table | (source,group), RPF parent, children | ____ |
| 3.8–3.9 four sends | 逐条求最慢与最快 arrival | ____ |
membership discovery 与 multicast routing 是两层。
每个 source/group 独立决定 RPF parent 与 pruned children。
到达时间沿实际 tree path 累加，最后比较四组事件。
3.1 A 的 G1 branch 走 A–R1–R3–E。3.2 只有 R2 立即知道 C join。3.3 E 发包时分别沿 R3–R1–A 与 R3–R4–R2–C。3.4 非 member B 仍可发送；3.5 到 E 走 B–R4–R3–E；3.6 最晚 member 是 A，耗时 5。3.7 必须为每个 (source,G1/G2) 单独列 RPF/children，未经过 R2 的 tree 不应伪造 row。3.8–3.9 对四次发送分别累加后再取 max/min，不能比较 hop count 代替 cost。
同一 group 不同 source 的 tree 是不同 state；同一 source 不同 group 的 prune children 也不同。
让 R3–R4 link down；列哪些 (source,group) entries 必须重算，哪些 local membership 不变。
对应官方 3.10、3.11、3.12、3.13、3.14、3.15
Why the official problem exists：在同一 shared tree 上分别推 control message、data injection 与 partition。
仍用上一拓扑，G1 初始为空，core=R1。C 先沿 C–R2–R1 join；D 随后沿 D–R4–R2 join，并在 R2 遇到已有 tree。
先预测：D 的 join 为什么不必从 R2 继续到 R1？
| ID | derive | answer |
|---|---|---|
| 3.10 | C join forwarders | ____ |
| 3.11 | D join 停点 | ____ |
| 3.12 | B→core→最远 member | ____ |
| 3.13 | C→core→最远 member | ____ |
| 3.14 | A–R1 down 后谁还能 inject | ____ |
| 3.15 | remaining members reachable | ____ |
sender 不必是 member，但必须能到 shared tree/core。
data delay 包括 sender 到 core，再从 core 到最远 member。
failure 后在树上删边，检查 connected components。
C join 由 R2、R1 forward/install；D join 到 R2 即可停止。B 和 C 发送时都先找到 shared tree/core，再沿 R1–R2 分支到 C/D，逐边累加决定最远到达。A–R1 断开只隔离 A；B、C、D、E 仍可向可达 tree 注入，G1 的 C、D 仍可接收。
shared tree 的 reachability 是一张真实 state graph；删一条边后的答案来自 connected component，不来自成员名册。
改断 R1–R2；画出 tree 的两个 components，分别列可发送者与可接收 members。
对应官方 4.1、4.2、4.3、4.4、4.5
Why the official problem exists：逐步覆盖零成本同机边、overlay cost、每节点 bytes、critical path 与物理 link load。
每节点有 4-Gbit vector；full mesh 中每节点向其余三节点发送完整 vector。带宽无限，只比较 travel time。
先预测：同侧 Node1↔Node2 cost=0 的合理解释？
| ID | compute | result |
|---|---|---|
| 4.1 | 0-cost model | ____ |
| 4.2 | 六条 undirected virtual edges 及 cost | ____ |
| 4.3 | 每节点/总发送量 | ____ |
| 4.4 | 最长 overlay edge | ____ seconds |
| 4.5 | 逐 virtual message 展开到 L–X–R | ____ Gbit |
同侧 cost=0，跨侧 cost=4。
每节点发 3×4Gbit。
跨侧有 2×2×2 directions 个 4-Gbit messages。
virtual costs：1–2 与 3–4 为 0，其余四对为 4。每节点 12Gbit，总计 48Gbit；critical travel time=4s。四个跨侧 unordered pairs、两个方向，各 4Gbit，所以中央 L–X 与 X–R 各承载 32Gbit。
overlay 边只是 underlay path 的别名；load 必须把每条 logical message 展开后相加。
Node4 vector 变 8Gbit，哪些 directed messages 与物理 link load 改变？
对应官方 4.6、4.7、4.8
Why the official problem exists：不靠 2(n−1) 公式跳过实际 logical edge 和 underlay mapping。
同一 underlay，ring 顺序 1→2→3→4→1；忽略分块优化，每次传完整 4-Gbit vector，从 4 开始，先 reduce 再 distribute。
先预测：一共经过多少个 sequential logical hops？
| step | logical edge | cost | underlay links/load |
|---|---|---|---|
| reduce 1 | 4→1 | ____ | ____ |
| reduce 2 | 1→2 | ____ | ____ |
| reduce 3 | 2→3 | ____ | ____ |
| broadcast 1–3 | 3→4→1→2 | ____ | ____ |
按 4→1→2→3 完成 reduce。
再 3→4→1→2 分发结果。
cost sequence 是 4,0,4,0,4,0。
六步 cost=4+0+4+0+4+0=12s。每步的 4-Gbit message 若跨左右 cut 就同时经过 L–X 与 X–R；把三次跨侧 step 相加，两条 central links 各承载 12Gbit。零成本 edge 仍有 logical data，但不占 central underlay。
ring 降低 fan-out，却把性能变成 node ordering 与 sequential critical path 的函数。
使用真正分块的 ring AllReduce 时，每步只发 1Gbit；latency step 数不变时，带宽模型怎样变化？
对应官方 4.9、4.10、4.11
Why the official problem exists：验证 overlay label 不是装饰：它决定连续 neighbors 是同机还是跨 cut。
保持物理位置不变，把 ring 改成 1→3→2→4→1。四条 logical edges 现在全部跨左右 cut，仍从 4 开始执行六步。
先预测：相较原 ring，新的 sequential latency？
4.9 画四条新 virtual edges并标 cost；4.10 写六步 edge/cost 序列并求总时长；4.11 将每步 4Gbit 展开，累计 central-link load。
新 ring 每个 neighbor pair 都左右跨侧。
六个 sequential hops 各 cost=4。
每步都穿过两条 central links。
virtual edges 1–3、3–2、2–4、4–1 均 cost=4。六步总 latency=24s；六枚 4-Gbit logical transfers 都穿 central cut，因此 L–X 与 X–R 各承载 24Gbit。只改编号就把原来的 12s/12Gbit 热点翻倍。
collective optimizer 必须感知 topology；抽象 ring 相同不代表映射成本相同。
在四节点两机布局中，枚举一个让跨侧 edges 最少的 ring ordering，并证明下界。
给 5 个节点、两层 underlay，自选两个 multicast groups 与两个 sources，闭卷画 DVMRP/CBT state；再选两个 ring orderings，逐步计算 latency 与每条 underlay link 的 bytes。