3.7 非基于比较的算法的下界＊

我们能够描述非基于比较的算法的消息数的下限吗？虽然Ω(nlogn)的界限可以被打破，但是可能表明这样做只能以大的时间复杂度为代价。举个例子，假设选出领导者的时间界限为t。如果标识符空间中UID的总数足够大，比如，大于某个快速增长的函数f(n,t)，那么存在一个标识符的子集U，其上的算法可能表现得像基于比较的算法，至少在t轮中如此。这意味着针对比较的下限也适用于使用U中标识符的时间受限算法。

我们会给出更多细节，但表示形式仍然只是一个大概。用Ramsey定理定义一个快速增长的函数f(n,t)，Ramsey定理是一种扩展的鸽巢原理。在定理的叙述中，一个n维子集就是有n个元素的子集，一个着色就是给每一个集合指定一种颜色。

定理3.10（Ramsey定理） 对于所有的整数n、m和c，总存在一个整数g(n,m,c)满足以下性质：对于每个大小至少为g(n,m,c)的集合S，当使用最多c种颜色来对S的n维子集进行着色时，总有一个大小为m的S的子集C，C的所有n维子集的颜色相同。

作为开始，我们把每个算法都放入规范式（normal form），其中每个状态都以LISP的S表达式来简单地记录初始的UID和所有曾经收到的消息，而且每个非空消息都包含其发送者的完整状态。然后将其中的某些S表达式指定为选举状态，这种状态表示进程已被选为领导者。如果原来的算法是一个正确的领导者选举算法，那么新的（带有修改后的输出约定）也是，通信复杂度也是一样的。

下界定理描述如下。

定理3.11 对于所有的整数n和t，存在满足如下性质的整数f(n,t)：令A为任意（不必基于比较）的算法，该算法于时间t内在大小为n的环中选出领导者，并且使用了大小至少为f(n,t)的UID空间，则存在一个A的运行，其中领导者被选出之前发送的消息数为Ω(nlogn)。

证明概要 固定n和t。不失一般性，我们只考虑规范式中的算法。因为算法中只涉及n个进程且只执行t轮，所以所有出现的S表达式都有最多n个不同的参数和最多t层括号深度。

现在对于每个算法A，我们定义一个UID的n维集合（大小为n的集合）上的等价关系≡_A。粗略地说，如果算法A在两个n维集合上的行为是一样的，那么称这两个集合是等价的。更精确地，如果V和V′是UID的两个n维子集，并且对于V上每个深度最多为t的S表达式，在算法A中，V′上对应的S表达式（通过用V′中的元素代替V中排位相同的元素得到）产生相同的决定，即是否在每个方向发送一个消息和是否该进程已被选为领导者，则称V≡_AV′。

因为在等价关系定义中，S表达式最多有n个参数和t层深度，所以≡_A等价类的数目有限。事实上，有一个不依赖于算法A的等价类数的上界，它只依赖于n和t。令c(n,t)为这个上界。

现在固定算法A。我们来描述一个给UID的n维子集着色的方法，这样就可以应用Ramsey定理。也就是说，我们把n维集合的每一个≡_A等价类与一种颜色相联系，类中所有的n维子集都用那种颜色着色。

现在我们定义f(n,t)=g(n,2n,c(n,t))，其中g是定理3.10中的函数，并且考虑任一包括至少f(n,t)个标识符的UID空间。定理3.10暗示着存在一个含有至少2n个元素的UID空间的子集C，使得C的所有n维子集都着同一种颜色。令U为由C中n个最小元素组成的集合。

当从U中选择UID时，我们可以声称在t轮内，算法的行为完全像一个基于比较的算法。每个进程做出的有关是否要发送消息或者要让哪个进程成为领导者的决定只依赖于在当前状态下所含参数的相对次序。为了弄清楚其原因，我们固定U的任意两个子集W和W′，大小都为m。假设S是一个深度最多为t的S表达式，其UID从W中选取，而S′是W′上对应的S表达式。那么W和W′通过加进C中最大的n-m个元素，就可以被扩展成为V和V′，每个大小都是n。因为V和V′有相同的着色，因此这两个S表达式就会对于是否在每个方向发送消息和选择某个进程为领导者做出相同决定。

由于算法在t轮内的行为完全像一个基于比较的算法，因此当从U中选择UID时，定理3.9就产生了这个下界。