分布式算法培训资料

《分布式算法培训资料》由会员分享，可在线阅读，更多相关《分布式算法培训资料（77页珍藏版）》请在金锄头文库上搜索。

1、,1,第二部分 分布式算法 黄刘生 中国科学技术大学计算机系 国家高性能计算中心（合肥） 2008.10,2,Ch.1 导论,1.1 分布式系统 Def：一个分布式系统是一个能彼此通信的单个计算装置的集合（计算单元：硬处理器；软进程） 包括：紧耦合系统-如共享内存多处理机 松散系统-cow、Internet 与并行处理的分别(具有更高程度的不确定性和行为的独立性) 并行处理的目标是使用所有处理器来执行一个大任务 而分布式系统中，每个处理器一般都有自己独立的任务，但由于各种原因（为共享资源，可用性和容错等），处理机之间需要协调彼此的动作。 分布式系统无处不在，其作用是： 共享资源 改善性能：并行

2、地解决问题 改善可用性：提高可靠性，以防某些成分发生故障,3,1.1 分布式系统,分布式系统面临的困难 异质性：软硬件环境 异步性：事件发生的绝对、甚至相对时间不可能总是精确地知道 局部性：每个计算实体只有全局情况的一个局部视图 故障：各计算实体会独立地出故障，影响其他计算实体的工作。,5,1.2 分布式计算的理论,否定结果、下界和不可能的结果 常常要证明在一个特定的分布式系统中，某个特定问题的不可解性。 就像NP-完全问题一样，表示我们不应该总花精力去求解这些问题。 当然，可以改变规则，在一种较弱的情况下去求解问题。 我们侧重研究： 可计算性：问题是否可解？ 计算复杂性：求解问题的代价是什么

3、？,6,1.3 理论和实际之关系,主要的分布式系统的种类，分布式计算理论中常用的形式模型之间的关系 种类 支持多任务的OS：互斥，死锁检测和防止等技术在分布式系统中同样存在。 MIMD机器：紧耦合系统，它由分离的硬件运行共同的软件构成。 更松散的分布式系统：由网络（局域、广域等）连接起来的自治主机构成 特点是由分离的硬件运行分离的软件。实体间通过诸如TCP/IP栈、CORBA或某些其它组件或中间件等接口互相作用。,7,1.3 理论和实际之关系,模型 模型太多。这里主要考虑三种，基于通信介质和同步程度考虑。 异步共享存储模型：用于紧耦合机器，通常情况下各处理机的时钟信号不是来源于同一信号源 异步

4、msg传递模型：用于松散耦合机器及广域网 同步msg传递模型：这是一个理想的msg传递系统。该系统中，某些计时信息（如msg延迟上界）是已知的，更实际系统能够模拟同步msg传递模型。 该模型便于设计算法，然后将其翻译成更实际的模型。,8,1.3 理论和实际之关系,错误的种类 Crash failure崩溃错误 指处理机没有任何警告而在某点上停止操作。 Byzantine failure拜占庭错误 一个出错可引起任意的动作,9,Ch.2 消息传递系统中的基本算法,本章介绍无故障的msg传递系统，考虑两个主要的计时模型：同步及异步。 定义主要的复杂性度量、描述伪代码约定，最后介绍几个简单算法 2.

5、1 消息传递系统的形式化模型 2.1.1 系统 1.基本概念 拓扑：无向图 结点处理机 边 双向信道,10,2.1.1 系统,算法：由系统中每个处理器上的局部程序构成 局部程序 执行局部计算本地机器 发送和接收msg邻居 形式地：一个系统或一个算法是由n个处理器p0, p1,pn-1构成，每个处理器pi可以模型化为一个具有状态集Qi的状态机（可能是无限的）,11,2.1.1 系统,状态（进程的局部状态） 由pi的变量，pi的msgs构成。 pi的每个状态由2r个msg集构成： outbufil(1lr): pi经第l条关联的信道发送给邻居，但尚未传到邻居的msg。 inbufil(1lr):

6、在pi的第l条信道上已传递到pi，但尚未经pi内部计算步骤处理的msg。 模拟在信道上传输的msgs,12,2.1.1 系统,初始状态： Qi包含一个特殊的初始状态子集：每个inbufil必须为空，但outbufil未必为空。 转换函数(transition)： 处理器pi的转换函数(实际上是一个局部程序) 输入：pi可访问的状态 输出：对每个信道l ，至多产生一个msg输出 转换函数使输入缓冲区(1lr)清空。,13,2.1.1 系统,配置：配置是分布式系统在某点上整个算法的全局状态 向量=(q0, q1,qn-1), qi是pi的一个状态 一个配置里的outbuf变量的状态表示在通信信道上

7、传输的信息，由del事件模拟传输 一个初始的配置是向量=(q0, q1,qn-1), 其中每个qi是pi的初始状态，即每个处理器处于初始状态,14,2.1.1 系统,事件：系统里所发生的事情均被模型化为事件，对于msg传递系统，有两种： comp(i)计算事件。代表处理器pi的一个计算步骤。其中，pi的转换函数被用于当前可访问状态 del(i,j,m)传递事件，表示msg m从pi传送到pj 执行：系统在时间上的行为被模型化为一个执行。 它是一个由配置和事件交错的序列。该序列须满足各种条件，主要分为两类：,15,2.1.1 系统,Safety条件： (安全性) 表示某个性质在每次执行中每个可到

8、达的配置里都必须成立 在序列的每个有限前缀里必须成立的条件 例如：“在leader选举中，除了pmax外，没有哪个结点宣称自己是leader” 非形式地：安全性条件陈述了“尚未发生坏的情况” “坏事从不发生”,16,2.1.1 系统,liveness条件： (活跃性) 表示某个性质在每次执行中的某些可达配置里必须成立。 必须成立一定次数的条件(可能是无数次) 例如：条件：“p1最终须终止”，要求p1的终止至少发生一次；“leader选举， pmax最终宣布自己是leader” 非形式地，一个活跃条件陈述：“最终某个好的情况发生” 对特定系统，满足所有要求的安全性条件的序列称为一个执行; 若一个

9、执行也满足所有要求的活跃性条件，则称为容许(合法 的)(admissible)执行,17,2.1.1 系统,2.异步系统 异步：msg传递的时间和一个处理器的两个相继步骤之间的时间无固定上界 例如，Internet中，email虽然常常是几秒种到达，但也可能要数天到达。当然msg延迟有上界，但它可能很大，且随时间而改变。 因此异步算法设计时，须使之独立于特殊的计时参数，不能依赖于该上界。 执行片断 一个异步msg传递系统的一个执行片断是一个有限或无限的序列： C0, 1, C1, 2, C2, 3, , (C0不一定是初始配置) 这里Ck是一个配置， k是一个事件。若是有限的，则它须结束于某个

10、配置，且须满足下述条件：,18,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上。(No

11、te:发送send，传递delivery之区别) 即： pi以当前状态(在Ck-1中)为基础按转换函数改变状态并发出msg。,19,2.1.1 系统,执行：一个执行是一个执行片断C0, 1, C1, 2, ,这里C0是一个初始配置。 调度：一个调度(或调度片段)总是和执行(或执行片断)联系在一起的，它是执行中的事件序列：1, 2, 。 并非每个事件序列都是调度。例如，del(1,2,m)不是调度，因为此事件之前，p1没有步骤发送(send)m。 若局部程序是确定的，则执行(或执行片断)就由初始配置C0和调度(或调度片断)唯一确定，可表示为exec(C0 , )。,20,2.1.1 系统,容许执

12、行：(满足活跃性条件) 异步系统中，若某个处理器有无限个计算事件，每个发送的msg都最终被传递，则执行称为容许的。 Note: 无限个计算事件是指处理器没有出错，但它不蕴含处理器的局部程序必须包括一个无限循环 非形式地说：一个算法终止是指在某点后转换函数不改变处理器的状态。 容许的调度： 若它是一个容许执行的调度。,21,2.1.1 系统,3.同步系统 在同步模型中，处理器按锁步骤(lock-step)执行： 执行被划分为轮，每轮里，每个处理器能够发送一个msg到每个邻居，这些msg被传递。每个处理器一接到msg就进行计算。 虽然特殊的分布系统里一般达不到，但这种模型对于设计算法非常方便，因为

13、无需和更多的不确定性打交道。当按此模型设计算法后，能够很容易模拟得到异步算法。 轮：在同步系统中，配置和事件序列可以划分成不相交的轮，每轮由一个传递事件(将outbuf的消息传送到信道上使outbuf变空)，后跟一个计算事件(处理所有传递的msg)组成。,22,2.1.1 系统,容许的执行：指无限的执行。 因为轮的结构，所以 每个处理器执行无限数目的计算步， 每个被发送的msg最终被传递 同步与异步系统的区别 在一个无错的同步系统中，一个算法的执行只取决于初始配置 但在一个异步系统中，对于相同的初始配置及无错假定，因为处理器步骤间隔及消息延迟均不确定，故同一算法可能有不同的执行。,23,2.1

14、.2 复杂性度量,分布式算法的性能：msg个数和时间。 最坏性能、期望性能 终止：假定每个处理器的状态集包括终止状态子集，每个的pi的转换函数对终止状态只能映射到终止状态 当所有处理机均处于终止状态且没有msg在传输时，称系统(算法)已终止。 算法的msg复杂性(最坏情况)：算法在所有容许的执行上发送msg总数的最大值(同步和异步系统),24,2.1.2 复杂性度量,时间复杂度 同步系统：最大轮数，即算法的任何容许执行直到终止的最大轮数。 异步系统：假定任何执行里的msg延迟至多是1个单位的时间，然后计算直到终止的运行时间 计时执行(timed execution) 指：每个事件关联一个非负实

15、数，表示事件发生的时间。时间起始于零，且须是非递减的。但对每个单个的处理器而言是严格增的。 若执行是无限的，则执行的时间是无界的。因此执行中的事件可根据其发生时间来排序 不在同一处理器上的多个事件可以同时发生，在任何有限时间之前只有有限数目的事件发生。,25,2.1.2 复杂性度量,消息的延迟 发送msg的计算事件和处理该msg的计算事件之间所逝去的时间 它主要由msg在发送者的outbuf中的等待时间和在接收者的inbuf中的等待时间所构成。 异步算法的时间复杂性 异步算法的时间复杂性是所有计时容许执行中直到终止的最大时间，其中每个msg延时至多为1。,26,2.1.3 伪代码约定,在形式模

16、型中，一个算法将根据状态转换来描述。但实际上很少这样做，因为这样做难于理解。 实际描述算法有两种方法： 叙述性：对于简单问题 伪码形式：对于复杂问题,27,2.1.3 伪代码约定,异步算法：对每个处理器，用中断驱动来描述异步算法。 在形式模型中，每个计算事件1次处理所有输入缓冲区中的msgs。而在算法中，一般须描述每个msg是如何逐个处理的 异步算法也可在同步系统中工作，因为同步系统是异步系统的一个特例。 一个计算事件中的局部计算的描述类似于顺序算法的伪代码描述。 同步算法：逐轮描述 伪代码约定： 在pi的局部变量中，无须用i做下标，但在讨论和证明中，加上下标i以示区别。 “/”后跟注释,28,2.2 生成树上的广播和汇集,信息收集及分发是许多分布式算法的基础。故通过介绍这两个算法来说明模型、伪码、正确性证明及复杂性度量等概念。 2.2.1 广播(Broadcast) 假定网络的生成树已给定。某处理器pr希望将消息M发送至其余处理器。 假定生成树的根为pr ，