1、分布协同计算基础第二章: 分布式算法(1)张锡哲 副教授计算机应用技术研究所东北大学信息科学与工程学院 1.分布式算法概述 2. 形式化模型3.消息传递系统基本算法生成树上广播和敛播生成树的构造4.因果关系和时间5.选举算法6.容错一致性主要内容1. 分布式算法概述异步不能精确的知道事件发生的绝对时间，甚至相对时间有限的局部知识每个计算实体只知道它自己所获得的信息，只是全局情况的一个局部视图。 非确定性由于系统各组件执行速度的差异,执行通常具有不确定性故障各计算实体可能独立发生故障分布式算法具有更高的不确定性和行为独立性！分布式算法具有更高的不确定性和行为独立性！4分布式计算的困难处理器数目未
2、知网络拓扑结构未知不同位置上的独立输入几个程序立即运行，在不同的时间开始，以不同的速度运行处理器的不确定性不确定的消息传递次数不确定的消息顺序处理器和通信故障幸运的是，并不是每个算法都要面对所有这些不确定性！5不确定性和行为独立性行为很难理解：多处理器并行执行，算法存在多种不同表现。准确预测算法的行为是不可能的。否定结论、下界和不可能性结论增加复杂度分析：通信开销（消息数），故障单元和非故障单元的数量6分布式计算的特点从各种分布式情况中提取基本问题，给出形式化的数学模型设计解决问题的分布式算法。算法正确性证明证明不可能性结果和下限，给出问题如何才能可解的限制以及其求解代价。算法复杂度分析。7研
3、究分布式算法的方法2. 形式化模型消息传递系统模型消息传递系统模型消息传递系统模型由一组位于有向网络图节点位置的计算元素组成。表示为G(V,E),其中节点集V=p0, p1, , pn-1 代表进程的集合，边集E代表间的信道的集合。每个进程pi用整数1r标记与之相连的信道，其中r是pi的度。算法由各进程上的局部程序所组成。消息传递模型11221132p3p2p0p1进程和信道建模11inbuf2p1的局部变量outbuf1inbuf1outbuf2p2的局部变量粉色区域粉色区域(局部变量局部变量+ inbuf) 是进程的可访问状态是进程的可访问状态配置配置(Configuration)是一个向
4、量C=(q0,qn-1),其中qi是pi的一种状态。配置中outbuf向量的状态，表示在通信信道上传送的消息。配置是系统当前的快照: 进程状态 (局部变量 + 到来消息队列) +通信信道.12事件系统中发生的事情用事件模拟，考虑两种事件：计算事件(Computational event)，表示为comp(i)表示进程pi的处理步骤，将pi的转移函数应用到它当前的可存取状态提交事件(delivery event)，表示为del(i, j, m)代表将消息m从进程pi提交到进程pj进程和信道建模进程pi用状态机描述，包括：进程标识i状态集合Qi消息转移函数信道变量outbufil和inbufil
5、,l=1,2,r从进程p1 到进程p2 的每个信道包括以下两部分：p1的outbuf变量，p2的inbuf 变量Outbuf 对应物理信道, inbuf 对应接收消息队列14提交事件将消息m从进程pi提交到pj将消息从发送者的outbufs移到接受者的 inbufs中; 消息将在下一次处理时可用p1p2m3 m2 m1p1p2m3 m2 m1计算事件以进程旧的可存取状态开始 (局部变量+ 到来消息)将转移函数应用到进程的当前可存取状态，处理所有的到来消息以新的可存取状态结束，将inbufs清空，将新消息放入outbufs中计算事件cd e旧局部状态ab新局部状态执行执行是随事件而改变的配置序列
6、,其形式是: 配置, 事件,配置, 事件,配置, 初始配置中: 每个进程都处于初始状态,所有的inbufs都为空对于每个连续配置(config, event, config), 新旧配置不变，除非发生以下事件: 提交事件: 将指定消息从发送者的outbuf 传送到接收者的inbuf 中 计算事件: 将转移函数应用到指定进程的可存取状态上安全性分布式算法需要满足两类性质：安全性条件(safety condition)在算法每次执行的每次配置中，断言P为真活跃性条件(liveness condition)在算法每次执行的某些配置中，断言P为真满足全部所要求的安全性条件的序列，称为一个执行。如果某次
7、执性满足全部所要求的活跃性条件，则称该执行是合法的(admissible)。异步执行异步模型中，如果某次执行满足以下条件，称该执行是合法的：每条发送的消息都被提交每个进程都有无限的计算事件数执行段是如下格式的序列： 其中每个Ck是一个配置，每个 是一个事件执行是一个执行段 ,其中C0是初始配置。调度是执行中的事件序列，即 .如果局部程序是确定的，执行由初始配置C0和调度唯一确定，表示为exec(C0, ),322110CCCk,322110CCC123, 异步执行执行必须满足以下两个条件：如果 = del(i,j,m)，那么m必定是ck-1中outbufil 的一个元素，其中l是信道pi, p
8、j中pi的标号。从ck-1到ck 的唯一改变是：在ck 中，m已从outbufil中移走并加入到inbufjh 中，其中h是信道pi,pj 中pj的标号。如果 =comp(i)，那么从ck-1到ck的的唯一改变是：pi依照其转移函数来改变状态，转移函数对ck-1 中pi 的可存取状态进行操作，并将所确定的消息集合加入到ck 的outbufi变量中，这些消息在这一事件上称为被发送的。kk例子 : 洪泛算法将洪泛算法描述为状态机交互的集合.进程的局部状态包括变量color=redred，greengreen初始:p0: color = greengreen, 所有outbufs包含Mothers:
9、 color = redred, 所有的outbufs 为空转移函数: If M 在inbuf中并且 color = redred, 那么 令color= greengreen ,将M 发送至所有的outbufs例子: 洪泛算法(续)p1p0p2MMp1p0p2MMdeliver eventat p1 from p0computationevent by p1deliver eventat p2 from p1p1p0p2MMMMp1p0p2MMcomputationevent by p2例子: 洪泛算法(续)deliver eventat p1 from p2computationevent
10、 by p1deliver eventat p0 from p1etc. to deliverrest ofmsgsp1p0p2MMMMp1p0p2MMMMp1p0p2MMMp1p0p2MMM不确定性以上的执行不是洪泛算法在网络拓扑上的唯一合法执行合法执行有很多，依赖于消息提交的顺序例如, p0 的消息可能在p1 消息前到达p2终止性为了模拟进程不发生故障，定义合法的执行的计算事件是无限的这样算法终止性如何表示？每个进程的状态集包括一个终止状态子集，并且每个进程的转移函数将终止状态仅映射成终止状态。当所有进程处于终止状态并且没有消息在传送，称算法已终止。复杂性度量集中考虑最坏情况消息复杂度:
11、:算法所有合法的执行中最大的发送消息总数。时间复杂度: : 任意合法执行中终止所需的最大时间。异步系统的时间复杂度如何衡量?异步系统的时间复杂度 计时（timed）执行是指执行中每个事件关联一个非负的实数，即事件发生的时间。消息的延迟（delay ) ，是指在发送消息的计算事件和处理消息的计算事件之间流逝的时间。时间复杂度: :所有计时的、合法的执行中，当各消息延迟最多为1 时，在终止前的最大时间这一度量仍然允许事件的任意交替，可以看做是考虑了算法的任意执行，且进行了标准化，使最长的消息延迟变成一个单位的时间。洪泛算法的复杂度定义终止状态为color = greengreen的状态.消息复杂度
12、: 消息在每条边双向传递,故共需2m个消息，其中m 为 边的个数时间复杂度: 网络直径个时间单位同步消息传递系统在同步系统中，如果一个执行有无限“轮(round)”，则称它是合法的执行什么是“轮”?执行按论划分，每一轮中:各处理器可以发送消息给每个邻居，消息被提交；每个处理器基于刚刚接收到的消息进行计算。时间复杂度是在算法所有合法的执行中最大的终止前轮数。 同步模型的例子洪泛算法在同步系统中的执行第一轮:将M从p0提交到 p1将M从p0提交到 p2p0 does nothingp1 color=green，将M发送到 p0 and p2p2 color=green，将M发送到 p0 and p
13、1同步模型的例子第2轮:将M从p1提交到 p0将M从p2提交到 p0将M从p2提交到 p1将M从p1提交到 p2p0 does nothingp1 does nothingp2 does nothing同步模型的例子CPSC 668Set 1: Introduction33p1p0p2MMMMp1p0p2MMp1p0p2round 1 eventsround 2events同步洪泛算法的复杂度时间复杂度为diameter 消息复杂度为2m与异步算法相同.只是特例，并不是所有算法都相同35伪代码约定在形式模型中，一个算法将根据状态转换来描述。但实际上很少这样做，因为这样做难于理解。 实际描述算法
14、有两种方法： 叙述性：对于简单问题 伪码形式：对于复杂问题36伪代码约定异步算法：对每个处理器，用中断驱动来描述异步算法。在形式模型中，每个计算事件1次处理所有输入缓冲区中的msgs。而在算法中，一般须描述每个msg是如何逐个处理的一个计算事件中的局部计算的描述类似于顺序算法的伪代码描述同步算法：逐轮描述伪代码约定：在pi的局部变量中，无须用i做下标，但在讨论和证明中，加上下标i以示区别。3.消息传递系统基本算法生成树上的广播设进程已经有关于信道拓扑的有根生成树的信息树: 无环连通图生成树: 包含所有进程有根: 有唯一的根节点通过每个进程的 parent和children 局部变量记录生成树的
15、结构表示在生成树中从父节点到子节点的边由于分布式系统中，每个节点并不知道全局拓扑，但某些算法需要在由于分布式系统中，每个节点并不知道全局拓扑，但某些算法需要在特定结构下才能达到最优，比如广播特定结构下才能达到最优，比如广播/敛播在树结构下才能达到消息敛播在树结构下才能达到消息复杂度最优，因此构造生成树是必要的，是其他算法的基础。复杂度最优，因此构造生成树是必要的，是其他算法的基础。算法步骤示例生成树上的广播每个进程的状态包含：变量parenti，保存一个进程索引或为空变量childreni，保存一组进程索引布尔量terminatedi，指示pi是否处在终止状态所有terminatedi初始为假
16、生成树上的广播根节点将消息M发送给他所有的子节点当一个进程从他的父节点接收到消息M将消息M 发送给它的子节点终止生成树上的广播Initially (M) is in transit from pr to all its children in the spanning tree. Code for pr: 1: upon receiving no message: / first computation event by pr 2: terminate Code for pi, 0 i n-1, ir: 3: upon receiving (M) from parent: 4: send (M
17、) to all children 5: terminate复杂性分析对同步模型中广播算法的每一次合法执行，生成树中距离pr为t的每个进程在第t轮接收到消息。当一颗有根的生成树，其深度d已知时，存在一个同步的广播算法，其消息复杂度为n-1，时间复杂度为d44复杂性分析-同步模型引理1：在同步模型中，在广播算法的每个合法执行里，树中每个距离pr为t的处理器在第t轮里接收消息M。证明：对距离t使用归纳法。归纳基础：t=1，pr的每个孩子在第1轮里接收来自于pr的消息M归纳假设：假设树上每个距pr为t-11的处理器在第t-1轮里已收到M。归纳步骤：设pi到pr距离为t，设pj是pi的双亲，因pj到p
18、r的距离为t-1，由归纳假设，在第t-1轮pj收到M。由算法描述知，在第t轮里pi收到来自于pj的消息M定理： 当生成树高度为d时，存在一个消息复杂度为n-1，时间复杂度为d的同步广播算法45复杂性分析-异步模型引理2：在异步模型的广播算法的每个合法执行里，树中每个距离pr为t的处理器至多在时刻t接收消息M。证明：对距离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
19、的M至多在t时刻到达。复杂性分析同步模型:时间复杂度为生成树的深度d消息数为 n - 1异步模型:与同步模型相同敛播做与广播相反的操作:叶结点将消息发送给它的父节点非叶节点等待接收每个子节点发送的消息,然后将其合并发送至父节点.敛播ghabcdefghde,gf,hc,f,hb,d虚线:非生成树边实心箭头: 父子关系生成树的构造如何构造生成树？假设有进程作为根修改洪泛算法生成树的构造根进程发送消息M给它的所有邻居非根进程首次收到消息M:将消息M的发送者设为它的父节点回复“parent“ 消息给发送者将 M 发送给所有其他邻居 (如没有则终止)非首次收到消息M回复“already”消息给发送者5
20、1基本思想首先，pr发送M给所有邻居，pr为根当pi从某邻居pj收到的M是第1个来自邻居的msg时，pj是pi的双亲；若pi首次收到的M同时来自多个邻居，则用一个comp事件处理自上一comp事件以来的所有已收到的msgs，故此时，pi可在这些邻居中任选一个邻居pj做双亲。当pi确定双亲是pj时，发送给pj，并向此后收到发来M的处理器发送msg生成树的构造-基本思路52基本思想因为pi收到pj的M是第1个M，就不可能已收到其他结点的M，当然可能同时收到(说明pi与这些邻居间不是父子关系，或说它们不是生成树中的边)；同时pi将M转发给其余邻居，这些邻居尚未发M给pi，或虽然已发M给pi，但pi尚
21、未收到。pi向那些尚未发M给pi(或已发M但尚未到达pi)的邻居转发M之后，等待这些邻居发回响应msg：或。那些回应的邻居是pi的孩子。当pi发出M的所有接收者均已回应(或)，则pi终止。将parent和children边保留即为生成树。生成树的构造-基本思路Initially parent = , children = , and other = . 1: upon receiving no message: 2: if pi = pr and parent = then / root has not yet sent (M) 3: send to all neighbors 4: pare
22、nt :=pi, 5: upon receiving from neighbor pj: 6: if parent = then / pi has not received before 7: parent :=pj 8: send to pj 9: send to all neighbors except pj 10: else send to pj 11: upon receiving from neighbor pj: 12: add pj to children 13: if children U other contains all neighbors except parent t
23、hen 14: terminate 15: upon receiving from neighbor pj: 16: add pj to other 17: if children U other contains all neighbors except parent then 18: terminate 54算法分析引理：在异步模型的每个合法执行中，上述算法构造一棵根为pr的生成树。(正确性)证明：算法代码告诉我们两个重要事实a)一旦处理器设置了parent变量，它绝不改变，即它只有一个双亲b)处理器的孩子集合决不会减小。因此，最终由parent和children确定的图结构G是静止的，且
24、parent和children变量在不同结点上是一致的，即若pj是pi的孩子，则pi是pj的双亲。 下述证明结果图G是根为pr的有向生成树。55为何从根能到达每一结点？(连通)反证：假设某结点在G中从pr不可达，因网络是连通的，若存在两个相邻的结点pi和pj使得pj在G中是从pr可达的(以下简称pj可达)，但pi不可达。因为G里一结点从pr可达当且仅当它曾设置过自己的parent变量(Ex2.4证明)，所以pi的parent变量在整个执行中仍为nil，而pj在某点上已设置过自己的parent变量，于是pj发送M到pi，因该执行是合法的，此msg必定最终被pi接收，使pi将自己的parent变量
25、设置为j。矛盾！算法分析56为何无环？(无环)假设有一环，pi1,pikpi1，若pi是pj的孩子，则pi在pj第1次收到M之后第1次收到M。因每个处理器在该环上是下一处理器的双亲，这就意味着pi1在pi1第1次接收M之前第1次接收M。矛盾！复杂性显然，此方法与洪泛算法相比，增加了msg复杂性，但只是一个常数因子。在异步通信模型里，易看到在时刻t，消息M到达所有与pr距离小于等于t的结点。因此有： 对于具有m条边和直径D的网络，给定一特殊结点，存在一个msg复杂性为O(m)，时间复杂性为O(D)的异步算法找到该网络的一棵生成树。算法分析57同步模型中的生成树前述在同步模型下仍可工作。其分析类似
26、于异步情形。然而，与异步不同的是，它所构造的生成树一定是一棵广度优先搜索(BFS)树。引理:在同步模型下，算法的每次合法执行均构造一棵根为pr的BFS树。证明：对轮t进行归纳。即要证明：在第t轮开始时刻 根据parent变量构造的图G是一棵包括所有与pr距离至多为t-1结点的BFS树； 而传输中的消息M仅来自于与pr距离恰为t-1的结点。 由此构造的树是一棵根为pr的BFS生成树算法的执行58ghabcdef同步模型: 总是给出广度优先搜索树breadth-first search (BFS) treeghabcdef异步模型: not necessarily BFS treeBoth models:O(m) 消息复杂度O(diam) 时间复杂度生成树算法的执行59ghabcdefAn asynchronous executiongave this depth-first search (DFS)tree. Is DFS property guaranteed?ghabcdefAnother asynchronousexecution results in this tree:neither BFS nor DFS
