《分布式算法课件》由会员分享，可在线阅读，更多相关《分布式算法课件（24页珍藏版）》请在金锄头文库上搜索。
1、第二部分 分布式算法第四次课中国科学技术大学计算机系国家高性能计算中心（合肥）12.5 不指定根时时构造DFS生成树树算法2.2和2.3构造连通网络的生成树时，必需存在 一个特殊的结点作为启动者(Leader)。当这样的特殊结 点不存在时，如何构造网络的一棵生成树？但本节算法 须假定：各结点的标识符唯一，不妨设是自然数，3.2 仍需此假定。n 基本思想v每个结点均可自发唤醒，试图构造一棵以自己为根 的DFS生成树。若两棵DFS树试图链接同一节点(未 必同时)时，该节点将加入根的id较大的DFS树。 v为了实现上述思想，须做：每个结点设置一个leader变量，其初值为0，当Pi 唤醒自己时，le
2、aderi=idi；不指定根构造DFS生成树，和后面的领导者 选举问题一样，都是破对称问题。22.5 不指定根时时构造DFS生成树树当一结点自发唤醒时，它将自己的id(leader)发送 给某一邻居； 当一结点Pi收到来自邻居Pj的标识符y时，Pi比较y 和leaderi：若yleaderi，则y可能是具 有最大标识符结点的DFS子 树的标记。因此，将leaderi 置为y，并令Pj是Pi的双亲。 从Pi开始继续生成标记为y的 DFS树。Note：要修改原Pi 所在的DFS子树中所有结点 的leader。32.5 不指定根时时构造DFS生成树树n 若y to pj;52.5 不指定根时时构造D
3、FS生成树树想像：有m个人竞选领袖，id是他自身的素质分，不想竞争人 的id不参与比较。 竞争规则：将自己的id(如讲演片)传递给一个熟悉的人，由他 再传给另一人(一次只能送一人。) 7: upon receiving from neighbor Pj: 8: if leader to PK; 15: else send to parent; / unexplored =else / leadernew-id 16: if leader=new-id then send to Pj; /表示自己已经传出过此录像带，无需重传。已在同一树中 /若leadernew-id，则new-id所在DFS停
4、止构造 /以前收到的竞选者优于new-id，不传送，使之停止传播。17: upon receiving or from neighbor Pj: 18: if received then add j to children; 19: if unexplored= then /无尚未访问的邻居 20: if parenti then send to parent /返回 21: else terminates as root of the DFS tree; /根终止 22: else /有尚未访问的邻居72.5 不指定根时时构造DFS生成树树23: Pk unexplored; 24: 将Pk
5、从unexplored中删去； 25: send to Pk; n 分析： v只有生成树的根显式地终止，其它结点没有终止，始终 在等待msg。但可修改此算法，使用Alg2.1从根结点发 送终止msg v正确性 该算法比前面的算法更复杂，这里只给出粗略的证明。 设Pm是所有自发唤醒结点中标识符最大者，其标识符为 idm。消息idm总是被传播，而一旦一个结点收到idm，则该 节点(Pm除外)上所有msgs被忽略。因为消息idm的处理和 Alg2.3求DFS树一致，因此产生的parent和children变量的 设置是正确的。因此有：82.5 不指定根时时构造DFS生成树树Lemma2.12 设Pm
6、是所有自发唤醒结点中具有最大标 识符的结点。在异步模型的每次容许执行里，算法 2.4构造根为Pm的一棵DFS树。 Note：因为在容许执行中，网络里的所有自发唤醒结 点中最大标识符结点最终会自发启动，故建立的 DFS树的根是Pm 可通过广播算法从Pm发出终止msg，即使不广播， 所有非Pm结点最终也会因为收到Pm的标识符而停 止。因此，不可能构造一棵根不是Pm的生成树。Lemma2.13 在异步模型的每个容许执行里，只有一 个处理器终止作为一生成树的根。 92.5 不指定根时时构造DFS生成树树v复杂性 定理：对于一个具有m条边和n个节点的网络，自 发启动的节点共有p个，其中ID值最大者的启动
7、 时间为t，则算法的消息复杂度为O(pn2)，时间 复杂度为O(t+m)。 消息复杂性：简单地分析，最坏情况下，每个处理 器均试图以自己为根构造一棵DFS树。因此， Alg2.4的msg复杂性至多是Alg2.3的n倍：O(m*n)时间复杂性：类似于Alg2.3的msg复杂性O(m)。102.5 不指定根时时构造DFS生成树树Ex. 2.1 分析在同步和异步模型下，convergecast算法的 时间复杂性。 2.2 证明在引理2.6中，一个处理器在图G中是从Pr可 达的，当且仅当它的parent变量曾被赋过值 2.3 证明Alg2.3构造一棵以Pr为根的DFS树。 2.4 证明Alg2.3的时
8、间复杂性为O(m)。 2.5 修改Alg2.3获得一新算法，使构造DFS树的时间 复杂性为O(n)。补充 2.6 小结11补补充 构造最小生成树树考虑每个信道都有权重，代表了信道的通信成本， 这样最小生成树能够使得执行广播算法总开销最小 。假设每个信道的权重都已存储在其两端的节点的局 部内存中。 基本思想：每个节点都有一个所属树的变量编号，用来判断两 个节点是否属于一棵树。刚开始时，每个节点独立 成一棵树，其ID值为树的编号，每棵树并发的搜索 自己权值最小的出边，并把这些边加入到生成森林 中，同时几棵树也就合并为一棵树，取其中编号较 大的一个为合并之后的树的编号，更新树中各节点 的树编号变量。
9、直至所有的树都被合并为一棵树， 此即为最小生成树。12补补充 构造最小生成树树可能出现的4个问题： n 产生环可以证明，如果边的权值不相等，那么图G只有唯一的最小生成树。利用三元组，将边表述为1,i,j,1,j,k,1,i,k当权相同时，按照i,j,k的字典序来排序假设ilevel(T) then(5.1) ID(T)ID(T)(5.2) level(T)level(T)else / level(T)=level(T) (5.3) ID(T)maxID(T), ID(T)(5.4) level(T)level(T)+1end ifend while end17补补充 构造最小生成树树消息复杂度
10、：每个level为k的树中的节点数至少为2k，level最大为 log(n)(n为节点数)。因为每个节点都从边的权值从小到 大开始探测此边是否是出边，当确定某边是出边后就停止 探测并敛播给根节点，直到根确认这条边是这棵树的最小 边，并进行合并操作，并更新level值，然后继续探测。消息分两类：每个节点探测自己的一条边是否是出边 而得到否认消息，这些消息数目为O(m)；每一层中在 树T中各种消息的传递，其消息数目为O(|T|)，|T|表示树 的节点数，此总数目为故消息总数为O(m+nlogn)18补补充 构造最小生成树树时间复杂度：系统中所有节点，其所在的树的level值都变成k 时所需的时间为
11、O(kn)，又因为k的最大值为 log(n)，所以总时间为O(nlogn)。192.6 小结结Introduction to distributed alg n 分类： v单源alg：一个启动者。又称centralized alg。 v多源alg：任意进程(结点)子集均可是启动者，又称 decentralized alg v启动者(initiator)：自发地执行局部算法，即由一内部事 件激发其执行 v非启动者：由接收一个msg(外部事件)触发其执行局部进 程。 n 复杂性： vMsg复杂性：msg总数目 vBit复杂性：发送msg中bit的总数目，当msg在发送过程 中其长度随时间增长时20
12、2.6 小结结v时间复杂性一个分布式算法的时间复杂性是满足下述两个假定的一个计 算所耗费的最大时间 T1：一个进程在零时间内可计算任何有限数目的事件 T2：一个msg的发送和接受之间的时间至多为1个时间单位 缺点:针对一算法的所有计算，其结果可能是极不可能发生的 计算。一个分布式算法的one-time复杂性是满足下述假定的一个计 算的最大时间 O1：同T1 O2：发送和接收一个msg之间的时间恰好是1个单位时间 缺点：某些计算可能被忽略，而其中可能有极其耗时的计算212.6 小结结表面上，1-time复杂性至少等于时间复杂性，因 为T2假定下的最坏时间不会高于O2假定下的时间 。但事实并非如此，而往往O1和O2假定之下的1- time复杂性是前一种时间复杂性的一个下界。例如：在echo算法里1-time复杂性是O(D)，时 间复杂性是(N)，即使直径为1的网络。n两种复杂性的折中：-复杂性 假定每个msg延迟介于-1之间(1常数) 对echo 算法复杂性为O(min(N, D/ ) n概率分析：msg延迟服从某种概率分布，由此可 获得精确的时间复杂性度量222.6 小结结n基于msg chains的分析 任何计算中最长消息链的长度。链上msgs：m1,m2,mk序列中，mi因果关系 领先于mi+1。n先验知识：邻居的id，全局id等。链路FIFO 假定等23下次继续！24
