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

§3.3.3 下界Ω(nlgn) 现证明对于uniform算法，异步环里任何leader选举算法至少发送Ω(nlgn)个msgs。 选中的leader必定是环上具有最大id的处理器。 所有处理器必须知道被选中leader的id，即每处理器终止前，将选中leader的id写入一个特殊变量。 基本思想。 设A是一个能解上述leader选举变种问题的均匀算法，证明存在A的一个允许执行，其中发送了Ω(nlgn)个msgs，证明采用构造法。 2 2

这种扩展依赖于算法是一致的且对各种规模的环以相同的方式执行 §3.3.3 下界Ω(nlgn) 对于大小为n/2的环构造算法的一个耗费执行(指msg的耗费)，然后将两个大小为n/2的不同环粘贴在一起形成一个大小为n的环，将两个较小环上的耗费执行组合在一起，并迫使θ(n)个附加msg被接收。 调度：前面定义过调度是执行中的事件序列，下面给出能够被粘贴在一起的调度。 Def3.1 开调度 设σ是一个特定环上算法A的一个调度，若该环中存在一条边e使得在σ中，边e的任意方向上均无msg传递，则σ称为是open，e是σ的一条开边。 这种扩展依赖于算法是一致的且对各种规模的环以相同的方式执行 3 3

§3.3.3 下界Ω(nlgn) Note：开调度未必是容许的调度，即它可能是有限的事件序列，环上的处理器不一定是终止的。 直观上，既然处理器不知道环的大小，我们能将两个较小的开调度粘贴为一个较大环的开调度，其依据是：算法是均匀的。 为简单起见，不放设n为2的整数次幂。 Th3.5 对于每个n及每个标识符集合(大小为n)，存在一个由这些标识符组成的环，该环有一个A的开调度，其中至少接收M(n)个消息，这里： 4 4

§3.3.3 下界Ω(nlgn) 显然递归方程的解为M(n)=θ(nlgn)，他蕴含了异步环选举问题消息复杂度下界。下面用归纳法证明之，其中 Lemma3.6 对每个由两个标识符构成的集合，存在一个使用这两个标识符的环R，R有A的一个开调度，其中至少有一个msg被接受。（归纳基础） pf：假定R有两个处理器P0和P1，其标识符分别为x和y，不妨设x>y. 5 5

§3.3.3 下界Ω(nlgn) 设α是A的一个容许执行，因为A是正确的，在α中，最终P1定将P0的标识符写入其中。因此，α中至少须接收一个msg，否则P1不知道P0的标识符为x. 设σ是α的调度的最短前缀：它包括第一个接受msg的事件。因为没有接收第一条msg的边是开的，因此σ中只有一个msg被接收且有一条开边，故引理成立。故σ是满足引理的开调度。 Lemma 3.7 选择n>2，假定对每个大小为n/2标识符集合，存在一个使用这些标识符的环，它有A的一个开调度，其中至少接收M(n/2)个msgs(归纳假设)，那么对于n个标识符的每个集合，存在一个使用这些标识符集的环，它有A的一个开调度，其中接收至少2M(n/2)+(n/2-1)/2个msgs(归纳步骤)。 6 6

§3.3.3 下界Ω(nlgn) pf：设S是n个标识符的集合，将S划分为两个集合S1和S2，每个大小为n/2，由假设分别存在一个使用S1和S2中标识符的环R1和R2，它们分别有A的一个开调度σ1和σ2，其中均至少接收M(n/2)个msgs，设e1和e2分别是σ1和σ2的开边，不妨设邻接于e1和e2的处理器分别是p1，q1和p2，q2，将e1，e2删去，用ep链接p1和p2，eq链接q1和q2，即可将两个环R1和R2粘贴在一起形成环R。 现说明如何在R上构造一个A的开调度σ，其中至少有2M(n/2)+(n/2-1)/2个msg被接收。其想法是先让每个较小环分别执行“耗费”的开调度。 7 7

§3.3.3 下界Ω(nlgn) 1) σ1σ2构成R上A的一个开调度 考虑从R的初始配置开始发生的事件序列σ1，因为R1中的处理器由这些事件并不能区别R1是一个独立的环还是R的一个子环，它们执行σ1恰像R1是独立的那样。考虑环R上后续事件序列σ2(与上类似)，因为没有msg在ep和eq上传递，故R2中处理器在σ2中亦不能区别R2是独立环还是R的子环。 因此，σ1σ2是一个调度，其中至少有2M(n/2)个msgs被接收。 2) 现说明如何通过连通ep和eq(但不是二者)来迫使算法接收(n/2-1)/2个附加的msgs。 考虑每个形式为σ1σ2σ3的有限调度，因为σ1σ2中ep和eq均为开的，若σ3中存在一边上至少有(n/2-1)/2个msg被接收，则σ1σ2σ3是要找的开调度，引理被证。 假设没有这样的调度，那么存在某个调度σ1σ2σ3，它导致相应执行中的一个“静止”配置。(配置：由全体结点状态构成) 一个处理器状态是“静止”的：若从该状态开始的计算事件序列中不send消息，即处理器接收一个msg之前不发送另一msg（即处理器的内部事件不引发send动作） 8 8

§3.3.3 下界Ω(nlgn) 一个配置是“静止”的(关于ep和eq)：若除开边ep和eq外，没有msgs处在传递之中，每个处理器均为静止状态。 不失一般性，假设R中最大id的处理器是在子环R1中，因为没有msg从R1传到R2中，R2中的处理器不知道leader的id，因此R2里没有处理器能够在σ1σ2σ3结束时终止。(在σ1σ2σ3结束时，R2里无结点终止) 我们断定在每个扩展σ1σ2σ3的容许调度里，子环R2里的每个处理器在终止前必须接收至少一个附加msg，因为R2里每一处理器只有接收来自R1的msg才知道leader的id。 上述讨论清楚地蕴含在环R上必须接收Ω(n/2)个msgs，但因为ep和eq是连通的，故调度未必是开的，即两边上均可能传递msg。 但若能说明ep或eq只有一个是连通的，迫使通过它接收Ω(n/2)个msgs，即可证明。这就是下一断言。 9 9

§3.3.3 下界Ω(nlgn) Pf: 设 使得σ1σ2σ3 是一个容许调度，因此所有的msgs在ep和eq上传递，所有结点终止。 Claim3.8 存在一个有限的调度片断σ4，其中有 (n/2-1)/2个msgs被接收，σ1σ2σ3σ4是一个开调度，其中ep或eq是开的。 Pf: 设 使得σ1σ2σ3 是一个容许调度，因此所有的msgs在ep和eq上传递，所有结点终止。 因为R2里，每个节点在终止前必须收到一个msg，故在A终止前在 里至少接收n/2个msgs,设 是 里接收n/2-1个msg的最短前缀。 考虑 R 里在 中所有已接收msg的结点，因为我们是从一个静止位置开始的，其中只有在ep和eq上有msg在传输，故这些结点形成了两个连续的结点集合P和Q： P包含由于连通ep而被唤醒的结点，故P至少包含p1和p2 Q包含由于连通eq而被唤醒的结点，故Q至少包含q1和q2 10 10

§3.3.3 下界Ω(nlgn) 因为P∪Q中至少包含n/2-1个结点（由 决定），且又因它们中的结点是连续的，所以P∩Q=Φ。Ｐ和Ｑ这两个集合中有一个集合，其中的结点至少接收 (n/2-1)/2个msg,( 因为Ｐ，Ｑ中的结点共接收n/2-1个msg),不失一般性，假定这样的集合是Ｐ。 设σ4是 的子序列，σ4只包含在Ｐ中结点上发生的事件，因为 里Ｐ中节点和Q中结点之间没有通信，故σ1 σ2 σ3 σ4是一个调度。 因为σ4里至少有 (n/2-1)/2各msg被接收，且由构造可知，eq上无msg传递，因此σ1 σ2 σ3 σ4是一个满足要求的开调度。 11 11

§3.3.3 下界Ω(nlgn) 总结： Th3.5的证明可分为3步： 1) 在 R1和R2 上构造2个独立的调度，每个接收2M(n/2)各msg: σ1 σ2 2) 强迫环进入一个静止配置： σ1 σ2 σ3 （主要由调度片断σ3 ） 3) 强迫(n/2-1)/2个附加msg被接收，并保持ep或eq是开的: σ1 σ2 σ3 σ4。 因此我们已构造了一个开调度，其中至少有2M(n/2)+ (n/2-1)/2个msg被接收。 12 12

§ 3.4 同步环 研究同步环上leader选举问题的上、下界。 上界： 提出两个msg复杂性为O(n)的算法，显然，这样的算法的msg复杂性是最优的。但运行时间并非只与环大小n有关，还与算法使用的非普通的id相关。(与id值相关) 下界： 讨论 1）只基于标识符之间比较的算法 2）时间受限（即若干轮内终止，轮数只依赖于环大小,不依赖于id值）的算法 当算法受限于上述两个条件时，至少需要Ω(nlgn)个msgs. 13 13

§ 3.4.1 上界 O(n) 上节已证明在异步环上leader选举问题的msg复杂度下界为Ω(nlgn) ，其算法的关键是msg延迟是任意长的。 因为同步环上 1) msg延迟是确定的，故同步模型是否有较好的结果呢? 2) 获取info不仅来自于接收msg,在某轮里的内附件也能获取info 本节提出两个算法，msg复杂性上界为O(n),针对单向环，但是用于双向环 1) 非均匀的：要求环中所有的结点开始于同一轮，标准的同步模型 (需知道n) 2) 均匀的： 结点可开始于不同轮，弱同步模型 (无需知道n) 14 14

§3.4.1 上界O(n) Non-uniform Alg 基本特征 选择环中最小id（各id互不相同）的结点作为leader，按Phase运行，每个阶段由n个轮组成。在Phase i (i ≥ 0)，若存在一个id为i的结点，则该结点为leader，并终止算法，因此，最小id的结点被选为leader 显然，Phase数目取决于n个节点的标志符的取值。 具体实现 Phase i包括轮：n·i+1, n·i+2, …, n·i+n 在第i阶段开始，若一个结点的id是i，且它尚未终止，则该节点绕环发送一个msg后作为一个leader终止；若一结点的id不是i，且它收到一个msg，则它转发此msg后作为non-leader终止。

§3.4.1 上界O(n) 分析 正确性：显然，只有最小的标志符被选中作为leader Msg复杂性：恰有n个msg被发送，故复杂性为O(n)。注意这n个msg均是在找到leader的那个Phase里发送的。 时间复杂性 依赖于环大小和环上最小标志符，不妨设环大小为n，最小标识符为i，则算法执行轮数为：n·(i+1)，不妨设i≥0 //运行时间与环大小及标识符取值相关 缺点 必须知道环大小n和同步开始，下面算法克服了这些限制 ①为什么id为i的结点要在phase i发msg ∵各结点互不知道彼此的id值 ∴只能在第i phase，结点(id=i)发自己的id ②为什么每个phase要n轮

§3.4.1 上界O(n) Uniform Alg 特点：①无须知道环大小，②弱同步模型 一个处理器可以在任意轮里自发地唤醒自己，也可以是收到另一个处理器的msg后被唤醒 基本思想 ① 源于不同节点的msg以不同的速度转发 源于id为i的节点的msg，在每一个接收该msg的节点沿顺时针转发到下一个处理器之前，被延迟2i-1轮 ② 为克服非同时启动，须加一个基本的唤醒阶段，其中每个自发唤醒的结点绕环发送一个唤醒msg，该msg转发时无延迟 ③ 若一个结点在算法启动前收到一个唤醒msg，则该结点不参与算法，只是扮演一个relay(转发)角色：即转发或没收msg

§3.4.1 上界O(n) 要点：在基本阶段之后，选举leader是在参与结点集中进行的，即只有自发唤醒的结点才有可能当选为leader。 具体实现 ① 唤醒：由一个结点发出的唤醒msg包含该结点的id，该msg以每轮一边的正常速率周游，那些接收到唤醒msg之前未启动的结点均被删除(不参与选举) ② 延迟：当来自一个id为i的节点的msg到达一个醒着的节点时，该msg以2i速率周游，即每个收到该msg的节点将其延迟2i-1轮后再转发。 Note： 一个msg到达一个醒着的节点之后，它要到达的所有节点均是醒着的。一个msg在被一个醒着的节点接收之前是处在1st阶段 (唤醒msg，非延迟) ，在到达一个醒着的节点之后，它就处于2nd阶段，并以2i速率转发(非唤醒msg，延迟)

§3.4.1 上界O(n) ③ 没收规则 a) 一个参与的节点收到一个msg时，若该msg里的id大于当前已看到的最小(包括自己)的id，则没收该msg； b) 一个转发的节点收到一个msg时，若该msg里的id大于当前已看到的最小(不包括自己)的id，则没收该msg。

§3.4.1 上界O(n) 算法 Alg3.2 同步leader选举 var waiting : init Φ; asleep : init true; //加上relay更好 ？ : init false; 1: 设R是计算事件中接收msg的集合 2: s:= Φ;// the msg to be sent 3: if asleep then { 4: asleep:=false; 5: if R = Φ then { // pi未收到过msg，属于自发唤醒 6: min:=id; //参与选举 7: s:=s+{<id>}; // 准备发送 }else{ //已收到过msg，但此前未启动，被唤醒故Pi不参与 8: min:=∞; //选举，置min为∞ ，使其变为relay结点 // relay:=true; ？ }

§3.4.1 上界O(n) 9: for each <m> in R do {// 处理完收到的m后相当于从R中删去 10: if m < min then { // 收到的id较小时通过 11: become not elected; // Pi未被选中 //可用relay控制使转发节点不延迟？ 12: 将<m>加入waiting且记住m何时加入; //m加入延迟转发 13: min:=m; } // if m > min then it is swallowed 14: if m=id then become elected; // Pi被选中 } //endfor 15: for each <m> in waiting do 16: if <m> 是在2m-1轮之前接收的 then 17: 将<m>从waiting中删去并加入S 18: send S to left;

§3.4.1 上界O(n) 分析 下面证明，在第1个结点被唤醒之后的n轮，只剩下第二阶段的msg，只有参与的结点才有可能被选中。 (1) 正确性 对∀i∈[0,n-1]，设idi是结点pi的标识符，<idi>是源于pi的msg Lemma 3.9 在参与的节点中，只有最小id的节点才能收回自己的id。 pf：①选中：设pi是参与者中具有最小id的结点(Note：至少有1个结点须参与算法)，显然没有节点(无论是否参与)能没收<idi>；另一方面，因为在每个节点上<idi>至多延迟2idi轮，故pi最终收回自己的id； ②唯一：除pi外，没有别的节点pj ( j≠i ) 也收回自己的<idj>。 若pj收回自己的<idj> ，则<idj>已通过pi及其它所有结点，但idi< idj，因为pi是一个参与者，它将不会转发idj，矛盾！ 该引理蕴含着：恰有一个结点收回自己的msg，故它是唯一声明自己是leader的结点，即算法正确。

§3.4.1 上界O(n) (2) msg复杂性 在算法的一次容许执行里，发送的msg可分为三个类型： 第二类：最终leader的msg进入自己的第二阶段之前发送的 第二阶段msg(其它结点发出的) 第三类：最终leader的msg进入自己的第二阶段之后发送的 第二阶段msg(包括leader发出的) Note：一个msg发送时，一开始是作为唤醒msg(非延迟)，当它到达的结点已唤醒时，msg就变为非唤醒msg(第二阶段，延迟msg)

§3.4.1 上界O(n) ① 第一类msg总数(第一阶段的msg) Lemma 3.10 第一类msg总数至多为n pf：只要说明每个节点在第一阶段至多转发一个msg即可。 反证：假设某结点pi在其第一阶段转发两个msgs：一个来自pj的<idj>，一个来自pk的<idk>。不失一般性，pj比pk更靠近pi(沿顺时针方向)。因此，<idk>到达pi之前先到达pj。 若<idk>是在pj自发唤醒及发送<idj>之后到达pj，则<idk>以2idk速度作为第二阶段msg继续前进；否则，pj不是参与结点，不会发送<idj>。 因此，或者<idk>是作为第二阶段msg到达pi，或者<idj>未被发送，即：pi最多收到一个第一阶段msg，矛盾！

§3.4.1 上界O(n) ② 第二类msg总数 (最终leader发出的msg进入自己的第二阶段之前发送的第二阶段msg) 为了求得第二类msg总数，首先说明第一个开始执行算法的结点启动之后的n轮，所有的msg均在自己的第二阶段中。 设pi是最早开始执行算法的结点中的某一个，其启动轮数为r。 Lemma 3.11 若pj距离pi为k(顺时针)，则pj 接收的第一阶段的msg不迟于第r+k轮。

§3.4.1 上界O(n) pf：对距离k归纳 基础：k=1，因为pi的 左邻居在第r+1轮接收到 pi的msg，故引理成立。 假设：设距离pi为k-1 的结点接收第一阶段 的msg不迟于r+k-1轮。 步骤 若距离pi为k-1的结点pt(顺时针)接收第一阶段msg时已被唤醒，则pt已发送了第一阶段msg给邻居pj； 否则，pt至迟在第r+k轮转发第一阶段msg到pj。

§3.4.1 上界O(n) Lemma 3.12 第二类msg总数至多为n pf：由引理3.10可知，在每边上至多只发送1个第一阶段的msg，又因为到第r+n轮，每边上已发送了一个第一阶段msg，故到第r+n轮之后，已无第一阶段的msg被发送。 Note：第一阶段msg是唤醒msg，即若在pi(第一个启动结点)发出唤醒msg绕环一周回到pi之前已有某结点启动，则该启动结点的msg在未收到pi的msg之前已将自己的唤醒msg向前转发。

§3.4.1 上界O(n) i) 第二类msg经历的总轮数： 由引理3.11知，最终的leader(不一定是首个启动者)的msg进入自己的第二阶段的时刻是：算法的第1个msg被发送之后至多n轮(前n轮)，故第二类被发送的msg必是在首个启动结点的n轮之中。 ii) 在这n轮中，第二类msg数目。即第二类msg是算法启动的前n轮中非唤醒msg的总数：

§3.4.1 上界O(n) 因为msg<i>在其第二阶段中，转发前须延迟2i-1轮，所以若<i>是第二类msg，则它至多被发送n/2i次。 因为较小id被转发的次数较多，故可这样构造以使msg数目最大： 所有结点均参与选举，标识符均尽可能小：0, 1, …, n-1（顺时针排列）。显然，因为id=0是leader，第二类msg中不包括leader的msg，故第二类msg总数至多是：

§3.4.1 上界O(n) ③第三类msg总数 (即：leader进入自己的第二阶段之后，所有非唤醒msg) Lemma 3.13 在<idi>返回pi之后，没有msg被转发 pf： 设pi是具有最小id的结点，当一结点转发<idi>之后，该结点将不再会转发其它msg。 若<idi>返回pi，则所有结点均已转发过<idi>, 故再也没有其它msg被转发。

§3.4.1 上界O(n) Lemma 3.14 第三类msg总数至多为2n pf：设pi是最终的leader，pj是某个参与的结点，由引理3.9知，idi<idj，由引理3.13知，在pi收回自己的idi之后，环上不再有msg在传输。 i) 第三类msg经历的总轮数：因为在每个结点上，<idi>至多延迟2idi轮(在唤醒结点上不延迟，故为至多)，所以<idi>返回pi至多经过n· 2idi轮。 ii) 在这n· 2idi轮中，第三类msg数目：第三类msg是在这n· 2idi轮中发送的所有第二阶段msg(非唤醒msg)。在这n· 2idi轮中，一个非唤醒的msg<idj>被转发的次数至多为：

§3.4.1 上界O(n) 故有：第三类msg总数至多为(包括leader) 这里，∀idi∈[0，n-1] Th3.15 存在一个同步的leader选举算法，其msg复杂度至多为4n pf：由引理3.10，3.12及3.14立即可得。

§3.4.1 上界O(n) (3) 时间复杂度 由引理3.13知，当leader接收到自己的id时，计算终止。这发生在第一个启动算法的节点之后的O(n· 2i)轮，其中i是leader的标识符。 // 当i=0时，为O(n)轮 //运行时间与环大小及标识符取值相关 (4) 思考 为何非唤醒msg要延迟2i -1轮？ 如何修改算法3.2来改善时间复杂性？

下次继续！