搜索
1第二部分分布式算法黄刘生中国科学技术大学计算机系国家高性能计算中心（合肥）2008.102Ch.1导论§1.1分布式系统Def：一个分布式系统是一个能彼此通信的单个计算装置的集合（计算单元：硬——处理器；软——进程）包括：紧耦合系统----如共享内存多处理机松散系统-----cow、Internet与并行处理的分别(具有更高程度的不确定性和行为的独立性)并行处理的目标是使用所有处理器来执行一个大任务而分布式系统中，每个处理器一般都有自己独立的任务，但由于各种原因（为共享资源，可用性和容错等），处理机之间需要协调彼此的动作。分布式系统无处不在，其作用是：①共享资源②改善性能：并行地解决问题③改善可用性：提高可靠性，以防某些成分发生故障3§1.1分布式系统分布式系统面临的困难异质性：软硬件环境异步性：事件发生的绝对、甚至相对时间不可能总是精确地知道局部性：每个计算实体只有全局情况的一个局部视图故障：各计算实体会独立地出故障，影响其他计算实体的工作。4§1.2分布式计算的理论目标：针对分布式系统完成类似于顺序式计算中对算法的研究具体：对各种分布式情况发生的问题进行抽象，精确地陈述这些问题，设计和分析有效算法解决这些问题，证明这些算法的最优性。计算模型：通信：计算实体间msg传递还是共享变量？哪些计时信息和行为是可用的？容许哪些错误复杂性度量标准时间，空间通信成本：msg的个数，共享变量的大小及个数故障和非故障的数目5§1.2分布式计算的理论否定结果、下界和不可能的结果常常要证明在一个特定的分布式系统中，某个特定问题的不可解性。就像NP-完全问题一样，表示我们不应该总花精力去求解这些问题。当然，可以改变规则，在一种较弱的情况下去求解问题。我们侧重研究：可计算性：问题是否可解？计算复杂性：求解问题的代价是什么？6§1.3理论和实际之关系主要的分布式系统的种类，分布式计算理论中常用的形式模型之间的关系种类支持多任务的OS：互斥，死锁检测和防止等技术在分布式系统中同样存在。MIMD机器：紧耦合系统，它由分离的硬件运行共同的软件构成。更松散的分布式系统：由网络（局域、广域等）连接起来的自治主机构成特点是由分离的硬件运行分离的软件。实体间通过诸如TCP/IP栈、CORBA或某些其它组件或中间件等接口互相作用。7§1.3理论和实际之关系模型模型太多。这里主要考虑三种，基于通信介质和同步程度考虑。①异步共享存储模型：用于紧耦合机器，通常情况下各处理机的时钟信号不是来源于同一信号源②异步msg传递模型：用于松散耦合机器及广域网③同步msg传递模型：这是一个理想的msg传递系统。该系统中，某些计时信息（如msg延迟上界）是已知的，更实际系统能够模拟同步msg传递模型。该模型便于设计算法，然后将其翻译成更实际的模型。8§1.3理论和实际之关系错误的种类Crashfailure崩溃错误指处理机没有任何警告而在某点上停止操作。Byzantinefailure拜占庭错误一个出错可引起任意的动作9Ch.2消息传递系统中的基本算法本章介绍无故障的msg传递系统，考虑两个主要的计时模型：同步及异步。定义主要的复杂性度量、描述伪代码约定，最后介绍几个简单算法§2.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集构成：outbufi[l](1≤l≤r):pi经第l条关联的信道发送给邻居，但尚未传到邻居的msg。inbufi[l](1≤l≤r):在pi的第l条信道上已传递到pi，但尚未经pi内部计算步骤处理的msg。模拟在信道上传输的msgs12§2.1.1系统初始状态：Qi包含一个特殊的初始状态子集：每个inbufi[l]必须为空，但outbufi[l]未必为空。转换函数(transition)：处理器pi的转换函数(实际上是一个局部程序)输入：pi可访问的状态输出：对每个信道l，至多产生一个msg输出转换函数使输入缓冲区(1≤l≤r)清空。13§2.1.1系统配置：配置是分布式系统在某点上整个算法的全局状态向量=(q0,q1,…qn-1),qi是pi的一个状态一个配置里的outbuf变量的状态表示在通信信道上传输的信息，由del事件模拟传输一个初始的配置是向量=(q0,q1,…qn-1),其中每个qi是pi的初始状态，即每个处理器处于初始状态14§2.1.1系统事件：系统里所发生的事情均被模型化为事件，对于msg传递系统，有两种：comp(i)——计算事件。代表处理器pi的一个计算步骤。其中，pi的转换函数被用于当前可访问状态del(i,j,m)——传递事件，表示msgm从pi传送到pj执行：系统在时间上的行为被模型化为一个执行。它是一个由配置和事件交错的序列。该序列须满足各种条件，主要分为两类：15§2.1.1系统①Safety条件：(安全性)表示某个性质在每次执行中每个可到达的配置里都必须成立在序列的每个有限前缀里必须成立的条件例如：“在leader选举中，除了pmax外，没有哪个结点宣称自己是leader”非形式地：安全性条件陈述了“尚未发生坏的情况”“坏事从不发生”16§2.1.1系统②liveness条件：(活跃性)表示某个性质在每次执行中的某些可达配置里必须成立。必须成立一定次数的条件(可能是无数次)例如：条件：“p1最终须终止”，要求p1的终止至少发生一次；“leader选举，pmax最终宣布自己是leader”非形式地，一个活跃条件陈述：“最终某个好的情况发生”对特定系统，满足所有要求的安全性条件的序列称为一个执行;若一个执行也满足所有要求的活跃性条件，则称为容许(合法的)(admissible)执行17§2.1.1系统2.异步系统异步：msg传递的时间和一个处理器的两个相继步骤之间的时间无固定上界例如，Internet中，email虽然常常是几秒种到达，但也可能要数天到达。当然msg延迟有上界，但它可能很大，且随时间而改变。因此异步算法设计时，须使之独立于特殊的计时参数，不能依赖于该上界。执行片断一个异步msg传递系统的一个执行片断α是一个有限或无限的序列：C0,Φ1,C1,Φ2,C2,Φ3,…,(C0不一定是初始配置)这里Ck是一个配置，Φk是一个事件。若α是有限的，则它须结束于某个配置，且须满足下述条件：18§2.1.1系统若Φk=del(i,j,m)，则m必是Ck-1里的outbufi[l]的一个元素，这里l是pi的信道{pi,pj}的标号从Ck-1到Ck的唯一变化是将m从Ck-1里的outbufi[l]中删去，并将其加入到Ck里的inbufj[h]中，h是pj的信道{pi,pj}的标号。即：传递事件将msg从发送者的输出缓冲区移至接收者的输入缓冲区。若Φk=comp(i)，则从Ck-1到Ck的变化是①改变状态：转换函数在pi的可访问状态(在配置Ck-1里)上进行操作，清空inbufi[l]，(1≤l≤r)②发送msg：将转换函数指定的消息集合加到Ck里的变量outbufi上。(Note:发送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系统容许执行：(满足活跃性条件)异步系统中，若某个处理器有无限个计算事件，每个发送的msg都最终被传递，则执行称为容许的。Note:无限个计算事件是指处理器没有出错，但它不蕴含处理器的局部程序必须包括一个无限循环非形式地说：一个算法终止是指在某点后转换函数不改变处理器的状态。容许的调度：若它是一个容许执行的调度。21§2.1.1系统3.同步系统在同步模型中，处理器按锁步骤(lock-step)执行：执行被划分为轮，每轮里，①每个处理器能够发送一个msg到每个邻居，这些msg被传递。②每个处理器一接到msg就进行计算。虽然特殊的分布系统里一般达不到，但这种模型对于设计算法非常方便，因为无需和更多的不确定性打交道。当按此模型设计算法后，能够很容易模拟得到异步算法。轮：在同步系统中，配置和事件序列可以划分成不相交的轮，每轮由一个传递事件(将outbuf的消息传送到信道上使outbuf变空)，后跟一个计算事件(处理所有传递的msg)组成。22§2.1.1系统容许的执行：指无限的执行。因为轮的结构，所以每个处理器执行无限数目的计算步，每个被发送的msg最终被传递同步与异步系统的区别在一个无错的同步系统中，一个算法的执行只取决于初始配置但在一个异步系统中，对于相同的初始配置及无错假定，因为处理器步骤间隔及消息延迟均不确定，故同一算法可能有不同的执行。23§2.1.2复杂性度量分布式算法的性能：msg个数和时间。最坏性能、期望性能终止：假定每个处理器的状态集包括终止状态子集，每个的pi的转换函数对终止状态只能映射到终止状态当所有处理机均处于终止状态且没有msg在传输时，称系统(算法)已终止。算法的msg复杂性(最坏情况)：算法在所有容许的执行上发送msg总数的最大值(同步和异步系统)24§2.1.2复杂性度量时间复杂度①同步系统：最大轮数，即算法的任何容许执行直到终止的最大轮数。②异步系统：假定任何执行里的msg延迟至多是1个单位的时间，然后计算直到终止的运行时间计时执行(timedexecution)指：每个事件关联一个非负实数，表示事件发生的时间。时间起始于零，且须是非递减的。但对每个单个的处理器而言是严格增的。若执行是无限的，则执行的时间是无界的。因此执行中的事件可根据其发生时间来排序不在同一处理器上的多个事件可以同时发生，在任何有限时间之前只有有限数目的事件发生。25§2.1.2复杂性度量消息的延迟发送msg的计算事件和处理该msg的计算事件之间所逝去的时间它主要由msg在发送者的outbuf中的等待时间和在接收者的inbuf中的等待时间所构成。异步算法的时间复杂性异步算法的时间复杂性是所有计时容许执行中直到终止的最大时间，其中每个msg延时至多为1。26§2.1.3伪代码约定在形式模型中，一个算法将根据状态转换来描述。但实际上很少这样做，因为这样做难于理解。实际描述算法有两种方法：①叙述性：对于简单问题②伪码形式：对于复杂问题27§2.1.3伪代码约定异步算法：对每个处理器，用中断驱动来描述异步算法。在形式模型中，每个计算事件1次处理所有输入缓冲区中的msgs。而在算法中，一般须描述每个msg是如何逐个处理的异步算法也可在同步系统中工作，因为同步系统是异步系统的一个特例。一个计算事件中的局部计算的描述类似于顺序算法的伪代码描述。同步算法：逐轮描述伪代码约定：—在pi的局部变量中，无须用i做下标，但在讨论和证明中，加上下标i以示区别。—“//”后跟注释28§2.2生成树上的广播和汇集信息收集及分发是许多分布式算法的基础。故通过介绍这两个算法来说明模型、伪码、正确性证明及复杂性度量等概念。§2.2.1广播(Broadcast)假定网络的生成树已给定。某处理器pr希望