《分布式算法》PPT课件.ppt

,1,第二部分 分布式算法汪炀中国科学技术大学计算机系 国家高性能计算中心（合肥）,2,Ch.1 导论,1.1 分布式系统Def：一个分布式系统是一个能彼此通信的单个计算装置的集合（计算单元：硬处理器；软进程）包括：紧耦合系统-如共享内存多处理机 松散系统-cow、Internet与并行处理的分别(具有更高程度的不确定性和行为的独立性)并行处理的目标是使用所有处理器来执行一个大任务而分布式系统中，每个处理器一般都有自己独立的任务，但由于各种原因（为共享资源，可用性和容错等），处理机之间需要协调彼此的动作。分布式系统无处不在，其作用是：共享资源改善性能：并行地解决问题改善可用性：提高可靠性，以防某些成分发生故障,3,1.1 分布式系统分布式系统软件实例简介,ElcomSoft Distributed Password Recovery 是一款俄罗斯安全公司出品的分布式密码暴力破解工具能够利用Nvidia显卡使WPA和WPA2无线密钥破解速度提高100倍还允许数千台计算机联网进行分布式并行计算,4,1.1 分布式系统系统适用范围,ElcomSoft 的密码恢复软件主要是面向Office，包括（Word,Excel,Access,Outlook,Outlook Express,VBA,PowerPoint and Visio)其他的面向微软的产品有（Project,Backup,Mail,Schedule+),archive products(including ZIP,RAR,ACE and ARJ files)等,5,1.1 分布式系统演示界面-支持的文件类型,6,1.1 分布式系统演示主界面,7,1.1 分布式系统最终破解效果,DOC加密的文档，8位数字型密码小于1分钟即可成功解密,8,1.1 分布式系统Agents工作界面,9,1.1 分布式系统NASA SETI寻找外星人计划,SETI(搜寻外星智慧)是一个寻找地球外智慧生命的科学性实验计划，使用射电望远镜来监听太空中的窄频无线电讯号。假设这些讯号中有些不是自然产生的，那么只要我们侦测到这些讯号就可以证明外星科技的存在。射电望远镜讯号主要由噪声(来自天体的发射源与接收者的电子干扰)与像电视转播站、雷达和卫星等等的人工讯号所组成。现代的 Radio SETI 计划会分析这些数字信息。有更强大的运算能力就可以搜寻更广泛的频率范围以及提高灵敏度。因此，Radio SETI 计划对运算能力的需求是永无止尽的。原来的 SETI 项目曾经使用望远镜旁专用的超级计算机来进行大量的数据分析。1995年，David Gedye 提议射电 SETI 使用由全球联网的大量计算机所组成的虚拟超级计算机来进行计算，并创建了 SETIhome 项目来实验这个想法。SETIhome 项目于1999年5月开始运行。,10,1.1 分布式系统NASA SETI寻找外星人计划,11,1.1 分布式系统,分布式系统面临的困难异质性：软硬件环境异步性：事件发生的绝对、甚至相对时间不可能总是精确地知道局部性：每个计算实体只有全局情况的一个局部视图故障：各计算实体会独立地出故障，影响其他计算实体的工作。,12,1.2 分布式计算的理论,目标：针对分布式系统完成类似于顺序式计算中对算法的研究具体：对各种分布式情况发生的问题进行抽象，精确地陈述这些问题，设计和分析有效算法解决这些问题，证明这些算法的最优性。计算模型：通信：计算实体间msg传递还是共享变量？哪些计时信息和行为是可用的？容许哪些错误复杂性度量标准时间，空间通信成本：msg的个数，共享变量的大小及个数故障和非故障的数目,13,1.2 分布式计算的理论,否定结果、下界和不可能的结果 常常要证明在一个特定的分布式系统中，某个特定问题的不可解性。就像NP-完全问题一样，表示我们不应该总花精力去求解这些问题。当然，可以改变规则，在一种较弱的情况下去求解问题。我们侧重研究：可计算性：问题是否可解？计算复杂性：求解问题的代价是什么？,14,1.3 理论和实际之关系,主要的分布式系统的种类，分布式计算理论中常用的形式模型之间的关系种类支持多任务的OS：互斥，死锁检测和防止等技术在分布式系统中同样存在。MIMD机器：紧耦合系统，它由分离的硬件运行共同的软件构成。更松散的分布式系统：由网络（局域、广域等）连接起来的自治主机构成特点是由分离的硬件运行分离的软件。实体间通过诸如TCP/IP栈、CORBA或某些其它组件或中间件等接口互相作用。,15,1.3 理论和实际之关系,模型模型太多。这里主要考虑三种，基于通信介质和同步程度考虑。异步共享存储模型：用于紧耦合机器，通常情况下各处理机的时钟信号不是来源于同一信号源异步msg传递模型：用于松散耦合机器及广域网同步msg传递模型：这是一个理想的msg传递系统。该系统中，某些计时信息（如msg延迟上界）是已知的，系统的执行划分为轮执行，是异步系统的一种特例。该模型便于设计算法，然后将其翻译成更实际的模型。,Dijkstra E W.Co-operating Sequential Process.In programming Language.F.Genyus(ed.).S.I.:Academic Press,1968,43-112;Owicki S,Gries D.Verifying Properties of Parallel Programs:An Axiomatic Approach.Communication ACM 19,5(1976),279-285;,16,1.3 理论和实际之关系,错误的种类初始死进程 指在局部算法中没有执行过一步。Crash failure崩溃错误(损毁模型)指处理机没有任何警告而在某点上停止操作。Byzantine failure拜占庭错误一个出错可引起任意的动作,即执行了与局部算法不一致的任意步。拜占庭错误的进程发送的消息可能包含任意内容。,17,Ch.2 消息传递系统中的基本算法,本章介绍无故障的msg传递系统，考虑两个主要的计时模型：同步及异步。定义主要的复杂性度量、描述伪代码约定，最后介绍几个简单算法2.1 消息传递系统的形式化模型2.1.1 系统1.基本概念拓扑：无向图 结点处理机 边 双向信道,18,2.1.1 系统,算法：由系统中每个处理器上的局部程序构成局部程序 执行局部计算本地机器 发送和接收msg邻居形式地：一个系统或一个算法是由n个处理器p0,p1,pn-1构成，每个处理器pi可以模型化为一个具有状态集Qi的状态机（可能是无限的）,19,2.1.1 系统,状态（进程的局部状态）由pi的变量，pi的msgs构成。pi的每个状态由2r个msg集构成：outbufil(1lr):pi经第l条关联的信道发送给邻居，但尚未传到邻居的msg。inbufil(1lr):在pi的第l条信道上已传递到pi，但尚未经pi内部计算步骤处理的msg。模拟在信道上传输的msgs,20,2.1.1 系统,初始状态：Qi包含一个特殊的初始状态子集：每个inbufil必须为空，但outbufil未必为空。转换函数(transition)：处理器pi的转换函数(实际上是一个局部程序)输入：pi可访问的状态输出：对每个信道l，至多产生一个msg输出转换函数使输入缓冲区(1lr)清空。,21,2.1.1 系统,配置：配置是分布式系统在某点上整个算法的全局状态向量=(q0,q1,qn-1),qi是pi的一个状态一个配置里的outbuf变量的状态表示在通信信道上传输的信息，由del事件模拟传输一个初始的配置是向量=(q0,q1,qn-1),其中每个qi是pi的初始状态，即每个处理器处于初始状态,22,2.1.1 系统,事件：系统里所发生的事情均被模型化为事件，对于msg传递系统，有两种：comp(i)计算事件。代表处理器pi的一个计算步骤。其中，pi的转换函数被用于当前可访问状态del(i,j,m)传递事件，表示msg m从pi传送到pj执行：系统在时间上的行为被模型化为一个执行。它是一个由配置和事件交错的序列。该序列须满足各种条件，主要分为两类：,23,2.1.1 系统,Safety条件：(安全性)表示某个性质在每次执行中每个可到达的配置里都必须成立在序列的每个有限前缀里必须成立的条件例如：“在leader选举中，除了pmax外，没有哪个结点宣称自己是leader”非形式地：安全性条件陈述了“尚未发生坏的情况”“坏事从不发生”,24,2.1.1 系统,liveness条件：(活跃性)表示某个性质在每次执行中的某些可达配置里必须成立。必须成立一定次数的条件(可能是无数次)例如：条件：“p1最终须终止”，要求p1的终止至少发生一次；“leader选举，pmax最终宣布自己是leader”非形式地，一个活跃条件陈述：“最终某个好的情况发生”对特定系统，满足所有要求的安全性条件的序列称为一个执行;若一个执行也满足所有要求的活跃性条件，则称为容许(合法的)(admissible)执行,25,第二部分 分布式算法汪炀第二次课中国科学技术大学计算机系 国家高性能计算中心（合肥）,26,2.1.1 系统,2.异步系统异步：msg传递的时间和一个处理器的两个相继步骤之间的时间无固定上界例如，Internet中，email虽然常常是几秒种到达，但也可能要数天到达。当然msg延迟有上界，但它可能很大，且随时间而改变。因此异步算法设计时，须使之独立于特殊的计时参数，不能依赖于该上界。执行片断一个异步msg传递系统的一个执行片断是一个有限或无限的序列：C0,1,C1,2,C2,3,(C0不一定是初始配置)这里Ck是一个配置，k是一个事件。若是有限的，则它须结束于某个配置，且须满足下述条件：,27,2.1.1 系统,若k=del(i,j,m)，则m必是Ck-1里的outbufil的一个元素，这里l是pi的信道pi,pj的标号从Ck-1到Ck的唯一变化是将m从Ck-1里的outbufil中删去，并将其加入到Ck里的inbufjh中，h是pj的信道pi,pj的标号。即：传递事件将msg从发送者的输出缓冲区移至接收者的输入缓冲区。若k=comp(i)，则从Ck-1到Ck的变化是改变状态：转换函数在pi的可访问状态(在配置Ck-1里)上进行操作，清空inbufil，(1lr)发送msg：将转换函数指定的消息集合加到Ck里的变量outbufi上。(Note:发送send，传递delivery之区别)即：pi以当前状态(在Ck-1中)为基础按转换函数改变状态并发出msg。,28,2.1.1 系统,执行：一个执行是一个执行片断C0,1,C1,2,这里C0是一个初始配置。调度：一个调度(或调度片段)总是和执行(或执行片断)联系在一起的，它是执行中的事件序列：1,2,。并非每个事件序列都是调度。例如，del(1,2,m)不是调度，因为此事件之前，p1没有步骤发送(send)m。若局部程序是确定的，则执行(或执行片断)就由初始配置C0和调度(或调度片断)唯一确定，可表示为exec(C0,)。,29,2.1.1 系统,容许执行：(满足活跃性条件)异步系统中，若某个处理器有无限个计算事件，每个发送的msg都最终被传递，则执行称为容许的。Note:无限个计算事件是指处理器没有出错，但它不蕴含处理器的局部程序必须包括一个无限循环非形式地说：一个算法终止是指在某点后转换函数不改变处理器的状态。容许的调度：若它是一个容许执行的调度。,30,2.1.1 系统,3.同步系统在同步模型中，处理器按锁步骤(lock-step)执行：执行被划分为轮，每轮里，每个处理器能够发送一个msg到每个邻居，这些msg被传递。每个处理器一接到msg就进行计算。虽然特殊的分布系统里一般达不到，但这种模型对于设计算法非常方便，因为无需和更多的不确定性打交道。当按此模型设计算法后，能够很容易模拟得到异步算法。轮：在同步系统中，配置和事件序列可以划分成不相交的轮，每轮由一个传递事件(将outbuf的消息传送到信道上使outbuf变空)，后跟一个计算事件(处理所有传递的msg)组成。,31,2.1.1 系统,容许的执行：指无限的执行。因为轮的结构，所以每个处理器执行无限数目的计算步，每个被发送的msg最终被传递同步与异步系统的区别在一个无错的同步系统中，一个算法的执行只取决于初始配置但在一个异步系统中，对于相同的初始配置及无错假定，因为处理器步骤间隔及消息延迟均不确定，故同一算法可能有不同的执行。,32,2.1.2 复杂性度量,分布式算法的性能：msg个数和时间。最坏性能、期望性能终止：假定每个处理器的状态集包括终止状态子集，每个的pi的转换函数对终止状态只能映射到终止状态当所有处理机均处于终止状态且没有msg在传输时，称系统(算法)已终止。算法的msg复杂性(最坏情况)：算法在所有容许的执行上发送msg总数的最大值(同步和异步系统),33,2.1.2 复杂性度量,时间复杂度同步系统：最大轮数，即算法的任何容许执行直到终止的最大轮数。异步系统：假定任何执行里的msg延迟至多是1个单位的时间，然后计算直到终止的运行时间计时执行(timed execution)指：每个事件关联一个非负实数，表示事件发生的时间。时间起始于零，且须是非递减的。但对每个单个的处理器而言是严格增的。若执行是无限的，则执行的时间是无界的。因此执行中的事件可根据其发生时间来排序不在同一处理器上的多个事件可以同时发生，在任何有限时间之前只有有限数目的事件发生。,34,2.1.2 复杂性度量,消息的延迟发送msg的计算事件和处理该msg的计算事件之间所逝去的时间它主要由msg在发送者的outbuf中的等待时间和在接收者的inbuf中的等待时间所构成。异步算法的时间复杂性异步算法的时间复杂性是所有计时容许执行中直到终止的最大时间，其中每个msg延时至多为1。,35,2.1.3 伪代码约定,在形式模型中，一个算法将根据状态转换来描述。但实际上很少这样做，因为这样做难于理解。实际描述算法有两种方法：叙述性：对于简单问题 伪码形式：对于复杂问题,36,2.1.3 伪代码约定,异步算法：对每个处理器，用中断驱动来描述异步算法。在形式模型中，每个计算事件1次处理所有输入缓冲区中的msgs。而在算法中，一般须描述每个msg是如何逐个处理的异步算法也可在同步系统中工作，因为同步系统是异步系统的一个特例。一个计算事件中的局部计算的描述类似于顺序算法的伪代码描述。同步算法：逐轮描述伪代码约定：在pi的局部变量中，无须用i做下标，但在讨论和证明中，加上下标i以示区别。“/”后跟注释,37,2.2 生成树上的广播和汇集,信息收集及分发是许多分布式算法的基础。故通过介绍这两个算法来说明模型、伪码、正确性证明及复杂性度量等概念。2.2.1 广播(Broadcast)假定网络的生成树已给定。某处理器pr希望将消息M发送至其余处理器。假定生成树的根为pr，每个处理器有一个信道连接其双亲(pr除外)，有若干个信道连接其孩子。,由于分布式系统中，每个节点并不知道全局拓扑，但某些算法需要在特定结构下才能达到最优，比如广播/敛播在树结构下才能达到消息复杂度最优，因此构造生成树是必要的，是其他算法的基础。,38,2.2.1 广播,根pr发送M给所有孩子。(a)当某结点收到父结点的M时，发送M到自己的所有孩子(b)。,39,2.2.1 广播,1.伪码算法Alg2.1 Broadcast pr:/发动者。假设初始化时M已在传输状态1.upon receiving no msg:/pr发送M后执行终止2.terminate;/将terminated置为true。pi(ir,0i n-1):3.upon receiving M from parent:4.send M to all children;5.terminate;2.用状态转换来分析算法每个处理器pi包含状态变量parenti：表示处理器pi双亲结点的标号或为nil(若i=r)变量childreni：pi的孩子结点标号的集合布尔变量terminatedi：表示pi是否处于终止状态,40,2.2.1 广播,初始状态parent和children的值是形成生成树时确定的所有terminated的值均为假outbufr j,jchildrenr持有消息M，注意j不是信道标号，而是r的邻居号。（任何系统中，均假定各节点标号互不相等）所有其他结点的outbuf变量均为空。comp(i)的结果若对于某个k，M在inbufik里，则M被放到outbufi j 里，jchildreni,41,2.2.1 广播,pi进入终止状态将terminatedi置为true；若i=r且terminatedr为false，则terminatedr立即置为true，否则空操作。该算法对同步及异步系统均正确，且在两模型中，msg和时间复杂度相同。Msg复杂度无论在同步还是异步模型中，msg M在生成树的每条边上恰好发送一次。因此，msg复杂性为n-1。,42,2.2.1 广播,时间复杂性：同步模型：时间由轮来度量。Lemma2.1 在同步模型中，在广播算法的每个容许执行里，树中每个距离pr为t的处理器在第t轮里接收消息M。pf：对距离t使用归纳法。归纳基础：t=1，pr的每个孩子在第1轮里接收来自于pr的消息M归纳假设：假设树上每个距pr为t-11的处理器在第t-1轮里已收到M。归纳步骤：设pi到pr距离为t，设pj是pi的双亲，因pj到pr的距离为t-1，由归纳假设，在第t-1轮pj收到M。由算法描述知，在第t轮里pi收到来自于pj的消息MTh2.2 当生成树高度为d时，存在一个消息复杂度为n-1，时间复杂度为d的同步广播算法,43,2.2.1 广播,异步模型Lemma2.3 在异步模型的广播算法的每个容许执行里，树中每个距离pr为t的处理器至多在时刻t接收消息M。pf：对距离t做归纳。对t=1，初始时，M处在从pr到所有距离为1的处理器pi的传输之中，由异步模型的时间复杂性定义知，pi至多在时刻1收到M。pi 距pr为t的处理器，设pj是pi的双亲，则pj与pr的距离为t-1，由归纳假设知，pj至多在时刻t-1收到M，由算法描述知，pj发送给pi的M至多在t时刻到达。Th2.4 同Th2.2,44,下次继续！,45,第二部分 分布式算法第三次课中国科学技术大学计算机系 国家高性能计算中心（合肥）,46,2.2.2 convergecast(汇集，敛播),与广播问题相反，汇集是从所有结点收集信息至根。为简单起见，先考虑一个特殊的变种问题：假定每个pi开始时有一初值xi，我们希望将这些值中最大者发送至根pr。,47,2.2.2 convergecast(汇集，敛播),算法 每个叶子结点pi发送xi至双亲。/启动者对每个非叶结点pj，设pj有k个孩子pi1,pik，pj等待k个孩子的msg vi1,vi2,vik，当pj收到所有孩子的msg之后将vj=maxxj,vi1,vik发送到pj的双亲。换言之：叶子先启动，每个处理器pi计算以自己为根的子树里的最大值vi，将vi发送给pi的双亲。复杂性Th2.5 当生成树高为d时，存在一个异步的敛播方法，其msg复杂性为n-1，时间复杂度为d。(与Th2.2相同)广播和敛播算法用途：初始化某一信息请求(广播发布)，然后用敛播响应信息至根。,48,2.3 构造生成树,上节算法均假设通信网的生成树已知。本节介绍生成树的构造问题。1.Flooding算法(淹没),算法 设pr是特殊处理器。从pr开始，发送M到其所有邻居。当pi第1次收到消息M（不妨设此msg来自于邻居pj）时，pi发送M到除pj外的所有邻居。,49,2.3 构造生成树,msg复杂性因为每个结点在任一信道上发送M不会多于1次，所以每个信道上M至多被发送两次(使用该信道的每个处理器各1次)。在最坏情况下：M除第1次接收的那些信道外，所有其他信道上M被传送2次。因此，有可能要发送2m-(n-1)个msgs。这里m是系统中信道总数，它可能多达n(n-1)/2。时间复杂性：O(D)D网直径2.构造生成树对于flooding稍事修改即可得到求生成树的方法。,50,2.3 构造生成树,基本思想首先，pr发送M给所有邻居，pr为根当pi从某邻居pj收到的M是第1个来自邻居的msg时，pj是pi的双亲；若pi首次收到的M同时来自多个邻居，则用一个comp事件处理自上一comp事件以来的所有已收到的msgs，故此时，pi可在这些邻居中任选一个邻居pj做双亲。当pi确定双亲是pj时，发送给pj，并向此后收到发来M的处理器发送msg,51,2.3 构造生成树,基本思想因为pi收到pj的M是第1个M，就不可能已收到其他结点的M，当然可能同时收到(说明pi与这些邻居间不是父子关系，或说它们不是生成树中的边)；同时pi将M转发给其余邻居，这些邻居尚未发M给pi，或虽然已发M给pi，但pi尚未收到。pi向那些尚未发M给pi(或已发M但尚未到达pi)的邻居转发M之后，等待这些邻居发回响应msg：或。那些回应的邻居是pi的孩子。当pi发出M的所有接收者均已回应(或)，则pi终止。将parent和children边保留即为生成树。,52,2.3 构造生成树,图示pi若认为pj是其双亲，则pi向pr发出M，而pr仍会向pi发reject，但因为此前pr向pi发出过M，故pi收到M时仍会向pr发reject。(可以改进？),53,2.3 构造生成树,算法：Alg2.2 构造生成树（code for pi 0in-1）初值：parent=nil；集合children和other均为upon receiving no message:if i=r and parent=nil then/根尚未发送M send M to all neighbors;parent:=i;/根的双亲置为自己upon receiving M from neighbor pj:if parent=nil then/pi此前未收到过M，M是pi收到的第1个msg parent:=j;send to pj;/pj是pi的双亲 send M to all neighbors except pj;else/pj不可能是pi的双亲，pi收到的M不是第1个msg send to pj;upon receiving from neighbor pj:children:=children j;/pj是pi的孩子，将j加入孩子集 if childrenother 包含了除parent外的所有邻居 then terminate;upon receiving from neighbor pj:other:=other j;/将j加入other，通过非树边发送的msg。if childrenother包含了除pi的双亲外的所有邻居 then terminate;,54,2.3 构造生成树,分析Lemma2.6 在异步模型的每个容许执行中，算法2.2构造一棵根为pr的生成树。(正确性)Pf：算法代码告诉我们两个重要事实一旦处理器设置了parent变量，它绝不改变，即它只有一个双亲处理器的孩子集合决不会减小。因此，最终由parent和children确定的图结构G是静止的，且parent和children变量在不同结点上是一致的，即若pj是pi的孩子，则pi是pj的双亲。下述证明结果图G是根为pr的有向生成树。,55,2.3 构造生成树,为何从根能到达每一结点？(连通)反证：假设某结点在G中从pr不可达，因网络是连通的，若存在两个相邻的结点pi和pj使得pj在G中是从pr可达的(以下简称pj可达)，但pi不可达。因为G里一结点从pr可达当且仅当它曾设置过自己的parent变量(Ex2.4证明)，所以pi的parent变量在整个执行中仍为nil，而pj在某点上已设置过自己的parent变量，于是pj发送M到pi(line9)，因该执行是容许的，此msg必定最终被pi接收，使pi将自己的parent变量设置为j。矛盾！,56,2.3 构造生成树,为何无环？(无环)假设有一环，pi1,pikpi1，若pi是pj的孩子，则pi在pj第1次收到M之后第1次收到M。因每个处理器在该环上是下一处理器的双亲，这就意味着pi1在pi1第1次接收M之前第1次接收M。矛盾！复杂性显然，此方法与淹没算法相比，增加了msg复杂性，但只是一个常数因子。在异步通信模型里，易看到在时刻t，消息M到达所有与pr距离小于等于t的结点。因此有：Th2.7 对于具有m条边和直径D的网络，给定一特殊结点，存在一个msg复杂性为O(m)，时间复杂性为O(D)的异步算法找到该网络的一棵生成树。,57,2.3 构造生成树,Alg2.2在同步模型下仍可工作。其分析类似于异步情形。然而，与异步不同的是，它所构造的生成树一定是一棵广度优先搜索(BFS)树。Lemma2.8 在同步模型下，Alg2.2的每次容许执行均构造一棵根为pr的BFS树。Pf：对轮t进行归纳。即要证明：在第t轮开始时刻 根据parent变量构造的图G是一棵包括所有与pr距离至多为t-1结点的BFS树；而传输中的消息M仅来自于与pr距离恰为t-1的结点。由此构造的树是一棵根为pr的BFS,58,2.3 构造生成树,当t=1时，所有parent初值为nil，M从pr传出。假设引理对第t-11轮为真，在该轮里，从距离 t-2的结点传出的M被接收，任何接收M的结点与pr的距离不超过t-1(恰为t-1或更短)，那些parent值非空的接收结点显然与pr的距离不超过t-2，他们既不改变parent的值也不转发M；而与pr距离为t-1的结点在t-1轮里收到M，因为它们的parent为nil，故将其置为合适的双亲并转发M。距离pr大于t-1的结点不会收到M，因此也不会转发M。因此有如下定理：Th2.9 对于具有m条边直径为D的网络，给定一个特殊结点，存在一个同步算法在msg复杂性为O(m)，时间复杂性为O(D)内找到一棵BFS树。,59,2.3 构造生成树,异步系统里，Alg2.2能构造BFS树？例如，考虑5个顶点的完全连通图,P0为根，假定M消息按P0到p1，P1到P2，P2到P3，P3到P4的次序快速传播，而M在其它路径上传播较慢。结果生成树是从P0到P4的链，它不是BFS树虽然此图直径D=1，生成树的高度d=4，但是算法的运行时间仍然为O(D)而不是O(d)。理解：P0到P4的M在1个时间内到达，即P0-P1-P2-P3-P4的时间之和不超过1。,60,2.3 构造生成树,信息的请求和收集将算法2.2(求生成树)和汇集算法组合即可完成。组合算法的时间复杂性在同步和异步模型中不同,设网是完全图求生成树算法：同步和异步均为 消息复杂性O(m)时间复杂性O(D)汇集算法：同步和异步均有 msg n-1 time d/生成树高组合算法 同步：组合算法的msg复杂性O(m+n)；BFS树中，d=1，dD，故时间复杂性O(D+d)=O(D)=O(1)。异步：组合算法的msg复杂性O(m+n)；生成树高 d=n-1，所以时间复杂性O(D+d)=O(d)=O(n)。1-time复杂性的组合算法T(n)=O(D)。,61,2.4 构造DFS生成树(指定根),构造DFS树时每次加一个结点，而不像Alg2.2那样，试图在树上同时增加同一层的所有结点。Alg2.3 构造DFS生成树，为Pr为根Code for processor Pi,0i n-1varparent:init nil;children:init;unexplored:init all the neighbors of Pi/未访问过的邻居集1:upon receiving no msg:2:if(i=r)and(parent=nil)then/当Pi为根且未发送M时3:parent:=i;/将parent置为自身的标号4:Pj unexplored;5:将Pj从unexplored中删去;/若Pr是孤立结点,4-6应稍作修改6:send M to Pj;/endif,62,2.4 构造DFS生成树(指定根),7:upon receiving M from neighbor Pj:8:if parent=nil then/Pi此前未收到M9:parent:=j;/Pj是Pi的父亲10:从unexplored中删Pj11:if unexplored then 12:Pk unexplored;13:将Pk从unexplored中删去；14:send M to Pk;15:else send to parent;/当Pi的邻居均已访问过，返回到父亲16:else send to Pj;/当Pi已访问过时,63,2.4 构造DFS生成树(指定根),17:upon receiving or from neighbor Pj:18:if received then add j to children;/Pj是Pi的孩子19:if unexplored=then/Pi的邻居均已访问20:if parent i then send to parent;/Pi非根，返回至双亲21:terminate;/以Pi为根的DFS子树已构造好！22:else/选择Pi的未访问过的邻居访问之23:Pk unexplored;24:将Pk从unexplored中删去；25:send M to Pk;,64,2.4 构造DFS生成树(指定根),引理2.10 在异步模型里的每个容许执行，Alg2.3构造一棵以Pr为根的DFS树。证明留作练习。Th2.11 对于一个具有m条边，n个结点的网络，以及给定的特殊顶点，存在一个时间复杂性和消息复杂性均为O(m)的异步算法找到一棵DFS树。Pf：每个结点在其邻接边上至多发送M一次，每个结点至多生成一个msg(或)作为对每个邻接边上收到的M的响应。因此Alg2.3至多发送4m个消息(其实大部分没有4倍)，即算法的msg复杂性为O(m)。时间复杂性证明留作练习。如何改进使msg的复杂性不是4m？注意：上述算法msg复杂性较好，但时间复杂性太差。可降至O(n)。,65,下次继续！,66,第二部分 分布式算法第四次课,中国科学技术大学计算机系 国家高性能计算中心（合肥）,67,2.5 不指定根时构造DFS生成树,算法2.2和2.3构造连通网络的生成树时，必需存在一个特殊的结点作为启动者(Leader)。当这样的特殊结点不存在时，如何构造网络的一棵生成树？但本节算法须假定：各结点的标识符唯一，不妨设是自然数，3.2仍需此假定。基本思想每个结点均可自发唤醒，试图构造一棵以自己为根的DFS生成树。若两棵DFS树试图链接同一节点(未必同时)时，该节点将加入根的id较大的DFS树。为了实现上述思想，须做：每个结点设置一个leader变量，其初值为0，当Pi唤醒自己时，leaderi=idi；,不指定根构造DFS生成树，和后面的领导者选举问题一样，都是破对称问题。,68,2.5 不指定根时构造DFS生成树,当一结点自发唤醒时，它将自己的id(leader)发送给某一邻居；当一结点Pi收到来自邻居Pj的标识符y时，Pi比较y和leaderi：,若yleaderi，则y可能是具有最大标识符结点的DFS子树的标记。因此，将leaderi置为y，并令Pj是Pi的双亲。从Pi开始继续生成标记为y的DFS树。Note：要修改原Pi所在的DFS子树中所有结点的leader。,69,2.5 不指定根时构造DFS生成树,若yleaderi，则标记为y的DFS树中最大id(y)小于目前所看到的最大标识符。此时无须发送msg，停止构造标记为y的DFS。等待最终某个更大的id的leader消息到达标记为y的树中结点时，再将该节点连接到树中。(至少标记为leaderi的msg会到达标记为y的树)若y=leaderi，则Pi已属于标记y的DFS树中。,70,2.5 不指定根时构造DFS生成树,算法Alg2.4 构造生成树，不指定根 Code for Processor Pi 0in-1Var parent:init nil;leader:init 0;children:int;unexplored:init all neighbors of Pi;1:upon receiving no msg:/wake up spontaneously2:if parent=nil then/若非空，则Pi在某子树上，则Pi失去竞选机会3:leader:=id;parent:=i;/试图以自己为根构造树4:Pjunexplored;5:将Pj从unexplored中删去；6：send to pj;,71,2.5 不指定根时构造DFS生成树,想像：有m个人竞选领袖，id是他自身的素质分，不想竞争人的id不参与比较。竞争规则：将自己的id(如讲演片)传递给一个熟悉的人，由他再传给另一人(一次只能送一人。)7:upon receiving from neighbor Pj:8:if leadernew-id then/将Pi所在树合并到Pj所在树中9:leader:=new-id;parent:=j;/令Pi的双亲为Pj，可能是修改，而非对nil赋值/并不一定能停止较差的竞选者传播msg10:unexplored:=all the neighbors of Pi except Pj;/重置未访问的邻居集11:if unexplored then/因为new-id大，使原Pi所在DFS树修改各自id12：Pk unexplored;13:将Pk从unexplored中删去；,72,2.5 不指定根时构造DFS生成树,14:send 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停止构造/以前收到的竞选者优于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/有尚未访问的邻居,73,2.5 不指定根时构造DFS生成树,23:Pk unexplored;24:将Pk从unexplored中删去；25:send to Pk;分析：只有生成树的根显式地终止，其它结点没有终止，始终在等待msg。但可修改此算法，使用Alg2.1从根结点发送终止msg正确性该算法比前面的算法更复杂，这里只给出粗略的证明。设Pm是所有自发唤醒结点中标识符最大者，其标识符为idm。消息idm总是被传播，而一旦一个结点收到idm，则该节点(Pm除外)上所有msgs被忽略。因为消息idm的处理和Alg2.3求DFS树一致，因此产生的parent和children变量的设置是正确的。因此有：,74,2.5 不指定根时构造DFS生成树,Lemma2.12 设Pm是所有自发唤醒结点中具有最大标识符的结点。在异步模型的每次容许执行里，算法2.4构造根为Pm的一棵DFS树。Note：因为在容许执行中，网络里的所有自发唤醒结点中最大标识符结点最终会自发启动，故建立的DFS树的根是Pm可通过广播算法从Pm发出终止msg，即使不广播，所有非Pm结点最终也会因为收到Pm的标识符而停止。因此，不可能构造一棵根不是Pm的生成树。Lemma2.13 在异步模型的每个容许执行里，只有一个处理器终止作为一生成树的根。,