本终点的主线是前三题：完成一批异步搜索，分别用回执、信用和令牌审查它的终止证据。后四题为网络协调和自稳定支线。所有任务均给定模型、输入和事件顺序；答案中的“完成”分别指基本计算终止、模拟轮结束、恢复合法服务，不能相互替换。
第一题：交叉任务与再次挂树
采用Dijkstra–Scholten的单根、可靠恰好一次、无故障模型。节点为r、p、q，初始仅r活动。基本程序只有以下四种任务，不再产生其他工作：
- r启动时发送a=p₀给p、b=q₀给q，然后被动
- p处理p₀时发送c=q₁给q，然后被动
- q处理q₀时不发消息，直接被动
- q处理q₁时发送d=p₁给p，然后被动
- p处理p₁时不发消息，直接被动
控制层与基本发送/接收按正文原子规则执行。固定交付顺序：先交付b，q完成并发出ACK(b)，立即把它交给r；再交付a，p发c后被动；暂停交付c，观察全网。随后交付c，q发d后被动；交付d，p完成；最后依次交付ACK(d)、ACK(c)、ACK(a)。
问题：逐步填写out向量、父关系及在途基本消息。p收到d时应暂扣回执并把父改成q吗？根何时能宣布？
解答
下表out按(r,p,q)排列，“—”表示非根不在树中。
| 事件后 | out | parent[p],parent[q] | 在途基本消息 | 关键控制动作 |
|---|---|---|---|---|
| r发a、b并被动 | (2,0,0) | —, — | a,b | 暂无ACK |
| q收b后完成 | (2,0,0) | —, — | a | 发ACK(b)，q离树 |
| r收ACK(b) | (1,0,0) | —, — | a | b责任结清 |
| p收a，发c并被动 | (1,1,0) | r, — | c | 暂扣ACK(a) |
| 暂停c | (1,1,0) | r, — | c | 全体被动，不能宣布 |
| q收c，发d并被动 | (1,1,1) | r, p | d | q再次挂树，父改为p |
| p收d后完成 | (1,1,1) | r, p | 空 | p仍在树内，即时发ACK(d) |
| q收ACK(d) | (1,1,0) | r, — | 空 | q发ACK(c)，离树 |
| p收ACK(c) | (1,0,0) | —, — | 空 | p发ACK(a)，离树 |
| r收ACK(a) | (0,0,0) | —, — | 空 | r被动，Announce |
p收到d时虽然原本被动，却仍挂在r下，因为out[p]=1。判定是否新建父边看parent是否为空，不能只看active/passive。若把p的父改成q，便制造p↔q父环，还丢掉r下的原责任。
一共4条基本消息和4条ACK。ACK(d)是即时回执，其余三条分别在对应挂树区间结束时归还。第七行基本计算已终止，控制回执仍可继续；安全检测允许这一延迟。
验收：能在第五行指出c而拒绝宣布；能解释q换父而p不换父；每一笔out递减都对应确实交付的一条ACK。
第二题：把同一批搜索改成信用账本
独立重置第一题的基本程序和交付顺序，改用信用分配。根初始1，给a附1/2、给b附1/4，自己留1/4。p处理p₀时把收到的1/2平分，c带1/4；q处理q₁时把1/4平分，d带1/8。每次非根被动便归还其全部剩余信用。
先让q处理b后归还的1/4到r。其余RETURN暂缓交付，基本消息仍按a、c、d的顺序到达。问题：c被扣在途中时，四类信用分别在哪？所有基本消息结束后，r还需收哪些RETURN？
解答
q处理b所产生的RETURN到达后，r持1/2。p处理a，把1/4放入c，剩余1/4放入自己的RETURN，随后信用归零。因此扣住c时：
- 节点信用：r为1/2，p、q均0
- 在途基本信用：c带1/4
- 在途归还信用：p第一次RETURN带1/4
- 总量为1，全体基本状态被动仍不代表终止
q收到c后，发d带1/8，并归还余下1/8；p收到d完成后再归还1/8。因此基本消息结束时，r仍持1/2，三条RETURN分别为1/4、1/8、1/8，总计1/2。任意顺序交付它们，根最终得到1且仍被动，才宣布。
p的两次RETURN属于两个不同活动区间，不能以发送者相同为理由合并去重；也不能让p第二次收到d时撤回第一条RETURN。每份信用只在节点与消息之间转移，总量不变即可。
验收：守恒式包含RETURN，不把在途归还当成遗失；分数精确，任何活动者及在途基本消息都有正信用。
第三题：Safra为什么不能删掉颜色
独立三节点环A→B→C→A，累计计数全0，初始仅C活动。采用Safra的累计计数、不清本地c版本。
A发白令牌，B被动转发后，C发m给B；B收m后发n给C并继续工作；C收n后被动，转发令牌回A。要求计算本轮采样和，并找出令牌颜色来自哪一步。随后B不再发送消息，最终被动，说明还需要哪些巡回。
解答
B被采样时c[B]=0。之后C发m使c[C]=1，B收m使c[B]=−1；B发n又使c[B]=0，C收n使c[C]=0。C被采样时贡献0，A也贡献0，所以本轮s=0。
然而B仍活动。m被计入发送而未计入接收，n被计入接收而未计入发送，两笔错误方向恰抵消。C收到n时染黑，故本轮令牌黑，A拒绝宣布。
第二轮令牌到B时须等B被动。B之前收到m留下的黑色尚未转交，第二轮仍黑；第三轮无新基本消息且全白，计数和0，才宣布。若B一直不被动，令牌就停在那里，检测器没有义务制造一份假的完成结果。
验收：写出“零和但B活动”的具体配置；说明累计计数没有在转发时清零；黑色清除与新令牌归零是不同字段的操作。
第四题：回声与逻辑轮不是同一份证明
网络节点A、B、C、D，边为AB、AC、BC、BD、CD。A启动回声波，首次接触顺序固定为A发现B、A发现C、B发现D。问父树、总消息数、根完成时是否保证此树是BFS树。
再换网络为路径A–B–C–D加边A–C，用α同步器模拟一轮。基本消息只有A→B的a与C→B的c，c迟到。问B收到a以及A的SAFE之后能否进入下一轮；计算本轮基本ACK与SAFE条数。β支线采用树A–B–C–D，另计UP与GO。
解答
回声父树为A→B、A→C、B→D，共3条树边。树边各一条发现与回声，另外BC、CD两条非树边各发双向WAVE，共2×5=10条。根完成证明本轮覆盖和端口结清；所给这一次树碰巧是BFS树，但异步算法一般不能保证首达路径最短。
同步器中，B还缺C的SAFE，不能关闭第r轮收件箱。c到B后须先被缓存并立即ACK，C收ACK后才发SAFE；之后B才能用{a,c}更新。基本ACK共2条，4条无向边上的SAFE共8条。
β既定树有3条边，UP和GO各3条，共6条；基本ACK仍为2条。树高3进入延迟分析，建树开销另算。这些消息确认一轮收件箱，不等于业务计算从此终止。
第五题：损坏令牌环恢复了什么
采用Dijkstra环，n=K=4、中央非空选择daemon。初始(x₀,x₁,x₂,x₃)=(2,0,3,1)，按节点3、2、3、1、2、3执行。要求列出每步配置与特权集合，找首次合法时刻。根之后是否应该停止？
解答
| 执行节点 | 配置 | 特权集合 |
|---|---|---|
| 初始 | (2,0,3,1) | |
| 3 | (2,0,3,3) | |
| 2 | (2,0,0,3) | |
| 3 | (2,0,0,0) | |
| 1 | (2,2,0,0) | |
| 2 | (2,2,2,0) | |
| 3 | (2,2,2,2) |
第三次更新已合法。初始普通节点中没有颜色2，根又一直为2，它向后传播并排除旧边界；全相同并不是合法的必要条件。
最后根仍使能，应把自己改为3，令牌再传给节点1。自稳定恢复的是合法服务的闭包，不是全网停止。恢复前存在多个特权，不能把恢复后的互斥保证提前套到整个损坏前缀。
第六题：距离正确还需检查父指针
采用静默自稳定BFS，根r，边ra、ab、bc、ca、cd，N=5，端口序r<a<b<c<d。给定距离(0,1,2,2,3)，父指针(⊥,r,a,b,c)。问它是不是合法静默状态，最少还需哪一个更新？若把网络改为五节点路径、错误设置N=2，会有什么固定点？
解答
距离全部正确，但c的父b也为距离2，缺少下降1。c的邻居a距离1，是唯一最小者，因此修复为parent[c]=a，距离仍为2。之后每个目标对都与当前对相等，guard全假，达到静默。
在r–a–b–c–d路径上错误用N=2，(0,1,2,∞,∞)可成为固定点，父向量为(⊥,r,a,⊥,⊥)。这说明N上界不是仅影响性能：若它截掉真实距离，连通性也不能保证输出完整BFS树。
第七题：随机稳定与确定最坏时间
采用Herman的非令牌保持位版本。五节点从00000开始，第一轮只让0翻位，第二轮只让当前持令牌的2翻位；其余节点保持。计算两轮令牌集合与这条路径概率。再从三节点000开始求稳定时间期望，并判断是否存在有限最坏轮数。
解答
五节点依次为00000、10000、10100，令牌集合为{0,1,2,3,4}、{2,3,4}、{4}。第一轮5次指定硬币、第二轮3次，路径概率2⁻⁸。
三节点000、111是仅有的三令牌状态，每轮八个新比特配置等概率，其中六个合法。因此T满足P(T>t)=4⁻ᵗ，期望4/3轮，没有有限最坏轮数。永不恢复的硬币序列确实存在，但总概率0。
验收：所有更新读取旧配置；独立硬币不能替换为全环共享一枚；单令牌状态仍继续随机行走，概率一稳定没有被误写成算法最终停止。
最终验收
- 能用一张完整账表同时标记节点活动、在途基本消息及检测控制消息
- 能区分即时ACK、父ACK和RETURN分别消除哪一份责任
- 能给出零计数误报的具体执行，并说明颜色怎样阻止它
- 能区分广播已覆盖、逻辑轮已完成、基本计算已终止、服务已恢复四种结论
- 能分别陈述合法集闭包、所有给定调度下收敛、概率一收敛及各自成本单位