3.6 基于比较的算法的下界

到现在为止，我们已经列出了好几种在同步环中的领导者选举算法。LCR和HS算法都是基于比较的，并且后者的通信复杂度为O(nlogn)，时间复杂度O(n)。另一方面，时间片和变速算法不是基于比较的，消息数为O(n)，但是需要很长的运行时间。在本节中，我们证明基于比较的算法的消息数下界为Ω(nlogn)。即使我们假设通信是双向的而且环的大小n是已知的，这个下界也不会改变。在下一节中，我们将针对具有受限时间复杂度的非基于比较的算法，证明一个类似的消息数下界Ω(nlogn)。

本节的结果是基于打破对称性的难度。回想一下定理3.1中的不可能性结果，因为对称性，如果缺少如UID这样的区别信息，就不可能选出一个领导者。下述证明的主要思想是，即使存在UID，也有可能发生某些对称性。在这种情况下，UID允许打破对称性，但是需要大量通信来实现。

在整章中，我们假设所有的进程除了它们的UID之外都是相同的。所以，除了那些包含进程UID的分量之外，进程的开始状态都是相同的。总之，我们并没有强行限制消息生成函数和状态迁移函数应该怎样使用UID的信息。

在本章的剩余部分中（本节和下一节），我们假设对于每个UID，只有一个开始状态包含这个UID（如定理3.1的证明中所示，此假设不失一般性）。这样假设的好处就是，它意味着系统（具有固定的UID指派）恰好只有一次运行。

一个基于比较的算法会遵守一些额外的约束，下面用不太形式化的定义来表示。在一个基于UID的环算法中，如果进程处理UID的唯一方法是复制它们、在消息中发送和接收它们以及用{＜,=,＞}来比较它们，那么算法就是基于比较的。

举例来说，这样的定义允许一个进程存储它所碰到的各种各样的UID，并且可能与其他的信息组合起来在消息中发送它们。进程还可以比较这些存储的UID，并用比较的结果在消息生成函数和状态迁移函数中选择。例如，这些选择可以包括是否要向它的每个相邻节点发送消息、是否要选举自己作为领导者以及是否需要保存UID，等等。一个重要的事实就是，一个进程的所有活动都只是依赖于它所面对的UID的相对次序，而不是这些UID的具体值。

下面的形式化表示用于阐述即使具有UID，对称性还是可以存在。设U=(u₁,u₂,…,u_k)和V=(v₁,v₂,…,v_k)为两个UID序列，其长度都为k。对于所有的i,j(1≤i,j≤k)，我们称U次序等价于V，当且仅当v_i≤v_j时有u_i≤u_j。

例3.6.1 次序等价

如果UID集是按正常排序的自然数，则序列(5,3,7,0)，(4,2,6,1)和(5,3,6,1)都是次序等价的。

注意，当且仅当对应UID的相对次序相同时，两个UID序列才能被认作次序等价。下面有两个技术性的定义。如果在运行的一轮中至少有一条（非空）消息被发送，那么这一轮就被称为活动的。在规模为n的环R中，进程i的k邻接节点（）被定义为由2k+1个进程i-k,…,i+k组成，即那些和进程i距离在k之内的进程（包括i本身）。

最后我们需要定义的是，除了进程包含的特定UID之外，进程状态是相同的。如果以下条件被满足，我们就称两个进程状态s和t对于UID序列U=(u₁,u₂,…,u_k)和V=(v₁,v₂,…,v_k)是对应的：s中的所有UID都是从U中选出的，t中的所有UID都是从V中选出的，且对于所有的i，1≤i≤k，将s中的u_i用t中的v_i代替后，t和s是相同的。同样可以给出对应消息的定义。

现在我们可以来证明关于下限的重要引理3.5了。它说明具有次序等价的k阶邻接节点的不同进程，会表现出基本相同的行为，除非信息有机会从k阶邻接节点以外向这些进程传播。

引理3.5 设A是一个基于比较的算法，它在一个大小为n的环R中执行。令k为一个整数，。令i和j是A中的两个进程，在它们的k阶邻接节点中具有次序等价的UID序列。那么在至多k个活动轮之内的任一点，进程i和j对于其k阶邻接节点中的UID序列是对应的。

例3.6.2 对应状态

假设进程i的3阶邻接节点中的UID的序列为(1,6,3,8,4,10,7)（进程i的UID为8），进程j的3阶邻接节点的UID的序列为(4,10,7,12,9,13,11)（进程j的UID为12）。因为这两个序列是次序等价的，按照引理3.5，只要已发生的活动的轮数不大于3，进程i和j对于其3阶邻接节点就处于对应状态。粗略地说，其原因在于如果只有3个活动的轮，次序等价的3阶邻接节点以外的信息就没有机会到达i和j。

（引理3.5的）证明 不失一般性，我们可以假设i≠j。对运行中已经执行的轮数r做归纳。对于每个r，我们证明引理对所有的k成立。

基础：r=0。从基于比较的算法的定义来看，i和j的初始化状态除了各自的UID外都相同的，所以就它们的k阶邻接节点（对任意的k）而言，它们的初始状态是对应的。

归纳步：假设引理对所有的r′＜r都成立。固定k，使得i和j有次序等价的k阶邻接节点，并假设最初的r轮中包含最多k个活动轮。

如果i和j都没有在r轮接收到消息，那么根据归纳假设（对r-1和k）得知，i和j正好在r-1轮后对于其k阶邻接节点是对应的。因为i和j没有新的输入，因此它们会做对应的状态转移，并在第r轮后处于对应状态。

假设i或j在r轮时接收到了消息，那么r轮就是活动的，所以开始的r-1轮最多包括了k-1个活动轮。注意i和j拥有次序等价的k-1阶邻接节点，这对于i-1和j-1，以及i+1和j+1也都成立。所以，根据归纳假设（对r-1和k-1）得知，进程i和j在r-1轮后对于其(k-1)阶邻接节点是对应的。类似地，这对于i-1和j-1，以及i+1和j+1也是成立的。

我们继续对不同情况进行分析。

1）在第r轮，i-1和i+1都没有发送消息给i。

因为i-1和j-1在r-1轮以后处于对应状态，并且i+1和j+1也一样，所以j-1和j+1都没有在第r轮中发送消息给j。这与i或者j在第r轮接收到消息的假设相矛盾。

2）在第r轮，i-1给i发送消息，但是i+1没有。

那么，既然i-1和j-1在第r-1轮以后处于对应状态，j-1也在第r轮给j发送了消息，而且相对于i-1和j-1的k-1阶邻接节点而言，这个消息与i-1发送给i的消息是对应的，因此这两个消息对于i和j的k阶邻接节点也是对应的。鉴于类似的理由，j+1在第r轮没有给j发消息。因为i和j在r-1轮后处于对应状态，并且接收到了对应消息，所以现在它们对于k阶邻接节点依然是对应的。

3）在第r轮，i+1给i发送消息，但是i-1没有。

类似于对前面情况的分析。

4）在第r轮，i-1和i+1都给i发送了消息。

同理。

引理3.5告诉我们，如果存在很大的次序等价的邻接节点，那么需要有许多活动轮来打破对称性。现在我们定义具有特殊属性的环，它们有许多不同大小的次序等价的邻接节点。设c为常数，0≤c≤1，并设R是规模为n的环。如果对每一个l，，以及对于R中长度为l的每一段S，在R中至少存在个次序等价于S的段（包括S本身），那么，我们称R是c对称的[1]。

如果n是2的幂，那么构造一个1/2对称的环是很容易的。特别地，我们定义大小为n的位反转环如下：假设n=2k，那么，给每一个进程赋值[0，n-1]之间的一个整数，使其k位二进制表示恰好是i的k位二进制表示的反转（我们用0k作为n的k位二进制表示，使0与n相同）。

例3.6.3 位反转环

对于n=8，可得k=3，且赋值如图3-3所示。

引理3.6 任意一个位反转环都是1/2对称的。

证明 留为一道习题[2]。

对不是2的幂的n值，也总是存在c对称环，不过一般情况下需要一个较小的常数c。

定理3.7 存在一个常数c，使得对于所有n∈N+，存在大小为n的c对称环。

定理3.7的证明需要一个很复杂的递归构造[3]。所需的环不可能通过简单的方法产生，如从一个2的次小次幂的位反转环出发并加入额外的进程，这些额外的进程会破坏对称性。

所以我们可以假设，对任意n，存在一个大小为n的c对称环R。接下来的引理说明如果在这样的环中选出领导者，那么需要许多活动轮。

引理3.8 令A是一个在大小为n的c对称环中执行的基于比较的算法，并假设A选出了一个领导者。设k是满足的整数，则A有多于k个活动轮。

证明 采用反证法。假设A在最多k个活动轮中选出了领导者进程i。令S为i的k阶邻接节点，S是长度为2k+1的一段。因为环是c对称性的，所以在环网中至少有个片段与S是次序等价的，包括S本身。因此至少有一个其他片段与S次序等价；令j为那个片段的中点。现在，根据引理3.5，直到选出点为止，i和j在整个运行中都处于等价状态。我们可以得到结论j也被选出了。矛盾。

现在我们来证明下界。

定理3.9 令A是一个在大小为n的环中选出一个领导者的基于比较的算法，则存在A的一个运行，其中在领导者被选出之前有Ω(nlogn)条消息被发送[4]。

证明 固定一个由定理3.7断定存在的常数c，并使用定理3.7来获得一个大小为n的c对称环R。我们考虑在R中的算法运行。

定义，那么（假设n足够大），且。根据引理3.8，有多于k个活动轮，亦即至少有k+1个活动轮。

考虑第r个活动轮，其中。因为这是活动轮，所以某个进程i在r轮中发送了消息。令S为i的r-1阶邻接节点。因为R是c对称的，所以至少有个片段和S等价。

根据引理3.5，在第r个活动轮即将执行的时候，所有这些片段的中点都处于对应状态，所以它们都发送消息。

现在令和。以上的讨论说明了消息总数至少为

第二项为O(n)，因此表明第一项是Ω(nlogn)就足够了。

我们有

由和的整数近似，

正是所求。