CS 168 · DISCUSSION 03 · GUIDED REASONING WORKBOOK
这组题不考 Bellman–Ford 算术，而是检查：每台 router 只能用当时已收到的邻居向量更新，本地“现实”因此可能落后于全局拓扑。
无需离开 CourseStack：先预测，再在表格、时间线或状态空间里完成推导；卡住时逐层打开提示，最后才展开解释与变式。
已阅读 Spring 2026 worksheet 与 official solution；以下是原创等价练习。官方 IDs 用于 coverage，对精确原题请回到页末 PDF。
对应官方 1.1、1.2、1.3、1.4、1.5、1.6、1.7、1.8
Why the official problem exists：复现官方连续 advertisements 的核心依赖：更新顺序决定中间状态，最短物理路径不会自动出现在 table。
Round 0 已完成直接邻接 bootstrap：C 知道 D=1，A 与 B 仍是 ∞。触发顺序固定为 C→B、B→A；每台 router 只看到已经送达的 advertisement。
先预测：C 尚未向 B 通告时，B 能立刻写 cost=3 吗？
| event 后 | A→D | B→D | C→D | 谁触发下一通告 |
|---|---|---|---|---|
| Round 0 | 1 via D | C | ||
| C→B | ____ | ____ | 1 | ____ |
| B→A | ____ | 3 via C | 1 | ____ |
| Converged | ____ | 3 via C | 1 via D | none |
只在收到 message 的 router 上计算 candidate。
更新式是 link-to-neighbor + neighbor-advertised distance。
C→B 时先算 c(B,C)=2 + D_C(D)=1。
初始 A=∞、B=∞、C=1。C→B 后：2+1=3，B 更新并触发广告。B→A 后：1+3=4，A 更新；最终 A=4 via B、B=3 via C、C=1 via D。任何尚未收到消息的 router 都保持旧 state。
D_x(d)=min_v[c(x,v)+D_v(d)] 中的 D_v(d) 是 x 已收到并保存的值，不是 v 此刻脑中的最新值。
DV 是 distributed asynchronous state machine；message arrival 才是允许 state 变化的 event。
当前 B→D=3 via C；C 把 D_C(D) 从 1 改为 8。问：B 能否因 candidate=10 比 3 差而忽略？先写 before/event/after。自检：必须更新为 10，因为旧 route 正依赖 C；否则留下 stale 3。
对应官方 2.1、2.2、2.3、2.4
Why the official problem exists：区分“不发”“说∞”和“真实失效”，并理解 policy 是 per outgoing neighbor 的。
B 到 A 的 next hop 是 A，metric=1。现在分别问 B 向 A、向 C 如何通告到 A 的距离。
先预测：Poison Reverse 下 B→A 的 advertisement？
| policy | B→A | B→C | 表达的含义 |
|---|---|---|---|
| Vanilla | ____ | ____ | 原 metric |
| Split Horizon | ____ | ____ | 抑制回告 |
| Poison Reverse | ____ | ____ | 对来源说∞ |
先标 next hop，再分别站在每个 outgoing neighbor 看。
policy 不改变 B 自己的 route，只改变输出。
向 A 是特殊方向；向 C 可正常说 1。
Vanilla：(1,1)；Split：(不发,1)；Poison：(∞,1)。Poisoning a route 是 B 真失去 A 后对所有相关邻居诚实说∞；poison reverse 是 B 仍能经 A 到达，却只对 A 说∞。
两种保护都切断“把从你学来的信息包装后再卖回给你”的两节点反馈边。
三节点环 A—B—C—A，destination 挂在 A 后失效；B 可从 C 听到旧值、C 可从 B 听到旧值。说明为何单个 next-hop 抑制不能消除所有多节点环。
对应官方 3.1、3.2、3.3、3.4、3.5、3.6
Why the official problem exists：让你看到错误不是一个瞬间，而是两个 router 交替把依赖彼此的旧结论当成新证据。
每边 cost=1。D 链路断前：R2 到 D=2 via R3，R1 到 D=3 via R2。断链后没有 split horizon，且 expiry/message 交错。
先预测：R2 route expiry 后收到 R1 仍通告 D=3，会怎样？
| time | R1 believes | R2 believes | wire evidence |
|---|---|---|---|
| t0 | D via R2,3 | D via R3,2 | converged |
| t1 link down | 3 | 旧 2，待 expiry | 无全局通知 |
| t2 R2 expires | 3 | ∞ | R1→R2 says 3 |
| t3 | 3 | via R1,4 | R2→R1 says 4 |
| t4 R1 expires/updates | via R2,5 | 4 | ____ |
每一步只使用 wire 上最新收到的数字。
被破坏的隐含假设是邻居 route 独立于我。
t2 candidate=1+3。
R2 接受 4，随后 R1 接受 5，下一轮 6、7……直到协议的有限 INFINITY 或另一机制打断。两者没有撒谎；它们缺少 path provenance，互相把旧 belief 重包装。
表格同时显示 local state 与 advertisement，因果环才可见。
把 expiry 顺序反转，让 R1 先过期。手推两轮；错误是否消失，还是只改变谁先被骗？
对应官方 3.7、3.8、3.9、3.10
Why the official problem exists：验证你学的是 information dependency，而不是“打开防环开关”。
仍用 R1—R2—R3—D。启用 split horizon。R1 的 D route via R2，所以 R1 不向 R2 通告 D。
先预测：R2 失去 D 后，能否从 R1 学回旧 route？
写出 R1↔R2 在 converged、link-down、R2 expiry 三个时刻对 D 的 advertisements；再画三节点环 X→Y→Z→X，标出每台 router 的 next hop。
Split horizon 只抑制向当前 next hop 的输出。
三节点中消息可以绕另一条边回来。
让 X via Y、Y via Z、Z via X。
在线形两节点依赖中，R1 不把 D 告诉 R2，所以 R2 无假替代，R1 的旧 route随后也过期。但在三节点依赖环中，每台都不是向自己的直接 next hop 收到回声，旧信息可绕一圈返回；split horizon 与 poison reverse 都不能保证任意拓扑无环。
保护范围由它删除的 dependency edge 决定；局部 policy 不能携带完整 path provenance。
把 advertisement 加上完整 path，收到含自身的 path 就拒绝；解释为何这从局部 heuristic 升级为显式 loop evidence。
当答案与物理最短路不同，先不要改算术；在图上给每条 advertisement 标时间，圈出该 router 的 Adjacent Knowledge。只有到达的 message 才能进入 Bellman–Ford candidate。
新图 P—1—Q—4—R—1—S，另有 Q—7—S。先按指定乱序通告推前三次 state；再断 R—S，分别用 vanilla、split horizon、poison reverse 追到稳定或出现环。