2.1　广播

定义2.1（广播）　广播操作是由一个单一的节点（即源节点）发起的。源节点想要向系统中的所有其他节点发送一个消息。

定义2.2（距离、半径、直径）　无向图G中两个节点u和v之间的距离是u和v之间最小路径的跳数。节点u的半径是u和图中任何其他节点之间的最大距离。图的半径是图中任何节点的半径的最小值。图的直径是两个任意节点之间的最大距离。

备注：

●显然，图的半径R和直径D之间存在着密切的关系，即R≤D≤2R。

定义2.3（消息复杂度）　一个算法的消息复杂度是由交换的消息总数决定的。

定理2.4（广播下界）　广播的消息复杂度至少是n-1。源节点的半径是时间复杂度的下界。

证明：每个节点都必须收到消息。

备注：

●你可以使用预先计算好的生成树来做广播，其消息复杂度很高。如果生成树是一个广度优先搜索生成树（对于一个给定的源节点），那么时间复杂度也很高。

定义2.5（纯洁的）　如果一个图（网络）的节点不知道该图的拓扑结构，那么该图就是纯洁的。

定理2.6（纯洁广播下界）　对于一个纯洁的网络，边的数量m是广播消息复杂度的下界。

证明：如果你不尝试每条边，你可能会错过它背后的整个图部分。

定义2.7（异步分布式算法）　在异步模型中，算法是事件驱动的（一旦收到消息后……，做……）。节点不能访问一个全局时钟。从一个节点发送到另一个节点的消息将在有限但无限制的时间内到达。

备注：

●异步模型和同步模型（定义1.8）是分布式计算的基础模型。由于它们不一定反映现实，在同步和异步之间还有几种模型。然而，从理论的角度来看，同步和异步模型是最有趣的模型（因为其他每个模型都在这两个极端之间）。

●请注意，在异步模型中，采取较长路径的消息可能会提前到达。

定义2.8（异步时间复杂度）　对于异步算法（如定义2.7），时间复杂度是在最坏情况下（每个合法输入，每个执行场景）从执行开始到完成的时间单位数，假设每个消息的延迟最多为一个时间单位。

备注：

●你不能在算法设计中使用最大延迟。换句话说，即使没有这样的延迟上界值，算法也必须是正确的。

●纯洁广播下界（定理2.6）直接把我们带到了众所周知的洪泛（flooding）算法。

算法2.9　洪泛

1.源（根节点）发送消息给所有的邻节点

2.每个其他节点v接收信息的，第一次将消息传输给所有（其他）的邻节点

3.稍后再次收到消息（从别的边），节点可以丢弃这个消息

备注：

●如果节点v首先收到节点u的消息，那么节点v就称节点u为父节点。这种父子关系定义了一个生成树T。如果洪泛算法是在一个同步系统中执行的，那么T是一个广度优先搜索生成树（相对于根节点）。

●更有趣的是，在异步系统中，洪泛算法在R时间单位后终止，R是源节点的半径。然而，构建的生成树可能不是一个广度优先搜索生成树。