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

不指定根构造DFS生成树，和后面的领导者 算法2.2和2.3构造连通网络的生成树时，必需存在一个特殊的结点作为启动者(Leader)。当这样的特殊结点不存在时，如何构造网络的一棵生成树？但本节算法须假定：各结点的标识符唯一，不妨设是自然数，§3.2仍需此假定。 基本思想 每个结点均可自发唤醒，试图构造一棵以自己为根的DFS生成树。若两棵DFS树试图链接同一节点(未必同时)时，该节点将加入根的id较大的DFS树。 为了实现上述思想，须做： 每个结点设置一个leader变量，其初值为0，当Pi唤醒自己时，leaderi=idi； 不指定根构造DFS生成树，和后面的领导者 选举问题一样，都是破对称问题。

§2.5 不指定根时构造DFS生成树 当一结点自发唤醒时，它将自己的id(leader)发送给某一邻居； 当一结点Pi收到来自邻居Pj的标识符y时，Pi比较y和leaderi： ①若y>leaderi，则y可能是具有最大标识符结点的DFS子树的标记。因此，将leaderi置为y，并令Pj是Pi的双亲。从Pi开始继续生成标记为y的DFS树。Note：要修改原Pi所在的DFS子树中所有结点的leader。

§2.5 不指定根时构造DFS生成树 若y<leaderi，则标记为y的DFS树中最大id(y)小于目前所看到的最大标识符。此时无须发送msg，停止构造标记为y的DFS。等待最终某个更大的id的leader消息到达标记为y的树中结点时，再将该节点连接到树中。(至少标记为leaderi的msg会到达标记为y的树) 若y=leaderi，则Pi已属于标记y的DFS树中。

§2.5 不指定根时构造DFS生成树 算法 Alg2.4 构造生成树，不指定根 Code for Processor Pi 0≤i≤n-1 Var parent: init nil; leader: init 0; children: int φ; unexplored: init all neighbors of Pi; 1: upon receiving no msg: //wake up spontaneously 2: if parent = nil then { //若非空，则Pi在某子树上，则Pi失去竞选机会 3: leader := id; parent := i;//试图以自己为根构造树 4: Pj∈unexplored; 5: 将Pj从unexplored中删去； 6： send <leader> to pj; }

§2.5 不指定根时构造DFS生成树 想像：有m个人竞选领袖，id是他自身的素质分，不想竞争人的id不参与比较。 7: upon receiving <new-id> from neighbor Pj: 8: if leader<new-id then { //将Pi所在树合并到Pj所在树中 9: leader := new-id; parent := j; //令Pi的双亲为Pj，可能是修改，而非对nil赋值 //并不一定能停止较差的竞选者传播msg 10: unexplored := all the neighbors of Pi except Pj; //重置未访问的邻居集 11: if unexplored ≠φ then { //因为new-id大，使原Pi所在DFS树修改各自id 12： Pk ∈ unexplored; 13: 将Pk从unexplored中删去；

§2.5 不指定根时构造DFS生成树 14: send <leader> to PK; 15: }else send <parent> to parent; // unexplored =φ }else // leader≥new-id 16: if leader=new-id then send <already> to Pj; //表示自己已经传出过此录像带，无需重传。已在同一树中 //若leader>new-id，则new-id所在DFS停止构造 //以前收到的竞选者优于new-id，不传送，使之停止传播。 17: upon receiving <parent> or <already> from neighbor Pj: 18: if received <parent> then add j to children; 19: if unexplored=φ then { //无尚未访问的邻居 20: if parent≠i then send <parent> to parent //返回 21: else terminates as root of the DFS tree; //根终止 22: }else { //有尚未访问的邻居

§2.5 不指定根时构造DFS生成树 分析： 23: Pk ∈ unexplored; 24: 将Pk从unexplored中删去； 25: send <leader> to Pk; } 分析： 只有生成树的根显式地终止，其它结点没有终止，始终在等待msg。但可修改此算法，使用Alg2.1从根结点发送终止msg 正确性 该算法比前面的算法更复杂，这里只给出粗略的证明。 设Pm是所有自发唤醒结点中标识符最大者，其标识符为idm。消息idm总是被传播，而一旦一个结点收到idm，则该节点(Pm除外)上所有msgs被忽略。因为消息idm的处理和Alg2.3求DFS树一致，因此产生的parent和children变量的设置是正确的。因此有：

§2.5 不指定根时构造DFS生成树 Lemma2.12 设Pm是所有自发唤醒结点中具有最大标识符的结点。在异步模型的每次容许执行里，算法2.4构造根为Pm的一棵DFS树。 Note：因为在容许执行中，网络里的所有自发唤醒结点中最大标识符结点最终会自发启动，故建立的DFS树的根是Pm 可通过广播算法从Pm发出终止msg，即使不广播，所有非Pm结点最终也会因为收到Pm的标识符而停止。因此，不可能构造一棵根不是Pm的生成树。 Lemma2.13 在异步模型的每个容许执行里，只有一个处理器终止作为一生成树的根。

§2.5 不指定根时构造DFS生成树 复杂性 定理：对于一个具有m条边和n个节点的网络，自发启动的节点共有p个，其中ID值最大者的启动时间为t，则算法的消息复杂度为O(pn2)，时间复杂度为O(t+m)。 消息复杂性：简单地分析，最坏情况下，每个处理器均试图以自己为根构造一棵DFS树。因此，Alg2.4的msg复杂性至多是Alg2.3的n倍：O(m*n) 时间复杂性：类似于Alg2.3的msg复杂性O(m)。

§2.5 不指定根时构造DFS生成树 Ex. 2.1 分析在同步和异步模型下，convergecast算法的时间复杂性。 2.2 证明在引理2.6中，一个处理器在图G中是从Pr可达的，当且仅当它的parent变量曾被赋过值 2.3 证明Alg2.3构造一棵以Pr为根的DFS树。 2.4 证明Alg2.3的时间复杂性为O(m)。 2.5 修改Alg2.3获得一新算法，使构造DFS树的时间复杂性为O(n)，并证明。 补充 § 2.6 小结

最小生成树 1、最小生成树性质 用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质： 设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权c[u][v]最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。

最小生成树 2、Prim算法 设G=(V,E)是连通带权图，V={1,2,…,n}。 构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。 在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

最小生成树 利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。 例如，对于右图中的带权图，按Prim算法选取边的过程如下页图所示。

最小生成树

最小生成树 在上述Prim算法中，还应当考虑如何有效地找出满足条件iS,jV-S，且权c[i][j]最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。 在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closest[j］)，最后将j添加到S中，并对closest和lowcost作必要的修改。 用这个办法实现的Prim算法所需的计算时间为

最小生成树 3、Kruskal算法 Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。

最小生成树 例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。

最小生成树 关于集合的一些基本运算可用于实现Kruskal算法。 按权的递增顺序查看等价于对优先队列执行removeMin运算。可以用堆实现这个优先队列。 对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型并查集UnionFind所支持的基本运算。 当图的边数为e时，Kruskal算法所需的计算时间是 。当 时，Kruskal算法比Prim算法差，但当 时，Kruskal算法却比Prim算法好得多。

§补充 构造最小生成树 考虑每个信道都有权重，代表了信道的通信成本，这样最小生成树能够使得执行广播算法总开销最小。 假设每个信道的权重都已存储在其两端的节点的局部内存中。 基本思想： 每个节点都有一个所属树的变量编号，用来判断两个节点是否属于一棵树。刚开始时，每个节点独立成一棵树，其ID值为树的编号，每棵树并发的搜索自己权值最小的出边，并把这些边加入到生成森林中，同时几棵树也就合并为一棵树，取其中编号较大的一个为合并之后的树的编号，更新树中各节点的树编号变量。直至所有的树都被合并为一棵树，此即为最小生成树。

§补充 构造最小生成树 1 Pk Pi 1 1 Pj 1 Pk Pi 1 Pj 可能出现的4个问题： 产生环 可以证明，如果边的权值不相等， 那么图G只有唯一的最小生成树。 利用三元组，将边表述为 {1,i,j},{1,j,k},{1,i,k} 当权相同时，按照i,j,k的字典序来排序 假设i<j<k,则有{1,i,j}<{1,i,k} <{1,j,k} 这样就可以避免出现环 1 Pk Pi 1 1 Pj 1 Pk Pi 1 Pj

§补充 构造最小生成树 可能出现的4个问题： 不平衡 由于异步系统的消息延迟，可能会出现不平衡构造树，从而导致更多的消息。 极端的例子：每次都是一个节点数目很多的树，去合并一个单节点的树，这样对于节点数目大的树来说，每次查找权最小的出边花去的代价太大。 解决办法：给每棵树设置一个level层变量，刚开始时，单节点树的level为0，如果一棵树的权值最小出边所连的另一棵树的level变量大于或等于自己的level变量，则两棵树通过这条边合并，否则等待。所合并的树的level取决于两棵树中level较大者，若两棵树level相同为L，则新合并的树的level=L+1。 (level的含义：好比游戏中的练级)

§补充 构造最小生成树 可能出现的4个问题： 错误判断出边 异步系统中，可能出现在判断一条边是否是出边时，边连接的两点已经处在一棵树当中了，但由于消息延迟导致树编号的更新消息还未传到，因而导致因为两节点的树编号不同而产生的错误。 解决方法： 在合并之前，树中节点按边的权值由小到大的顺序开始探测此边是否是出边，当确认某条边是出边之后便停止探测其他边，并将结果敛播给根节点，由根节点确定通过哪一条边进行合并。 当两棵树合并时，合并后的树的编号以及根节点取level值较大的那棵树的根和树编号。若level值相同，取树编号较大的树的根和树编号。然后由根执行广播操作，更新所有树编号和level值，并通知寻找权值最小的出边。 （确定Pi和Pj是否属于一棵树） ①如果Pi和Pj编号相同，则肯定属于一棵树； ②如果编号不同，但Pj的level和Pi一样大，则肯定不属于一棵树，因为每棵树在一层中不可能有两个树编号，且当Pi在寻找其权值最小的出边的时候，其树编号是最新的； ③如果Pj的树编号与Pi不同且Pj的层数严格小于Pi，那么节点Pj就延迟回答Pi直到他更新到其level值上升到至少和Pi一样大。 (可以证明，这个新增的延迟将不会构成节点间的死锁)

§补充 构造最小生成树 可能出现的4个问题： 存在干扰 不同层的邻接树同时寻找权值最小的出边有可能发生相互干扰。具体来说，当层低的树T合并到层高的树T’，而T’正在确定其权值最小出边时可能会发生此情况。

§补充 构造最小生成树 算法框架： Code for Every Tree T Begin While ( 系统中的子树个数大于1) do (1) 根节点广播ID(T)和level(T)，命令各节点寻找权值最小的边； (2) 按权值由小到大顺序寻找权值最小的出边，找到之后敛播给根节点； (3) 根节点收到所有节点的权值最小出边后，确定整棵树的最小出边e，边e连接树T’。/*level(T)≤level(T’)*/ (4) T’’=T∪T’ ∪e (5) if level(T’)>level(T) then (5.1) ID(T’’)←ID(T’) (5.2) level(T’’)←level(T’) else // level(T’)=level(T) (5.3) ID(T’’)←max{ID(T), ID(T’)} (5.4) level(T’’)←level(T’’)+1 end if end while end

§补充 构造最小生成树 消息复杂度： 每个level为k的树中的节点数至少为2k，level最大为log(n)(n为节点数)。因为每个节点都从边的权值从小到大开始探测此边是否是出边，当确定某边是出边后就停止探测并敛播给根节点，直到根确认这条边是这棵树的最小边，并进行合并操作，并更新level值，然后继续探测。 消息分两类：①每个节点探测自己的一条边是否是出边而得到否认消息，这些消息数目为O(m)；②每一层中在树T中各种消息的传递，其消息数目为O(|T|)，|T|表示树的节点数，此总数目为 故消息总数为O(m+nlogn)

§补充 构造最小生成树 时间复杂度： 系统中所有节点，其所在的树的level值都变成k 时所需的时间为O(kn)，又因为k的最大值为log(n)，所以总时间为O(nlogn)。

§2.6 小结 Introduction to distributed alg 分类： 复杂性： 单源alg：一个启动者。又称centralized alg。 多源alg：任意进程(结点)子集均可是启动者，又称decentralized alg 启动者(initiator)：自发地执行局部算法，即由一内部事件激发其执行 非启动者：由接收一个msg(外部事件)触发其执行局部进程。 复杂性： Msg复杂性：msg总数目 Bit复杂性：发送msg中bit的总数目，当msg在发送过程中其长度随时间增长时

§2.6 小结 时间复杂性 一个分布式算法的时间复杂性是满足下述两个假定的一个计算所耗费的最大时间 T1：一个进程在零时间内可计算任何有限数目的事件 T2：一个msg的发送和接受之间的时间至多为1个时间单位 缺点:针对一算法的所有计算，其结果可能是极不可能发生的计算。 一个分布式算法的one-time复杂性是满足下述假定的一个计算的最大时间 O1：同T1 O2：发送和接收一个msg之间的时间恰好是1个单位时间 缺点：某些计算可能被忽略，而其中可能有极其耗时的计算

§2.6 小结 两种复杂性的折中：α-复杂性 概率分析：msg延迟服从某种概率分布，由此可获得精确的时间复杂性度量 表面上，1-time复杂性至少等于时间复杂性，因为T2假定下的最坏时间不会高于O2假定下的时间。但事实并非如此，而往往O1和O2假定之下的1-time复杂性是前一种时间复杂性的一个下界。 例如：在echo算法里1-time复杂性是O(D)，时间复杂性是Ө(N)，即使直径为1的网络。 两种复杂性的折中：α-复杂性 假定每个msg延迟介于α-1之间(α≤1常数) 对echo 算法α复杂性为O(min(N, D/ α)) 概率分析：msg延迟服从某种概率分布，由此可获得精确的时间复杂性度量

§2.6 小结 基于msg chains的分析 先验知识：邻居的id，全局id等。链路FIFO假定等 任何计算中最长消息链的长度。 链上msgs：m1,m2,…mk序列中，mi因果关系领先于mi+1。 先验知识：邻居的id，全局id等。链路FIFO假定等

下次继续！