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