4.1.2 简单的洪泛算法

我们给出一个简单算法用于让领导者和非领导者识别自己。算法要求进程都知道直径diam。算法中最大的UID在整个网络中像水流一样传播，所以我们称它为洪泛最大值（FloodMax）算法。

洪泛最大值算法（非形式化）：

每个进程都保持有一个最大UID的记录（最初是自己的UID）。在每轮中，每个进程都要在自己的所有出向边上传播最大的UID。在diam轮后，如果得到的最大值是进程自己的UID，那么进程就把自己选为领导者，否则就为非领导者。

进程i的代码如下。

洪泛最大值算法（形式化）：

消息字母表是UID的集合。

容易看出，洪泛最大值算法选出具有最大UID的进程。更确切地讲，我们定义i_max为具有最大UID的进程的索引，u_max为那个最大的UID。我们有如下定理：

定理4.1 在洪泛最大值算法中，在diam轮内，进程i_max输出自己为领导者，其他的进程输出自己为非领导者。

证明 很容易证明以下断言：

断言4.1.1 在diam轮后，，并且对于每一个不等于i_max的j，status_j=non-leader。

对于断言4.1.1证明的关键是，在r轮过后，沿着G中的有向路径，最大UID已经到达了那些与i_max的距离在r之内的所有进程。这个条件可由下面的不变式断言得到：

断言4.1.2 对于每一个j和0≤r≤diam，在r轮后，如果从i_max到j的距离不超过r，那么max-uid_j=u_max。

尤其是从图的直径的定义来看，断言4.1.2暗示着每个进程在diam轮后就会有最大的UID。为了证明断言4.1.2，我们还需要有以下辅助的不变式断言。

断言4.1.3 对于每个r和j，在r轮后，rounds_j=r。

断言4.1.4 对于每个r和j，在r轮后，max-uid_j≤u_max。

将断言4.1.2、断言4.1.3和断言4.1.4中的r定为diam-1，再加上对发生第diam轮的情况的证明，就能证明断言4.1.1。

洪泛最大值算法可以被认作在3.3节中LCR算法的推广，因为LCR算法也是把最大的UID值在整个环形网络中传递。但是，注意LCR算法并不需要任何与网络有关的特殊信息，如网络直径等。在LCR中，一个进程在消息中接收到自己的UID之后，就会把自己选为领导者，而洪泛最大值算法在特定轮数之后才把自己选为领导者。这样特殊的策略只在环形网络中才能成立，而不适应于一般的有向图。

复杂性分析 很容易可以看出，直到领导者被选出（并且其他进程知道自己不是领导者），所需时间为diam轮。消息数为diam·|E|，其中|E|是有向图中有向边的数目，这是因为在开始的diam轮中，每轮都要在每条有向边上发送一个消息。

直径的上界 注意，即使所有进程都知道一个直径的上界d而不知道直径本身，算法也可以有效地工作。此时算法复杂度将随d而不是diam增长。