Dijkstra–Scholten 终止检测

形式陈述

Dijkstra–Scholten是面向单源扩散计算的终止检测算法。初始只有根r活动，其余节点被动；此后只有收到基本消息才能激活。基本消息可沿任意有向边传播，只要每条边都能反向送控制回执。无故障、恰好一次最终交付，不要求FIFO。

每个节点v维护out[v]，表示自己发送而尚未收到对应ACK的基本消息数。根始终留在检测树中，直到宣布完成；非根用parent[v]是否为空表示是否仍挂在树内。挂在树内不等于active：一个被动节点仍可能替下游工作保留责任。

text

发送基本消息m给w：
  out[v] += 1
  发送m

收到u发来的基本消息m：
  基本状态变为active
  if v不是根 且 parent[v]为空:
    parent[v] = u        // 暂扣m的ACK，作为本次挂树的父回执
  else:
    立即发送m的ACK给u    // 已经挂树，不再建立第二个父节点

收到一个ACK：
  out[v] -= 1

每次状态改变后检查：
  if 基本状态为passive 且 out[v] == 0:
    if v == r: Announce
    else if parent[v]非空:
      发送那条暂扣的父ACK
      parent[v] = 空

发送时增加out与消息入信道合为一个本地事件；接收、挂树和决定哪条ACK暂扣也按一个事件处理。ACK带足够身份避免误配或重复扣账。若传输层可能重复，则先去重再应用这些规则，不能把重复ACK当成新完成。

直觉

out不是“孩子数”。一条刚发出、尚未送达的消息已经记在out里；一条发给已在树内节点的消息也先记账，等即时ACK回来才结清。它是比实际孩子数更保守的未清责任数。

首次接收者暂扣一张回执，相当于告诉发送者：“我接住了任务，但我的这一支还没收尾。”只有自己被动、下游责任全清，才交还这张最后回执。这样，一个活动叶子或一条在途任务，都能通过尚未结清的责任一路牵住根。

这里动态维护的父树不同于网络拓扑。通信图可以有环、交叉边、重复发往同一节点的任务；一个节点每次挂树只保留一个父节点，离树后再次激活则可以换父。

动态父树与在途任务的未清回执 — r的两条父责任指向p与q，q又挂住s；p→q的交叉任务立即回ACK，不产生第二条父边。

例子与边界

交叉任务不能提前拆掉下游责任

取根r和工作者p、q、s，初始out均为0。固定如下执行，其中“父”指暂扣哪一条消息的ACK。

事件后	out[r]	out[p]	out[q]	父关系与未完工作
r发送m₁给p、m₂给q	2	0	0	两条基本消息在途
p、q接收	2	0	0	p父r，q父r
q发送m₃给s；p发送m₄给q	2	1	1	m₃、m₄在途
q接收m₄，即时ACK到p	2	0	1	q仍父r，不改为p
p被动，父ACK到r	1	0	1	p离树
r、q都被动，m₃尚未交付	1	0	1	全体被动，但不能宣布
s接收m₃	1	0	1	s活动，父q
s完成，父ACK到q	1	0	0	s离树；q可交还父ACK
q的父ACK到r	0	0	0	r被动，宣布完成

第六行是最重要的检查点。r看到自己被动，但out[r]=1；q虽然也被动，out[q]=1仍替在途m₃保留责任。不能把“本地没活”当成“可以脱离父节点”。

m₄的即时ACK也不表示q已经做完所有工作。它只表示这次到达没有建立新的父责任，因为q原有父r已经覆盖其后续活动。混淆这两种ACK含义，会错误地要求每个接收都建一条父边，甚至在通信环上制造等待环。

不变量怎样排除漏报工作

采用以下归纳不变量。

第一，out[v]始终是已发送基本消息中尚未收到ACK的数量，所以非负；在途基本消息必然有一笔未清账。ACK在途中时，发送者仍保留这笔账，宁可晚结清，不会提前漏掉。

第二，每个活动非根都在父树内；非根若还有未清下游账，也不能离树。新父边只把一个当前不在树中的节点接到已有树节点下，且离树要求out=0，此时它没有仍依赖自己的树孩子。因此父边不会成环，也不会把仍有活动的子树从根切断。

根被动且out=0时，不可能还存在树孩子，也不可能有根发出的在途任务。若其他节点活动或持有在途任务的发送责任，沿父链必到达根，强迫根保留至少一笔未清账，矛盾。于是Announce满足完整终止谓词。

完成后为什么回执会全部回来

基本计算终止后不会再创建新基本消息。即时ACK最终送达；留下的父责任构成有限树。被动叶子的out最终变0，可以交还父ACK；父节点依次成为叶子。归纳到根，根最终out=0并宣布。

一个节点允许先离树、后来被新的在途任务再次激活。该任务在发送者那里仍有out账，因此第一次离树不会使根过早宣布；重新到达时，接收者按新一轮挂树规则记录父节点即可。

推论与应用

若基本计算总共发送M条消息，每条最终恰好对应一条ACK，额外控制消息为M；发送、接收和结清各需O(1)本地记账操作。每个节点保存一个父身份和一个最多M的计数，需 $O(\log n+\log(M+1))$ 位，不计消息身份、基本任务与传输缓冲。

异步可靠性给最终完成，不给固定秒数。若基本计算确实已经终止，且为性能分析另外给单次传输/处理一个单位上界，剩余回执在树上逐层回收，检测延迟为O(n)；这不等于基本计算本身的运行时间。

本算法的单根前提有实质作用。若两个互不受同一父责任覆盖的节点都能自行启动工作，一个根的树消失并不能说明另一棵树也结束。可增加共同的虚拟启动者或选用支持分散初始活动的检测器，但必须明确建立新的覆盖不变量。

单元终点给出具体异步搜索及回执表，要求同时检查在途任务、即时ACK和暂扣父ACK，而不是只画最后那棵树。

参考资料

Edsger W. Dijkstra and Carel S. Scholten, “Termination Detection for Diffusing Computations”, Information Processing Letters 11(1), 1980, 1–4；EWD687a的deficit、cornet及engagement-tree证明
Wan Fokkink, Distributed Algorithms: An Intuitive Approach, MIT Press, 2013，§6.1：首次挂树与即时/延迟回执的计数实现

形式陈述 ​

交叉任务不能提前拆掉下游责任 ​

不变量怎样排除漏报工作 ​

完成后为什么回执会全部回来 ​

反向链接

形式陈述

交叉任务不能提前拆掉下游责任

不变量怎样排除漏报工作

完成后为什么回执会全部回来