2.2　融合广播

融合广播与广播相同，只是相反：不是由根向所有其他节点发送信息，而是由所有其他节点向根节点发送信息（从叶子开始，即树T是已知的）。最简单的融合广播算法是回传（echo）算法。

算法2.10　回传

1.一个叶子传送消息给它的父节点

2.如果一个内节点已经从每个孩子那里接收到了所有的消息，那么它发送一个消息给它的父节点

备注：

●通常情况下，回传算法与洪泛算法配对，用来让叶子知道它们应该开始回传过程，这被称为洪泛/回传（flooding/echo）。

●例如，人们可以使用融合广播进行终止检测。如果一个根节点想知道系统中的所有节点是否已经完成了某些任务，它就会发起一个洪泛/回传；然后回传算法中的消息意味着这个子树已经完成了任务。

●回传算法的消息复杂度是n-1，但与洪泛一起是O（m），其中m=|E|是图中边的数量。

●回传算法的时间复杂度由洪泛算法生成的生成树的深度（即树内根的半径）决定。

●洪泛/回传算法可以做的事情远不止从子树上收集确认信息。例如，我们可以用它来计算系统中的节点数、最大的ID，或系统中存储的所有值的总和或路由不相交匹配。

●此外，通过组合结果，人们可以计算出更多更复杂的聚合，例如，用节点数和总和可以计算出均值。有了均值，就可以计算出标准差。以此类推。