中国科学技术大学计算机系 国家高性能计算中心（合肥） 第二部分 分布式算法 第七次课 中国科学技术大学计算机系 国家高性能计算中心（合肥）

§3.4.2 有限制算法的下界Ω(nlgn) 时间复杂度会表现很差 上节中的两个算法在同步环上最坏的msg复杂度为O(n)，但两算法的缺陷为： ① 它们用一种非同寻常的方式使用id，即id决定msg延迟多长； ② 在每个容许的执行中，执行轮数依赖于id，而id相对于n而言可能是巨大的。(更主要的) 本节将说明： ① 这些性质对于基于消息的有效算法而言是固有的； ② 若一个算法中的标识符仅用于比较，则它需要Ω(nlgn)个msgs； ③ 若一个算法中，限制轮数的上界，但独立于id，则它的msg复杂度亦为Ω(nlgn)。 时间复杂度会表现很差

§3.4.2 有限制算法的下界Ω(nlgn) 同步的下界不可能从异步的下界导出 因为上节中的算法表明：同步模型中的附加假定是必不可少的。 同步的下界对于非均匀和均匀算法均成立，但异步的下界只对均匀算法成立。 但是从同步导出的异步结果是正确的，并且提供了一个非均匀算法的异步下界。 异步通信模型中领导者选举问题 所需的消息数下界为Ω(nlgn)且 算法不依赖于比较的或者限时的

§3.4.2 有限制算法的下界Ω(nlgn) 基于比较的算法的概念和定义 为了得到下界，假定所有处理器在同一轮开始执行 一个环是由结点表按顺时针方向指定的，结点表开始于最小标识符。 在同步模型里，算法的容许执行完全由初始配置定义，这是因为msg延迟及节点步骤的相对次序均无选择的可能。 系统的初始配置完全由环决定，即由节点标识符列表按上述规则来决定。当算法的选择可以从上下文判断清楚时，则将由环R确定的容许执行表示为exec(R). 匹配：若环R1上的结点pi和R2上的pj在各自的环里具有相同的位置，则称pi和pj是匹配的，即：匹配的结点在各自环上距其最小id的结点的距离相同。

§3.4.2 有限制算法的下界Ω(nlgn) 基于比较的算法 1）序相同（order equivalent） 直观上，若一个算法在两个相对次序相同的环上具有相同的行为，则该算法是基于比较的，形式定义： 1）序相同（order equivalent） 两个环x0, x1,…, xn-1和y0, y1,…,yn-1是(次)序等价的，若对每个i和j，xi<xj, 当且仅当yi<yj。 回忆一下环上的结点pi的k-邻居是2k+1个结点的序列(下标是mod n)： pi-k, …, pi-1, pi, pi+1,…, pi+k 序等价的概念很容易扩展到k-邻居集(所有索引按模n计算)

§3.4.2 有限制算法的下界Ω(nlgn) 2）何谓行为相同(similar)？ 直观上：在序等价的环R1和R2上的容许执行里，发送同样的msg做同样的决策。但一般情况下，算法发送的msg包含结点的id，因此，R1上发送的msg通常不同于R2上发送的msg。然而，我们关注的是msg模式和决策。所谓msg模式(patten)是指：msg是何时何地发送的，而不是指其内容。 节点在第k轮里行为相似：考虑两个执行α1，α2和两个结点pi，pj，我们说pi在α1的第k轮里的行为相似于pj在α2的第k轮里的行为，若下述条件成立： ① pi在α1的第k轮里发送一个msg到其左(右)邻居当且仅当pj在α2的第k轮里发送一个msg到其左(右)邻居； ② pi在α1的第k轮里作为一个leader终止当且仅当pj在α2的第k轮里作为一个leader终止。

§3.4.2 有限制算法的下界Ω(nlgn) 算法的行为相似：指每对匹配的结点行为相似 节点的行为相似：若α1里pi和α2里pj在所有的k≥0轮里均相似，则称α1里pi和α2里pj的行为相似。 算法的行为相似：指每对匹配的结点行为相似 3）定义 Def 3.2 一个算法是基于比较的，若对于每对序等价的环R1和R2，每对匹配的节点在exec(R1)和exec(R2)里的行为均相似。 该定义说明，若一算法只与环上标识符之间的相对次序相关，而与具体id值无关，则该算法一定只是基于标识符的比较

§3.4.2 有限制算法的下界Ω(nlgn) 2. 基于比较算法的下界 2. 基于比较算法的下界 设A是一个基于比较的leader选举算法，证明时考虑的环就序模式而言具有高度的对称性。即：环里存在很多次序等价的邻域。 直观上，只要两个节点有序等价的邻域，它们在A里就有同样的行为。我们将通过在一个高度对称的环里执行A来导出下界。讨论若一结点在某轮里发送一个msg，则具有序等价邻域的所有结点也在同一轮里发送一个msg。 证明的关键是：区别获得信息的轮及没有获得信息的轮. Note：在同步环里，一个结点即使没有收到一个msg也会获得info，例如，在§3.4.1里的非均匀算法中，若第1到第n轮里未接收到msg，实际上蕴含着信息：环里没有标识符为0的结点。

§3.4.2 有限制算法的下界Ω(nlgn) 下面的证明关键是观察： 若某一轮r里不存在msg也对于结点pi是有用的(指可获取info)，则仅当存在一个次序等价的不同环，在该环上的第r轮里已接收一个msg 例如，在非均匀算法中，若环上某一个结点的id为0，则在第1, 2, …, n轮里均已收到msg。但对于一个次序等价的不同环(设最小id>0)，则它在前n轮里就没有任何msg存在。但同样认为前n轮对每个结点是有用的。 因此，若某一轮在任何次序等价的环上均无msg发送，则该轮是无用的，而有用的轮被称为是主动的(active)。

§3.4.2 有限制算法的下界Ω(nlgn) Def 3.3 在一个环R上的一个执行里，某轮r称为是active的，若该执行的第r轮里，某一个结点发送一个msg。当R是从上下文已知时，用rk表示第k个active轮。 Note： 一旦环R确定，整个容许执行就确定(因为系统同步) 由于一个基于比较的算法在等价环上的行为相似，因此： 对于序等价的环R1和R2，一轮在exec(R1)里是主动的当且仅当它在exec(R2)里也是主动的。 因为消息中的信息在k个轮里只能在环上通过k个结点，所以一个结点在k轮之后的状态只依赖于它的k-邻居。 然而一个更强的性质是：一个结点在第k个主动轮之后的状态只依赖于它的k-邻居。这实际上告诉我们：信息只有在主动轮里才能获得。这一点在下面的引理中给出形式证明。

§3.4.2 有限制算法的下界Ω(nlgn) Note：该引理无需结点匹配(否则立即从定义3.2中可得结论)，但要求它们的邻居是相同的(identical)。该引理要求假设两个环是次序等价的，原因是要确保考虑中的两个执行有相同的主动轮集合，因此rk是良定义的。 Lemma3.16 设R1和R2是次序等价的两个环，设Pi和Pj分别是R1和R2上具有相同k-邻居的两个节点，那么在exec(R1)的第1至第rk轮里Pi所经历的转换序列和在exec(R2)的第1至第rk轮里Pj所经历的转换序列相同。 //该引理蕴含：在k个主动轮结束时，Pi和Pj的状态相同 Pf：非形式地，该证明说明在k个主动轮之后，一个结点可能只知道距离自己至多为k的那些结点。形式证明对k进行归纳。

§3.4.2 有限制算法的下界Ω(nlgn) 归纳基础：k=0，因为两个具有相同0-邻居的结点有同样的id，故它们的状态相同； 归纳假设：假定每两个具有相同(k-1)-邻居的结点在(k-1)个主动轮之后有相同的状态； 归纳步骤：因为Pi和Pj有相同的k-邻居，故它们亦有相同的(k-1)-邻居。因此由归纳假设知，Pi和Pj在第(k-1)个主动轮之后处在相同的状态。又因Pi和Pj各自的邻居有同样的(k-1)-邻居，故由归纳假设知，它们各自的邻居在第(k-1)个主动轮之后也处在相同的状态。 两个主动轮之间可能有非主动轮。 因为在第(k-1)主动轮和第k主动轮之间的轮(若有的话)里，没有结点接收任何msg，故Pi和Pj及各自的邻居均处在相同的状态(Note: Pi在非主动轮里可能改变它的状态，但因为Pj有同样的转换函数，故它有同样的状态转换)。

§3.4.2 有限制算法的下界Ω(nlgn) 在第k个主动轮里： i)若Pi和Pj均不接收msg，则它们在该轮结束时有相同的状态； ii)因为Pi 和Pj的邻居状态相同，若Pi接收右(左)邻的一个msg，则Pj也接收右(左)邻同样的msg。因此，在第k个主动轮结束之后，Pi和Pj均处于相同的状态。 下一引理将上述论断从具有相同k-邻居的结点扩展至具有次序等价的k-邻居的结点。这依赖于事实：A是基于比较的。 更进一步要求环R是有空隙的，即环R中，每两个id之间均有n个未使用的标识符。形式地，在大小为n的环上，若对于每一个标识符x，标识符x-1到x-n均不在环上，则该环称为有空隙的。

§3.4.2 有限制算法的下界Ω(nlgn) 因为R是有空隙环，故我们能够构造R’。例如，对于k=1和n=8有： 引理3.16定义在两环上(Pi和Pj的k-邻居相同)，引理3.17是定义在同一个环上(Pi和Pj的k-邻居序等价) Lemma3.17 设R是有空隙环，Pi和Pj是R上具有序等价k-邻居的两个结点。则Pi和Pj在exec(R)的第1到第rk轮里有相似的行为。 Pf：我们构造满足下述条件的另一个环R’： R’中的Pj和R中Pi的有相同的k-邻居； R’中的标识符唯一 R’和R序等价，R’中的Pj匹配于R中的Pj。 因为R是有空隙环，故我们能够构造R’。例如，对于k=1和n=8有：

§3.4.2 有限制算法的下界Ω(nlgn) R R’ Pi的1-邻居60，90，75 Pj的1-邻居60，90，75 R’中id唯一 10,30,20,40,60,90,75,100 60,90,75,91,92,94,93,95 Pj与10距离为1， Pj与60距离为1

§3.4.2 有限制算法的下界Ω(nlgn) R上的Pi和R’上的Pj的前k个主动轮行为相似 因为R上Pi和R’上Pj的k-邻居相同，由引理3.16知，Pi和Pj在各自的exec(R)和exec(R’)的1到rk轮里所经历的转换序列相同，所以Pi和Pj在各自的执行exec(R)和exec(R’)的1至rk轮里的行为相似。 Pi(R) ∽ Pj(R’) (2)R上的Pj和R’上的Pj的前k个主动轮行为相似 因为算法是基于比较的，由定义3.2在两个序等价的环中，每对匹配的结点在各自执行中有相似的行为。而R里的Pj和R’里的Pj是匹配的，故R里的Pj在exec(R)的1至rk轮里的行为相似于R’里的Pj在exec(R’)的第1至rk轮里的行为。 Pj(R’) ∽ Pj(R) (3)R上两节点的k-邻居序等价，则其行为在前k个主动轮里相似 由(1)和(2)得：R里的Pi和Pj在exec(R)的1至rk轮里的行为相似。Pi(R) ∽ Pj(R) □

§3.4.2 有限制算法的下界Ω(nlgn) Th3.18 对于每个n≥8(n是2的幂)，存在一个大小为n的环Sn，使得对每个基于比较的同步leader选举算法A，在Sn上A的容许执行里发送msg的数目为Ω(nlgn) Pf：固定算法A。证明分2步： (1) 构造1个高度对称(很多结点有很多序等价的邻居)的环Sn； (2) Sn上发送的msg总数。 （1）构造Sn（分2步构造） 定义大小为n的环 ： 对∀i∈[0，n-1]，设Pi的id为rev(i)，这里rev(i)是i的二进制表示的逆序列。

§3.4.2 有限制算法的下界Ω(nlgn) 若将环 划分为长度为j(j是2的方幂)的连续片断，则所有这些片断是序等价的(Ex3.9)。 例如，4,2,6,1和5,3,7,0序等价 2,6,1,5和3,7,0,4序等价

§3.4.2 有限制算法的下界Ω(nlgn) 从 构造Sn 将 上每个id乘以(n+1)再加上n所获得的Sn是有空隙环。但这种变化不改变片断的序等价性。 (2) Sn上发送的msg总数（分3步） ①求Sn中序等价的邻居集数目（引理3.19） ②由①证明算法里主动轮数目下界（引理3.20） ③由①求每个主动轮里发送msg数目的下界(引理3.21) 由②和③的组合即可获得算法的msg复杂性下界。

§3.4.2 有限制算法的下界Ω(nlgn) Lemma3.19 对所有k<n/8以及每个Sn的k-邻居集N，在Sn中与N序等价的k-邻居集的个数(包括N本身)大于 Pf： N由2k+1个id构成，设j是大于2k+1的2的最小方幂。将Sn划分为n/j个连续片断，使某一片段包含N。 由Sn的构造可知，上述划分所得的所有片段均是序等价的。因此，至少有n/j个邻居集和N是序等价的。 设j=2i，∵2i-1<2k+1<2i，∴j<2(2k+1) 故与N序等价的邻居集数目>

§3.4.2 有限制算法的下界Ω(nlgn) Lemma3.20 在exec(Sn)里，主动轮的数目至少为n/8。 Pf：设主动轮数目T<n/8。//反证法 设Pi是exec(Sn)里被选为leader的结点，由引理3.19知，与Pi的T-邻居集序等价的T-邻居集个数大于 因此，存在某个异于Pi的结点Pj，Pj的T-邻居集与Pi的T- 邻居集是序等价的。由引理3.17知，Pj与Pi的行为相似， 故Pj亦被选为leader，这与A是正确的算法矛盾！□

§3.4.2 有限制算法的下界Ω(nlgn) Lemma3.21 对于∀k∈[1，n/8]，在exec(Sn)的第k个主动轮里，至少有 个msg被发送。 Pf：考虑第k个主动轮，因它是主动的，故该轮里至少有一结点发送一个msg，不妨设Pi发送一个msg。 由引理3.19知，与Pi的k-邻居集序等价的k-邻居集个数大于 ，因为每个k-邻居集中至少有一个结点(k≥1)，这也就是说至少有 个结点，其k-邻居集与Pi的k-邻居集序等价。 因此，由引理3.17知，这些结点与Pi的行为相似，即它们在第k个主动轮中发送msg。

§3.4.2 有限制算法的下界Ω(nlgn) 由引理3.20和3.21知，在exec(Sn) 里发送msg的总数至少为： 即Ω(nlgn)，Th3.18得证。□ 注意：为了使上述定理成立，要求标识符是取自集合{0,1,…,n2+2n-1}。//该集合的势为n2+2n。 原因是Sn中最小标识符为n，最大标识符为n2+n-1 =(n+1)*rev(n-1)+n。 但是证明所用到的引理3.17要求算法在比Sn中最小标识符小n及最大标识符大n的所有标识符上是可以比较的。//有空隙环。

§3.4.2 有限制算法的下界Ω(nlgn) 3.时间受限算法的下界 下面的定义中，算法的时间不依赖于id，仅受限于环大小n，即使id可能是无界的(因为它们来自于自然数集合)。 Def3.4 若对任意的n，当标识符取自于自然数集合时，在所有大小为n的环上同步算法A的最坏时间是有界的，则称A为时间有界(或时间受限time-bounded) 证明时间受限的同步算法的msg复杂性的下界的基本思想是： 将时间受限算法映射为基于比较的算法。从而获得时间受限算法的msg复杂性下界Ω(nlgn)

§3.4.2 有限制算法的下界Ω(nlgn) 因为基于比较的算法的msg下界是针对n为2的方幂讨论的(虽然对所有n值成立)，故下面仍针对n为2的方幂情况来讨论。 为了将时间受限算法映射到基于比较的算法，需要定义在某一时间界限内算法的行为。 Def3.5 设R1和R2是任意两个大小为n的序等价的环，若每对匹配的结点在exec(R1)和exec(R2)的第1至t轮里有相似的行为，则同步算法A对于环大小为n的标识符集合S是基于t-比较的。 直观上，S上的一个基于t-比较的算法可看做这样一个算法： 它的行为与一个基于比较的算法的前t轮的行为相同，只要基于比较算法的标识符也选自于S； 若算法在t轮内终止，则它和S上基于比较的算法在所有轮上完全相同。

§3.4.2 有限制算法的下界Ω(nlgn) 首先要说明每个时间受限算法的行为和一个输入子集上的基于比较算法的行为相同(假设输入集合足够大)。为此须用Ramsey定理的有限版本。非形式地，Ramsey定理陈述： 设有一个集合S，若用t种颜色中的一种对每个大小为k的子集着色，则我们能够找到某个大小为L的子集使得它的所有大小为k的子集有相同的颜色。若将着色看做等价类划分(若两个大小为k的子集着相同颜色，则它们属于同一等价类)，则该定理说明存在一个大小为L的集合，其所有大小为k的子集是同一个等价类。 稍后，我们将对匹配结点行为相似的环着上相同颜色。 例：面试老师分为t组，每组有k个老师；面试学生集S中任何人可以到任何一组面试，则能找到某个L值，这L个学生中所有k个人的子集是在同一房间面试的。

§3.4.2 有限制算法的下界Ω(nlgn) Ramsey’s Theorem (finite version) 对所有正整数k,L和t，存在一个整数 f(k,L,t)使得对每一个大小至少为 f(k,L,t)的集合S，对S的k-元子集的每一个t-着色，S的某一个L-元子集中所有k-元子集具有同样的颜色(L≥k) 。（着色等价类划分） 在下面的引理中，用Ramsey定理将任何时间受限算法映射到基于比较的算法上。 Lemma3.22 设A是一个运行时间为r(n)的时间受限的同步算法，则对于每个n，存在一个具有n2+2n个id的集合Cn，使得A是Cn上的一个基于r(n)-比较的算法，这里n是环大小。

§3.4.2 有限制算法的下界Ω(nlgn) Pf：固定n。设Y和Z是N(自然数集合)的任意两个n-元子集。 Y和Z称为等价子集，若对于每对序等价的环R1和R2(R1和R2中的标识符分别来自于Y和Z)，匹配结点在exec(R1)和exec(R2)的第1至r(n)轮里均有相似的行为。 该定义将N的n-元子集划分为有限多个等价类，因为行为相似仅指是否发送和接收msg，是否终止。我们对N的n-元子集着色使得两个n-元子集颜色相同当且仅当它们在同一等价类中。 由Ramsey定理，若设t是等价类(颜色)的数目，L为n2+2n，k为n，则因为N是无限集，存在一个势为n2+2n的子集(N的子集)Cn，使得Cn的所有n-元子集属于同一个等价类。//N相当于定理中的S {f(k,n2+2n,t)} ∈N

§3.4.2 有限制算法的下界Ω(nlgn) 考虑大小为n，标识符来自Cn的两个序等价的环R1和R2，设Y和Z分别是R1和R2的标识符集合，Y和Z显然均是Cn的n元子集，所以它们属于同一个等价类。 由等价子集定义知：匹配的结点在exec(R1)和exec(R2)的第1至r(n)轮里均有相似的行为。因此，A是Cn(环大小为n)上的一个基于r(n)-比较的算法(由def3.5) Note：因为上述引理中算法A中的标识符是特定的，故还不能直接用Th3.18导出其msg复杂性为Ω(nlgn)。因此，须使用A来构造A’，使A’的复杂性与A相同，且ids来自于集合{0,1,…,n2+2n-1}。因为基于比较的算法的ids来自于该集合。

§3.4.2 有限制算法的下界Ω(nlgn) Th3.23 对每个同步的时间有界的leader选举算法A，以及每个n>8，n为2的方幂，存在一个大小为n的环R，使得A在R上的容许执行里发送Ω(nlgn)个msgs。 Pf：设A是运行时间为r(n)且满足定理假设的算法。固定n，设Cn是满足引理3.22的标识符集合，c0,c1,…cn2+2n-1是Cn中按递增序排列的元素。 下面构造算法A’是基于比较的，它所执行的环大小为n，标识符集为{0,1,…,n2+2n-1}，它和A有同样的时间和msg复杂性。

§3.4.2 有限制算法的下界Ω(nlgn) 在算法A’中，一个标识符为i的结点执行算法就好像A在标识符Ci上执行一样。因为A在Cn上是基于r(n)-比较的且A在r(n)轮里终止，所以A’在大小为n的环上是基于比较的，且环上标识符来自于集合{0,1,…,n2+2n-1}。 由定理3.18，存在一个标识符来自于{0,1,…,n2+2n-1}，大小为n的环，算法A’在该环上发送的msg为Ω(nlgn)。 由A’的构造方法知，在大小为n、标识符来自于Cn的环上，存在A的一次执行，它发送的msg个数与A’相同。故定理得证。□ Ex3.9 若将环 划分为长度为j(j是2的方幂)的连续片段，则所有这些片段是次序等价的。

下次继续！