回声波算法

根先把波向外推。第一次接触确定“我沿谁的消息被发现”；最后一次回应再沿这条父边回去。一个节点在父边上交卷以前，必须已经从每个其他端口收到WAVE。

环不会造成所有节点互等，因为非父边两端在各自被发现时就会主动发送WAVE，不等待对方先完成。真正需要逐层等待的是父子依赖，而父边按首次发现时间指向更早节点，不可能形成环。

这个协议可用来完成一轮广播或汇聚，但它本身不是任意基本计算的终止检测器公理库分布式终止检测Distributed termination detection用活动状态与在途基本消息共同定义终止，将不误报、最终检测与外部任务边界分别说明。。一个业务节点若在回声之后还能生成新任务，根收到回声并不能证明这些后续工作也结束。

菱形加横边的一轮完整执行 ​

取四节点A、B、C、D，边集为AB、AC、BC、BD、CD，A为根。图中m=5、n=4。固定下列到达顺序：

1. A发送A→B、A→C。
2. B收到A的WAVE，选A为父，发送B→C、B→D。
3. C收到A的WAVE，选A为父，发送C→B、C→D。
4. D先收到B的WAVE，选B为父，发送D→C。
5. C收到B、D的WAVE。它已从A、B、D全部邻居收到消息，发送C→A。
6. D收到C的WAVE。它的两个端口B、C都已收到，发送D→B。
7. B收到C、D的WAVE，加上最早的A，端口全部结清，发送B→A。
8. A收到C和B的回声，完成。

发送总数为2+2+2+1+1+1+1=10，恰等于2m。C和D之间的两条消息不表示双方互为父子：D的父节点始终是B。父边负责汇聚依赖，所有边上的Received负责证明没有遗漏端口。

为什么完成一定覆盖全网 ​

首次被发现的非根v把父指针指向此前已被发现的u；沿父指针，发现事件严格变早。因此所有已发现节点构成以r为根的树，不会出现父指针环。

若根最终完成，却仍有未发现节点，利用连通性公理库图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。，必有一条边连接已发现区域与未发现区域。已发现端在发现时会沿这条非父边发送WAVE，且不收到另一端的WAVE就不能完成。这个未结清条件沿父链一直阻止根完成，与假设矛盾。

进一步，根完成前每个子树都已经回声。一个非根发出父回声时，所有端口都已收到消息；归纳到根可知所有WAVE都已经交付。若要汇聚节点值，可让父回声携带本子树结果，非树边WAVE只作端口结清，不能把同一节点经横边重复计入。

为什么最终会完成 ​

可靠交付首先保证波沿路径访问所有节点。访问完成后，父树的叶子从所有非父邻居收到WAVE，就能回复父节点；去掉已完成叶子，再对上一层重复，最终根收齐。证明依赖树的有限性与每条已发消息最终交付，不依赖超时。

异步首达树未必是BFS树。若A→C很慢，而A→B→C很快，C会选择B，即使A与C直接相邻。回声证明覆盖与完成，不把先到达自动解释为最少跳数。

每条树边传一条发现WAVE和一条回声；每条非树边传两个方向的WAVE。因此控制消息恰为2m，节点v的Received需 $O(\mathrm{deg}(v))$ 个标记，整网为O(m)；父端口另占常数个本地字段。

纯异步模型没有墙钟完成上界。若只为性能分析另外约定每次消息传输和处理至多一个时间单位，洪泛与树上汇聚各经过至多n−1层，可得O(n)时间；树可能很深，不能直接把它写成O(D)的BFS界。

回声还可建立孩子集合、汇聚计数或确认一次配置发布。网络同步器公理库异步网络同步器Network synchronizer · Alpha synchronizer · Beta synchronizer用基本消息ACK与轮安全通知模拟同步轮，比较逐邻居α和树汇聚β的通信、延迟与缓冲条件。的全网安全确认也能采用树上汇聚，但必须先证明它汇聚的“安全”标记对应当前轮全部基本消息已到达。