算法分析课件分布式算.ppt

第二部分第二部分 分布式算法分布式算法黄刘生黄刘生中国科学技术大学计算机系中国科学技术大学计算机系 国家高性能计算中心（合肥）国家高性能计算中心（合肥）2008.101Ch.1 导论导论1.1 分布式系统分布式系统nDef：一一个个分分布布式式系系统统是是一一个个能能彼彼此此通通信信的的单单个个计计算算装装置置的的集集合（计算单元：硬合（计算单元：硬处理器；软处理器；软进程）进程）包括：紧耦合系统包括：紧耦合系统-如共享内存多处理机如共享内存多处理机 松散系统松散系统-cow、Internetn与与并并行行处处理理的的分分别别(具具有有更更高高程程度度的的不不确确定定性性和和行行为为的的独独立立性性)v并行处理的目标是使用所有处理器来执行一个大任务并行处理的目标是使用所有处理器来执行一个大任务v而而分分布布式式系系统统中中，每每个个处处理理器器一一般般都都有有自自己己独独立立的的任任务务，但但由由于于各各种种原原因因（为为共共享享资资源源，可可用用性性和和容容错错等等），处处理理机之间需要协调彼此的动作。机之间需要协调彼此的动作。n分布式系统无处不在，其作用是：分布式系统无处不在，其作用是：共享资源共享资源改善性能：并行地解决问题改善性能：并行地解决问题改善可用性：提高可靠性，以防某些成分发生故障改善可用性：提高可靠性，以防某些成分发生故障21.1 分布式系统分布式系统n分布式系统面临的困难分布式系统面临的困难v异质性：异质性：软硬件环境软硬件环境v异步性：异步性：事件发生的绝对、甚至相对时间不可能事件发生的绝对、甚至相对时间不可能总是精确地知道总是精确地知道v局部性：局部性：每个计算实体只有全局情况的一个局部每个计算实体只有全局情况的一个局部视图视图v故障：故障：各计算实体会独立地出故障，影响其他计各计算实体会独立地出故障，影响其他计算实体的工作。算实体的工作。31.2 分布式计算的理论分布式计算的理论n目标：目标：针对分布式系统完成类似于顺序式计算中对算法的研究针对分布式系统完成类似于顺序式计算中对算法的研究v具体：具体：对各种分布式情况发生的对各种分布式情况发生的问题进行抽象问题进行抽象，精确地陈述精确地陈述这些问题这些问题，设计和分析有效算法解决这些问题设计和分析有效算法解决这些问题，证明这些算证明这些算法的最优性法的最优性。n计算模型：计算模型：v通信：通信：计算实体间计算实体间msg传递还是共享变量？传递还是共享变量？v哪些计时信息和行为是可用的？哪些计时信息和行为是可用的？v容许哪些错误容许哪些错误n复杂性度量标准复杂性度量标准v时间，空间时间，空间v通信成本：通信成本：msg的个数，共享变量的大小及个数的个数，共享变量的大小及个数v故障和非故障的数目故障和非故障的数目41.2 分布式计算的理论分布式计算的理论n否定结果、下界和不可能的结果否定结果、下界和不可能的结果 常常要证明在一个特定的分布式系统中，某个特定问常常要证明在一个特定的分布式系统中，某个特定问题的不可解性。题的不可解性。就像就像NP-完全问题一样，表示我们不应该总花精力去完全问题一样，表示我们不应该总花精力去求解这些问题。求解这些问题。当然，可以改变规则，在一种较弱的情况下去求解问当然，可以改变规则，在一种较弱的情况下去求解问题。题。n我们侧重研究：我们侧重研究：v可计算性：可计算性：问题是否可解？问题是否可解？v计算复杂性：计算复杂性：求解问题的代价是什么？求解问题的代价是什么？51.3 理论和实际之关系理论和实际之关系主主要要的的分分布布式式系系统统的的种种类类，分分布布式式计计算算理理论论中中常常用用的形式模型之间的关系的形式模型之间的关系n种类种类v支支持持多多任任务务的的OS：互互斥斥，死死锁锁检检测测和和防防止止等等技技术术在在分分布布式系统中同样存在。式系统中同样存在。vMIMD机机器器：紧紧耦耦合合系系统统，它它由由分分离离的的硬硬件件运运行行共共同同的的软软件件构成。构成。v更更松松散散的的分分布布式式系系统统：由由网网络络（局局域域、广广域域等等）连连接接起起来来的自治主机构成的自治主机构成特特点点是是由由分分离离的的硬硬件件运运行行分分离离的的软软件件。实实体体间间通通过过诸诸如如TCP/IP栈栈、CORBA或或某某些些其其它它组组件件或或中中间间件件等等接接口口互互相相作用。作用。61.3 理论和实际之关系理论和实际之关系n模型模型模模型型太太多多。这这里里主主要要考考虑虑三三种种，基基于于通通信信介介质质和和同同步程度步程度考虑。考虑。异异步步共共享享存存储储模模型型：用用于于紧紧耦耦合合机机器器，通通常常情情况况下下各各处处理理机的时钟信号不是来源于同一信号源机的时钟信号不是来源于同一信号源异步异步msg传递模型：传递模型：用于松散耦合机器及广域网用于松散耦合机器及广域网同同步步msg传传递递模模型型：这这是是一一个个理理想想的的msg传传递递系系统统。该该系系统统中中，某某些些计计时时信信息息（如如msg延延迟迟上上界界）是是已已知知的的，更更实实际系统能够模拟同步际系统能够模拟同步msg传递模型。传递模型。该该模模型型便便于于设设计计算算法法，然然后后将将其其翻翻译译成成更更实实际际的的模模型。型。71.3 理论和实际之关系理论和实际之关系n错误的种类错误的种类vCrash failure崩溃错误崩溃错误指处理机没有任何警告而在某点上停止操作。指处理机没有任何警告而在某点上停止操作。vByzantine failure拜占庭错误拜占庭错误一个出错可引起任意的动作一个出错可引起任意的动作8Ch.2 消息传递系统中的基本算法消息传递系统中的基本算法本本章章介介绍绍无无故故障障的的msg传传递递系系统统，考考虑虑两两个个主主要要的的计时计时模型：同步及异步。模型：同步及异步。定定义义主主要要的的复复杂杂性性度度量量、描描述述伪伪代代码码约约定定，最最后后介介绍绍几个几个简单简单算法算法2.1 消息传递系统的形式化模型消息传递系统的形式化模型2.1.1 系统系统1.基本概念基本概念n拓扑：拓扑：无向图无向图 结点结点处理机处理机 边边 双向信道双向信道92.1.1 系统系统n算法：由系统中每个处理器上的局部程序构算法：由系统中每个处理器上的局部程序构成成v局部程序局部程序 执行局部计算执行局部计算本地机器本地机器 发送和接收发送和接收msg邻居邻居v形式地：形式地：一个系统或一个算法是由一个系统或一个算法是由n个处理器个处理器p0,p1,pn-1构成，每个处理器构成，每个处理器pi可以模型化为一个可以模型化为一个具有状态集具有状态集Qi的状态机（可能是无限的）的状态机（可能是无限的）102.1.1 系统系统n状态（进程的局部状态）状态（进程的局部状态）由由pi的变量，的变量，pi的的msgs构成。构成。pi的每个状态由的每个状态由2r个个msg集构成：集构成：voutbufill(1llr):pi经经第第ll条条关关联联的的信信道道发发送送给给邻邻居，但尚未传到邻居的居，但尚未传到邻居的msg。vinbufill(1llr):在在pi的的第第ll条条信信道道上上已已传传递递到到pi，但尚未经，但尚未经pi内部计算步骤处理的内部计算步骤处理的msg。模拟在信道上传输的模拟在信道上传输的msgs 112.1.1 系统系统n初始状态：初始状态：vQi包含一个特殊的初始状态子集：每个包含一个特殊的初始状态子集：每个inbufill必必须为空，但须为空，但outbufill未必为空。未必为空。n转换函数转换函数(transition)：处理器处理器pi的转换函数的转换函数(实际上是一个局部程序实际上是一个局部程序)v输入：输入：pi可访问的状态可访问的状态v输出：输出：对每个信道对每个信道ll，至多产生一个，至多产生一个msg输出输出v转换函数使输入缓冲区转换函数使输入缓冲区(1llr)清空。清空。122.1.1 系统系统n配置：配置：配置是分布式系统在某点上整个算法配置是分布式系统在某点上整个算法的全局状态的全局状态向量向量=(q0,q1,qn-1),qi是是pi的一个状态的一个状态一个配置里的一个配置里的outbuf变量的状态表示在通信信道上变量的状态表示在通信信道上传输的信息，由传输的信息，由del事件模拟传输事件模拟传输一个初始的配置是向量一个初始的配置是向量=(q0,q1,qn-1),其中每个其中每个qi是是pi的初始状态，即每个处理器处于初始状态的初始状态，即每个处理器处于初始状态132.1.1 系统系统n事件：事件：系统里所发生的事情均被模型化为事件，对系统里所发生的事情均被模型化为事件，对于于msg传递系统，有两种：传递系统，有两种：comp(i)计算事件。代表处理器计算事件。代表处理器pi的一个计算步的一个计算步骤。其中，骤。其中，pi的转换函数被用于当前可访问状态的转换函数被用于当前可访问状态del(i,j,m)传递事件，表示传递事件，表示msg m从从pi传送到传送到pjn执行：执行：系统在时间上的行为被模型化为一个执行。系统在时间上的行为被模型化为一个执行。它是一个由配置和事件交错的序列。该序列须满足它是一个由配置和事件交错的序列。该序列须满足各种条件，主要分为两类：各种条件，主要分为两类：142.1.1 系统系统 Safety条件条件：(安全性安全性)表表示示某某个个性性质质在在每每次次执执行行中中每每个个可可到到达达的的配配置置里里都必须成立都必须成立在序列的每个有限前缀里必须成立的条件在序列的每个有限前缀里必须成立的条件例例如如：“在在leader选选举举中中，除除了了pmax外外，没没有有哪哪个结点宣称自己是个结点宣称自己是leader”非非形形式式地地：安安全全性性条条件件陈陈述述了了“尚尚未未发发生生坏坏的的情情况况”“坏事从不发生坏事从不发生”152.1.1 系统系统 liveness条件条件：(活跃性活跃性)表示某个性质在每次执行中的某些可达配置里必须成立。表示某个性质在每次执行中的某些可达配置里必须成立。必须成立一定次数的条件必须成立一定次数的条件(可能是无数次可能是无数次)例例如如：条条件件：“p1最最终终须须终终止止”，要要求求p1的的终终止止至至少少发发生生一次；一次；“leader选举，选举，pmax最终宣布自己是最终宣布自己是leader”非形式地，一个活跃条件陈述：非形式地，一个活跃条件陈述：“最终某个好的情况发生最终某个好的情况发生”对特定系统，满足所有要求的安全性条件的序列称为一个对特定系统，满足所有要求的安全性条件的序列称为一个执行执行;若一个执行也满足所有要求的活跃性条件，则称为若一个执行也满足所有要求的活跃性条件，则称为容许容许(合法合法的的)(admissible)执行执行162.1.1 系统系统2.异步系统异步系统n异异步步：msg传传递递的的时时间间和和一一个个处处理理器器的的两两个个相相继继步步骤骤之之间间的的时间无固定上界时间无固定上界例例如如，Internet中中，email虽虽然然常常常常是是几几秒秒种种到到达达，但但也也可可能能要要数数天天到到达达。当当然然msg延延迟迟有有上上界界，但但它它可可能能很很大大，且且随随时时间而改变。间而改变。因因此此异异步步算算法法设设计计时时，须须使使之之独独立立于于特特殊殊的的计计时时参参数数，不不能能依赖于该上界。依赖于该上界。n执行片断执行片断一一个个异异步步msg传传递递系系统统的的一一个个执执行行片片断断是是一一个个有有限限或或无无限限的序列：的序列：C0,1,C1,2,C2,3,(C0不一定是初始配置不一定是初始配置)这这里里Ck是是一一个个配配置置，k是是一一个个事事件件。若若是是有有限限的的，则则它它须结束于某个配置，且须满足下述条件：须结束于某个配置，且须满足下述条件：172.1.1 系统系统v若若k=del(i,j,m)，则则m必必是是Ck-1里里的的outbufill的的一一个个元元素素，这这里里ll是是pi的信道的信道pi,pj的标号的标号从从Ck-1到到Ck的的唯唯一一变变化化是是将将m从从Ck-1里里的的outbufill中中删删去去，并并将将其加入到其加入到Ck里的里的inbufjh h中，中，h是是pj的信道的信道pi,pj的标号。的标号。即即：传传递递事事件件将将msg从从发发送送者者的的输输出出缓缓冲冲区区移移至至接接收收者者的的输输入入缓冲区。缓冲区。v若若k=comp(i)，则从，则从Ck-1到到Ck的变化是的变化是改改变变状状态态：转转换换函函数数在在pi的的可可访访问问状状态态(在在配配置置Ck-1里里)上上进进行操作，清空行操作，清空inbufill，(1llr)发发送送msg：将将转转换换函函数数指指定定的的消消息息集集合合加加到到Ck里里的的变变量量outbufi上。上。(Note:发送发送send，传递，传递delivery之区别之区别)即即：pi以以当当前前状状态态(在在Ck-1中中)为为基基础础按按转转换换函函数数改改变变状状态态并并发发出出msg。182.1.1 系统系统n执执行行：一一个个执执行行是是一一个个执执行行片片断断C0,1,C1,2,这里这里C0是一个初始配置。是一个初始配置。n调调度度：一一个个调调度度(或或调调度度片片段段)总总是是和和执执行行(或或执执行行片片断断)联联系系在在一一起起的的，它它是是执执行行中中的的事事件件序序列列：1,2,。并并非非每每个个事事件件序序列列都都是是调调度度。例例如如，del(1,2,m)不不是是调度，因为此事件之前，调度，因为此事件之前，p1没有步骤发送没有步骤发送(send)m。若若局局部部程程序序是是确确定定的的，则则执执行行(或或执执行行片片断断)就就由由初初始始配配置置C0和和调调度度(或或调调度度片片断断)唯唯一一确确定定，可可表表示示为为exec(C0,)。192.1.1 系统系统n容许执行：容许执行：(满足活跃性条件满足活跃性条件)异异步步系系统统中中，若若某某个个处处理理器器有有无无限限个个计计算算事事件件，每每个发送的个发送的msg都最终被传递，则执行称为容许的。都最终被传递，则执行称为容许的。Note:无无限限个个计计算算事事件件是是指指处处理理器器没没有有出出错错，但但它它不蕴含处理器的局部程序必须包括一个无限循环不蕴含处理器的局部程序必须包括一个无限循环非非形形式式地地说说：一一个个算算法法终终止止是是指指在在某某点点后后转转换换函函数数不改变处理器的状态。不改变处理器的状态。n容许的调度：容许的调度：若它是一个容许执行的调度。若它是一个容许执行的调度。202.1.1 系统系统3.同步系统同步系统在同步模型中，处理器按锁步骤在同步模型中，处理器按锁步骤(lock-step)执行：执行：执执行行被被划划分分为为轮轮，每每轮轮里里，每每个个处处理理器器能能够够发发送送一一个个msg到到每每个个邻邻居居，这这些些msg被被传传递递。每每个个处处理理器器一一接接到到msg就进行计算。就进行计算。虽虽然然特特殊殊的的分分布布系系统统里里一一般般达达不不到到，但但这这种种模模型型对对于于设设计计算算法法非非常常方方便便，因因为为无无需需和和更更多多的的不不确确定定性性打打交交道道。当当按按此模型设计算法后，能够很容易模拟得到异步算法。此模型设计算法后，能够很容易模拟得到异步算法。n轮轮：在在同同步步系系统统中中，配配置置和和事事件件序序列列可可以以划划分分成成不不相相交交的的轮轮，每每轮轮由由一一个个传传递递事事件件(将将outbuf的的消消息息传传送送到到信信道道上上使使outbuf变变空空)，后后跟跟一一个个计计算算事事件件(处处理理所所有有传传递递的的msg)组组成。成。212.1.1 系统系统n容许的执行：容许的执行：指无限的执行。指无限的执行。因为轮的结构，所以因为轮的结构，所以每个处理器执行无限数目的计算步，每个处理器执行无限数目的计算步，每个被发送的每个被发送的msg最终被传递最终被传递n同步与异步系统的区别同步与异步系统的区别在一个无错的同步系统中，一个算法的执行只取决在一个无错的同步系统中，一个算法的执行只取决于初始配置于初始配置但在一个异步系统中，对于相同的初始配置及无错但在一个异步系统中，对于相同的初始配置及无错假定，因为处理器步骤间隔及消息延迟均不确定，假定，因为处理器步骤间隔及消息延迟均不确定，故同一算法可能有不同的执行。故同一算法可能有不同的执行。222.1.2 复杂性度量复杂性度量n分布式算法的性能：分布式算法的性能：msg个数和时间。个数和时间。最坏性能、期望性能最坏性能、期望性能n终终止止：假假定定每每个个处处理理器器的的状状态态集集包包括括终终止止状状态态子子集集，每每个个的的pi的的转转换换函函数数对对终终止止状状态态只只能能映映射射到到终终止止状状态态当当所所有有处处理理机机均均处处于于终终止止状状态态且且没没有有msg在在传传输输时时，称系统称系统(算法算法)已终止。已终止。n算算法法的的msg复复杂杂性性(最最坏坏情情况况)：算算法法在在所所有有容容许许的的执行上发送执行上发送msg总数的最大值总数的最大值(同步和异步系统同步和异步系统)232.1.2 复杂性度量复杂性度量n时间复杂度时间复杂度同同步步系系统统：最最大大轮轮数数，即即算算法法的的任任何何容容许许执执行行直直到到终终止止的的最大轮数。最大轮数。异异步步系系统统：假假定定任任何何执执行行里里的的msg延延迟迟至至多多是是1个个单单位位的的时时间，然后计算直到终止的运行时间间，然后计算直到终止的运行时间n计时执行计时执行(timed execution)指指：每每个个事事件件关关联联一一个个非非负负实实数数，表表示示事事件件发发生生的的时时间间。时时间间起起始始于于零零，且且须须是是非非递递减减的的。但但对对每每个个单单个个的的处处理理器器而而言言是严格增的是严格增的。若若执执行行是是无无限限的的，则则执执行行的的时时间间是是无无界界的的。因因此此执执行行中中的的事件可根据其发生时间来排序事件可根据其发生时间来排序不不在在同同一一处处理理器器上上的的多多个个事事件件可可以以同同时时发发生生，在在任任何何有有限限时间之前只有有限数目的事件发生。时间之前只有有限数目的事件发生。242.1.2 复杂性度量复杂性度量n消息的延迟消息的延迟发送发送msg的计算事件和处理该的计算事件和处理该msg的计算事件之间所逝去的计算事件之间所逝去的时间的时间它主要由它主要由msg在发送者的在发送者的outbuf中的等待时间和在接收者中的等待时间和在接收者的的inbuf中的等待时间所构成。中的等待时间所构成。n异步算法的时间复杂性异步算法的时间复杂性异步算法的时间复杂性是所有计时容许执行中直到终止的最异步算法的时间复杂性是所有计时容许执行中直到终止的最大时间，其中每个大时间，其中每个msg延时至多为延时至多为1。252.1.3 伪代码约定伪代码约定在在形形式式模模型型中中，一一个个算算法法将将根根据据状状态态转转换换来来描描述述。但但实实际际上上很很少少这这样样做做，因因为为这这样样做做难于理解。难于理解。实际描述算法有两种方法：实际描述算法有两种方法：叙述性：对于简单问题叙述性：对于简单问题 伪码形式：对于复杂问题伪码形式：对于复杂问题262.1.3 伪代码约定伪代码约定n异步算法：异步算法：对每个处理器，用对每个处理器，用中断驱动中断驱动来描述异步算法。来描述异步算法。在在形形式式模模型型中中，每每个个计计算算事事件件1次次处处理理所所有有输输入入缓缓冲冲区区中中的的msgs。而而在在算算法法中中，一一般般须须描描述述每每个个msg是是如如何何逐逐个个处处理理的的异异步步算算法法也也可可在在同同步步系系统统中中工工作作，因因为为同同步步系系统统是是异异步步系系统统的一个特例。的一个特例。一一个个计计算算事事件件中中的的局局部部计计算算的的描描述述类类似似于于顺顺序序算算法法的的伪伪代代码码描述描述。n同步算法：同步算法：逐轮描述逐轮描述n伪代码约定：伪代码约定：在在pi的的局局部部变变量量中中，无无须须用用i做做下下标标，但但在在讨讨论论和和证证明明中中，加上下标加上下标i以示区别。以示区别。“/”后跟注释后跟注释272.2 生成树上的广播和汇集生成树上的广播和汇集 信信息息收收集集及及分分发发是是许许多多分分布布式式算算法法的的基基础础。故故通通过过介介绍绍这这两两个个算算法法来来说说明明模模型型、伪伪码码、正正确确性性证证明及复杂性度量等概念。明及复杂性度量等概念。2.2.1 广播广播(Broadcast)假假定定网网络络的的生生成成树树已已给给定定。某某处处理理器器pr希希望望将将消息消息M发送至其余处理器。发送至其余处理器。假假定定生生成成树树的的根根为为pr，每每个个处处理理器器有有一一个个信信道道连接其双亲连接其双亲(pr除外除外)，有若干个信道连接其孩子。，有若干个信道连接其孩子。282.2.1 广播广播l根根pr发发送送M给给所所有孩子。有孩子。(a)l当当某某结结点点收收到到父父结结点点的的M时时，发发送送M到到自自己己的所有孩子的所有孩子(b)。292.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.用状态转换来分析算法用状态转换来分析算法n每个处理器每个处理器pi包含状态包含状态变量变量parenti：表示处理器：表示处理器pi双亲结点的标号或为双亲结点的标号或为nil(若若i=r)变量变量childreni：pi的孩子结点标号的集合的孩子结点标号的集合布尔变量布尔变量terminatedi：表示：表示pi是否处于终止状态是否处于终止状态302.2.1 广播广播n初始状态初始状态vparent和和children的值是形成生成树时确定的的值是形成生成树时确定的v所有所有terminated的值均为假的值均为假voutbufr j,jchildrenr持持有有消消息息M，注注意意j不不是是信信道道标标号号，而而是是r的的邻邻居居号号。（任任何何系系统统中中，均假定各节点标号互不相等）均假定各节点标号互不相等）v所有其他结点的所有其他结点的outbuf变量均为空。变量均为空。ncomp(i)的结果的结果若若 对对 于于 某某 个个 k，M在在 inbufik里里，则则 M被被 放放 到到outbufi j 里，里，jchildreni312.2.1 广播广播npi进入终止状态进入终止状态将将terminatedi置置为为true；若若i=r且且terminatedr为为false，则，则terminatedr立即置为立即置为true，否则空操作。，否则空操作。n该该算算法法对对同同步步及及异异步步系系统统均均正正确确，且且在在两两模模型型中，中，msg和时间复杂度相同。和时间复杂度相同。nMsg复杂度复杂度无无论论在在同同步步还还是是异异步步模模型型中中，msg M在在生生成成树树的的每每条边上恰好发送一次。条边上恰好发送一次。因此，因此，msg复杂性为复杂性为n-1。322.2.1 广播广播n时间复杂性：时间复杂性：同步模型：同步模型：时间由轮来度量。时间由轮来度量。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的同步广播算法的同步广播算法332.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.2342.2.2 convergecast(汇集，敛播汇集，敛播)与与广广播播问问题题相相反反，汇汇集集是是从从所所有有结结点点收收集集信信息息至至根根。为简单起见，先考虑一个特殊的变种问题：为简单起见，先考虑一个特殊的变种问题：假假定定每每个个pi开开始始时时有有一一初初值值xi，我我们们希希望望将将这这些些值值中中最大者发送至根最大者发送至根pr。352.2.2 convergecast(汇集，敛播汇集，敛播)n算法算法 每个叶子结点每个叶子结点pi发送发送xi至双亲。至双亲。/启动者启动者对对每每个个非非叶叶结结点点pj，设设pj有有k个个孩孩子子pi1,pik，pj等等待待k个个孩孩子子的的msg vi1,vi2,vik，当当pj收收到到所所有有孩孩子子的的msg之后将之后将vj=maxxj,vi1,vik发送到发送到pj的双亲。的双亲。换换言言之之：叶叶子子先先启启动动，每每个个处处理理器器pi计计算算以以自自己己为为根的子树里的最大值根的子树里的最大值vi，将，将vi发送给发送给pi的双亲。的双亲。n复杂性复杂性Th2.5 当当生生成成树树高高为为d时时，存存在在一一个个异异步步的的敛敛播播方方法法，其其msg复复杂杂性性为为n-1，时时间间复复杂杂度度为为d。(与与Th2.2相相同同)n广广播播和和敛敛播播算算法法用用途途：初初始始化化某某一一信信息息请请求求(广广播播发发布布)，然后用敛播响应信息至根。，然后用敛播响应信息至根。362.3 构造生成构造生成树树上上节节算算法法均均假假设设通通信信网网的的生生成成树树已已知知。本本节节介介绍生成树的构造问题。绍生成树的构造问题。1.Flooding算法算法(淹没淹没)n算法算法 设设pr是是特特殊殊处处理理器器。从从pr开开始始，发发送送M到到其其所所有有邻邻居居。当当pi第第1次次收收到到消消息息M（不不妨妨设设此此msg来来自自于于邻邻居居pj）时时，pi发发送送M到到除除pj外的所有邻居。外的所有邻居。372.3 构造生成构造生成树树nmsg复杂性复杂性因因为为每每个个结结点点在在任任一一信信道道上上发发送送M不不会会多多于于1次次，所所以以每每个个信信道道上上M至至多多被被发发送送两两次次(使使用用该该信信道道的的每个处理器各每个处理器各1次次)。在在最最坏坏情情况况下下：M除除第第1次次接接收收的的那那些些信信道道外外，所所有有其其他他信信道道上上M被被传传送送2次次。因因此此，有有可可能能要要发发送送2m-(n-1)个个msgs。这这里里m是是系系统统中中信信道道总总数数，它它可能多达可能多达n(n-1)/2。n时间复杂性：时间复杂性：O(D)D网直径网直径2.构造生成树构造生成树对于对于flooding稍事修改即可得到求生成树的方法。稍事修改即可得到求生成树的方法。382.3 构造生成构造生成树树基本思想基本思想n首先，首先，pr发送发送M给所有邻居，给所有邻居，pr为根为根n当当pi从从某某邻邻居居pj收收到到的的M是是第第1个个来来自自邻邻居居的的msg时时，pj是是pi的的双双亲亲；若若pi首首次次收收到到的的M同同时时来来自自多多个个邻邻居居，则则用用一一个个comp事事件件处处理理自自上上一一comp事事件件以以来来的的所所有有已已收收到到的的msgs，故故此此时时，pi可可在在这这些些邻邻居居中中任任选选一一个个邻居邻居pj做双亲。做双亲。n当当pi确确定定双双亲亲是是pj时时，发发送送给给pj，并并向向此此后后收收到发来到发来M的处理器发送的处理器发送msg392.3 构造生成构造生成树树基本思想基本思想n因因为为pi收收到到pj的的M是是第第1个个M，就就不不可可能能已已收收到到其其他他结结点点的的M，当当然然可可能能同同时时收收到到(说说明明pi与与这这些些邻邻居居间间不不是是父父子子关关系系，或或说说它它们们不不是是生生成成树树中中的的边边)；同同时时pi将将M转转发发给给其其余余邻邻居居，这这些些邻邻居居尚尚未未发发M给给pi，或或虽虽然然已已发发M给给pi，但，但pi尚未收到尚未收到。npi向向那那些些尚尚未未发发M给给pi(或或已已发发M但但尚尚未未到到达达pi)的的邻邻居居转转发发M之之后后，等等待待这这些些邻邻居居发发回回响响应应msg：或或。那些回应。那些回应的邻居是的邻居是pi的孩子。的孩子。n当当 pi发发 出出 M的的 所所 有有 接接 收收 者者 均均 已已 回回 应应(或或)，则则pi终终止止。将将parent和和children边边保保留留即即为生成树。为生成树。402.3 构造生成构造生成树树图示图示pi若认为若认为pj是其双亲，则是其双亲，则pi向向pr发出发出M，而，而pr仍会向仍会向pi发发reject，但因为此前，但因为此前pr向向pi发出过发出过M，故，故pi收到收到M时时仍会向仍会向pr发发reject。(可以改进？可以改进？)412.3 构造生成构造生成树树算法：算法：Alg2.2 构造生成树（构造生成树（code for pi 0in-1）初值：初值：parent=nil；集合；集合children和和other均为均为1.upon receiving no message:2.if i=r and parent=nil then /根尚未发送根尚未发送M3.send M to all neighbors;4.parent:=i;/根的双亲置为自己根的双亲置为自己5.upon receiving M from neighbor pj:6.if parent=nil then/pi此前未收到过此前未收到过M，M是是pi收到的第收到的第1个个msg7.parent:=j;8.send to pj;/pj是是pi的双亲的双亲9.send M to all neighbors except pj;10.else /pj不可能是不可能是pi的双亲，的双亲，pi收到的收到的M不是第不是第1个个msg10.send to pj;11.upon receiving from neighbor pj:12.children:=children j;/pj是是pi的孩子，将的孩子，将j加入孩子集加入孩子集13.if childrenother 包含了除包含了除parent外的所有邻居外的所有邻居 then terminate;14.upon receiving from neighbor pj:15.other:=other j;/将将j加入加入other，通过非树边发送的，通过非树边发送的msg。16.if childrenother包含了除包含了除pi的双亲外的所有邻居的双亲外的所有邻居 then terminate;422.3 构造生成构造生成树树分析分析Lemma2.6 在异步模型的每个容许执行中，算法在异步模型的每个容许执行中，算法2.2构造一棵根为构造一棵根为pr的生成树。的生成树。(正确性正确性)Pf：算法代码告诉我们两个重要事实：算法代码告诉我们两个重要事实a)一旦处理器设置了一旦处理器设置了parent变量，它绝不改变，即它变量，它绝不改变，即它只有一个双亲只有一个双亲b)处理器的孩子集合决不会减小。处理器的孩子集合决不会减小。因此，最终由因此，最终由parent和和children确定的图结构确定的图结构G是是静止的，且静止的，且parent和和children变量在不同结点上是一变量在不同结点上是一致的，即若致的，即若pj是是pi的孩子，则的孩子，则pi是是pj的双亲。的双亲。下述证明结果图下述证明结果图G是根为是根为pr的有向生成树。的有向生成树。432.3 构造生成构造生成树树n为何从根能到达每一结点？为何从根能到达每一结点？(连通连通)反反证证：假假设设某某结结点点在在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。矛盾！。矛盾！442.3 构造生成构造生成树树n为何无环？为何无环？(无环无环)假假设设有有一一环环，pi1,pikpi1，若若pi是是pj的的孩孩子子，则则pi在在pj第第1次次收收到到M之之后后第第1次次收收到到M。因因每每个个处处理理器器在在该该环环上上是是下下一一处处理理器器的的双双亲亲，这这就就意意味味着着pi1在在pi1第第1次次接接收收M之前第之前第1次接收次接收M。矛盾！。矛盾！n复杂性复杂性显显然然，此此方方法法与与淹淹没没算算法法相相比比，增增加加了了msg复复杂杂性性，但但只只是是一一个个常常数数因因子子。在在异异步步通通信信模模型型里里，易易看看到到在在时时刻刻t，消消息息M到到达达所所有有与与pr距距离离小小于于等等于于t的的结结点点。因因此此有：有：Th2.7 对对于于具具有有m条条边边和和直直径径D的的网网络络，给给定定一一特特殊殊结结点点，存存在在一一个个msg复复杂杂性性为为O(m)，时时间间复复杂杂性性为为O(D)的的异异步算法找到该网络的一棵生成树。步算法找到该网络的一棵生成树。452.3 构造生成构造生成树树Alg2.2在在同同步步模模型型下下仍仍可可工工作作。其其分分析析类类似似于于异异步步情情形形。然然而而，与与异异步步不不同同的的是是，它它所所构构造造的的生生成成树树一定是一棵广度优先搜索一定是一棵广度优先搜索(BFS)树。树。Lemma2.8 在在同同步步模模型型下下，Alg2.2的的每每次次容容许许执执行行均构造一棵根为均构造一棵根为pr的的BFS树。树。Pf：对轮对轮t进行归纳进行归纳。即要证