环上选举算法.pptVIP

第三章 环上选举算法 汪 炀 上节中的两个算法在同步环上最坏的msg复杂度为O(n)，但两算法的缺陷为： ① 它们用一种非同寻常的方式使用id，即id决定msg延迟多长； ② 在每个容许的执行中，执行轮数依赖于id，而id相对于n而言可能是巨大的。(更主要的) 本节将说明： ① 这些性质对于有效的msg算法而言是固有的； ② 若一个算法中的标识符仅用于比较，则它需要Ω(nlgn)个msgs； ③ 若一个算法中，限制轮数的上界，但独立于id，则它的msg复杂度亦为Ω(nlgn)。 同步的下界不可能从异步的下界导出 因为上节中的算法表明：同步模型中的附加假定是必不可少的。 同步的下界对于非均匀和均匀算法均成立，但异步的下界只对均匀算法成立。 但是从同步导出的异步结果是正确的，并且提供了一个非均匀算法的异步下界。 基于比较的算法的概念和定义 为了得到下界，假定所有处理器在同一轮开始执行 一个环是由结点表按顺时针方向指定的，结点表开始于最小标识符。 在同步模型里，算法的容许执行完全由初始配置定义，这是因为msg延迟及节点步骤的相对次序均无选择的可能。 系统的初始配置完全由环决定，即由节点标识符列表按上述规则来决定。当算法的选择可以从上下文判断清楚时，则将由环R确定的容许执行表示为exec(R). 匹配：若环R1上的结点pi和R2上的pj在各自的环里具有相同的位置，则称pi和pj是匹配的，即：匹配的结点在各自环上距其最小id的结点的距离相同。 基于比较的算法 直观上，若一个算法在两个相对次序相同的环上具有相同的行为，则该算法是基于比较的，形式定义： 1）序相同（order equivalent） 两个环x0, x1,…, xn-1和y0, y1,…,yn-1是(次)序等价的，若对每个i和j，xixj, 当且仅当yiyj。 回忆一下环上的结点pi的k-邻居是2k+1个结点的序列(下标是mod n)： pi-k, …, pi-1, pi, pi+1,…, pi+k 序等价的概念很容易扩展到k-邻居集(所有索引按模n计算) 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终止。 节点的行为相似：若α1里pi和α2里pj在所有的k≥0轮里均相似，则称α1里pi和α2里pj的行为相似。 算法的行为相似：指每对匹配的结点行为相似 3）定义 Def 3.2 一个算法是基于比较的，若对于每对序等价的环R1和R2，每对匹配的节点在exec(R1)和exec(R2)里的行为均相似。 该定义说明，若一算法只与环上标识符之间的相对次序相关，而与具体id值无关，则该算法一定只是基于标识符的比较 2. 基于比较算法的下界 设A是一个基于比较的leader选举算法，证明时考虑的环就序模式而言具有高度的对称性。即：环里存在很多次序等价的邻域。 直观上，只要两个节点有序等价的邻域，它们在A里就有同样的行为。我们将通过在一个高度对称的环里执行A来导出下界。讨论若一结点在某轮里发送一个msg，则具有序等价邻域的所有结点也在同一轮里发送一个msg。 证明的关键是：区别获得信息的轮及没有获得信息的轮. Note：在同步环里，一个结点即使没有收到一个msg也会获得info，例如，在§3.4.1里的非均匀算法中，若第1到第n轮里未接收到msg，实际上蕴含着信息：环里没有标识符为0的结点。 下面的证明关键是观察： 若某一轮r里不存在msg也对于结点pi是有用的(指可获取info)，则仅当存在一个次序等价的不同环，在该环上的第r轮里已接收一个msg 例如，在非均匀算法中，若环上某一个结点的id为0，则在第1, 2, …, n轮里均已收到msg。但对于一个次序等价的不同环(设最小id0)，则它在前n