分布式算法-基本算法.ppt

课程网站,,分布协同计算基础,第二章: 分布式算法(1) 张锡哲 副教授 计算机应用技术研究所 东北大学信息科学与工程学院,1.分布式算法概述 2. 形式化模型 3.消息传递系统基本算法 生成树上广播和敛播 生成树的构造 4.因果关系和时间 5.选举算法 6.容错一致性,主要内容,1. 分布式算法概述,异步 不能精确的知道事件发生的绝对时间，甚至相对时间 有限的局部知识 每个计算实体只知道它自己所获得的信息，只是全局情况的一个局部视图。 非确定性 由于系统各组件执行速度的差异,执行通常具有不确定性 故障 各计算实体可能独立发生故障 分布式算法具有更高的不确定性和行为独立性！,5,分布式计算的困难,处理器数目未知 网络拓扑结构未知 不同位置上的独立输入 几个程序立即运行，在不同的时间开始，以不同的速度运行 处理器的不确定性 不确定的消息传递次数 不确定的消息顺序 处理器和通信故障 幸运的是，并不是每个算法都要面对所有这些不确定性！,6,不确定性和行为独立性,行为很难理解：多处理器并行执行，算法存在多种不同表现。 准确预测算法的行为是不可能的。 否定结论、下界和不可能性结论增加 复杂度分析：通信开销（消息数），故障单元和非故障单元的数量,7,分布式计算的特点,从各种分布式情况中提取基本问题，给出形式化的数学模型 设计解决问题的分布式算法。 算法正确性证明 证明不可能性结果和下限，给出问题如何才能可解的限制以及其求解代价。 算法复杂度分析。,8,研究分布式算法的方法,2. 形式化模型,消息传递系统模型,消息传递系统模型由一组位于有向网络图节点位置的计算元素组成。 表示为G(V,E),其中节点集V=p0, p1, , pn-1 代表进程的集合，边集E代表间的信道的集合。 每个进程pi用整数1r标记与之相连的信道，其中r是pi的度。 算法由各进程上的局部程序所组成。,消息传递模型,1,1,2,2,1,1,3,2,p3,p2,p0,p1,进程和信道建模,12,粉色区域(局部变量+ inbuf) 是进程的可访问状态,配置,配置(Configuration)是一个向量C=(q0,qn-1),其中qi是pi的一种状态。 配置中outbuf向量的状态，表示在通信信道上传送的消息。 配置是系统当前的快照: 进程状态 (局部变量 + 到来消息队列) +通信信道.,13,事件,系统中发生的事情用事件模拟，考虑两种事件： 计算事件(Computational event)，表示为comp(i) 表示进程pi的处理步骤，将pi的转移函数应用到它当前的可存取状态 提交事件(delivery event)，表示为del(i, j, m) 代表将消息m从进程pi提交到进程pj,进程和信道建模,进程pi用状态机描述，包括： 进程标识i 状态集合Qi 消息转移函数 信道变量outbufil和inbufil ,l=1,2,r 从进程p1 到进程p2 的每个信道包括以下两部分： p1的outbuf变量， p2的inbuf 变量 Outbuf 对应物理信道, inbuf 对应接收消息队列,15,提交事件,将消息m从进程pi提交到pj 将消息从发送者的outbufs移到接受者的 inbufs中; 消息将在下一次处理时可用,p1,p2,m3 m2 m1,计算事件,以进程旧的可存取状态开始 (局部变量+ 到来消息) 将转移函数应用到进程的当前可存取状态，处理所有的到来消息 以新的可存取状态结束，将inbufs清空，将新消息放入outbufs中,计算事件,c,d e,旧局部状态,ab,新局部状态,执行,执行是随事件而改变的配置序列,其形式是: 配置, 事件,配置, 事件,配置, 初始配置中: 每个进程都处于初始状态,所有的inbufs都为空 对于每个连续配置(config, event, config), 新旧配置不变，除非发生以下事件: 提交事件: 将指定消息从发送者的outbuf 传送到接收者的inbuf 中 计算事件: 将转移函数应用到指定进程的可存取状态上,安全性,分布式算法需要满足两类性质： 安全性条件(safety condition) 在算法每次执行的每次配置中，断言P为真 活跃性条件(liveness condition) 在算法每次执行的某些配置中，断言P为真 满足全部所要求的安全性条件的序列，称为一个执行。 如果某次执性满足全部所要求的活跃性条件，则称该执行是合法的(admissible)。,异步执行,异步模型中，如果某次执行满足以下条件，称该执行是合法的： 每条发送的消息都被提交 每个进程都有无限的计算事件数 执行段是如下格式的序列： 其中每个Ck是一个配置，每个 是一个事件 执行是一个执行段 ,其中C0是初始配置。 调度是执行中的事件序列，即 . 如果局部程序是确定的，执行由初始配置C0和调度唯一确定，表示为exec(C0, ),异步执行,执行必须满足以下两个条件： 如果 = del(i,j,m)，那么m必定是ck-1中outbufil 的一个元素，其中l是信道pi, pj中pi的标号。从ck-1到ck 的唯一改变是：在ck 中，m已从outbufil中移走并加入到inbufjh 中，其中h是信道pi,pj 中pj的标号。 如果 =comp(i)，那么从ck-1到ck的的唯一改变是：pi依照其转移函数来改变状态，转移函数对ck-1 中pi 的可存取状态进行操作，并将所确定的消息集合加入到ck 的outbufi变量中，这些消息在这一事件上称为被发送的。,例子 : 洪泛算法,将洪泛算法描述为状态机交互的集合. 进程的局部状态包括变量color=red，green 初始: p0: color = green, 所有outbufs包含M others: color = red, 所有的outbufs 为空 转移函数: If M 在inbuf中并且 color = red, 那么 令color= green ,将M 发送至所有的outbufs,例子: 洪泛算法(续),例子: 洪泛算法(续),不确定性,以上的执行不是洪泛算法在网络拓扑上的唯一合法执行 合法执行有很多，依赖于消息提交的顺序 例如, p0 的消息可能在p1 消息前到达p2,终止性,为了模拟进程不发生故障，定义合法的执行的计算事件是无限的 这样算法终止性如何表示？ 每个进程的状态集包括一个终止状态子集，并且每个进程的转移函数将终止状态仅映射成终止状态。 当所有进程处于终止状态并且没有消息在传送，称算法已终止。,复杂性度量,集中考虑最坏情况 消息复杂度:算法所有合法的执行中最大的发送消息总数。 时间复杂度: 任意合法执行中终止所需的最大时间。 异步系统的时间复杂度如何衡量?,异步系统的时间复杂度,计时（timed）执行是指执行中每个事件关联一个非负的实数，即事件发生的时间。 消息的延迟（delay ) ，是指在发送消息的计算事件和处理消息的计算事件之间流逝的时间。 时间复杂度:所有计时的、合法的执行中，当各消息延迟最多为1 时，在终止前的最大时间 这一度量仍然允许事件的任意交替，可以看做是考虑了算法的任意执行，且进行了标准化，使最长的消息延迟变成一个单位的时间。,洪泛算法的复杂度,定义终止状态为color = green的状态. 消息复杂度: 消息在每条边双向传递,故共需2m个消息，其中m 为 边的个数 时间复杂度: 网络直径个时间单位,同步消息传递系统,在同步系统中，如果一个执行有无限“轮(round)”，则称它是合法的执行 什么是“轮”? 执行按论划分，每一轮中: 各处理器可以发送消息给每个邻居，消息被提交； 每个处理器基于刚刚接收到的消息进行计算。 时间复杂度是在算法所有合法的执行中最大的终止前轮数。,同步模型的例子,洪泛算法在同步系统中的执行 第一轮: 将M从p0提交到 p1 将M从p0提交到 p2 p0 does nothing p1 color=green，将M发送到 p0 and p2 p2 color=green，将M发送到 p0 and p1,同步模型的例子,第2轮: 将M从p1提交到 p0 将M从p2提交到 p0 将M从p2提交到 p1 将M从p1提交到 p2 p0 does nothing p1 does nothing p2 does nothing,同步模型的例子,CPSC 668,Set 1: Introduction,34,同步洪泛算法的复杂度,时间复杂度为diameter 消息复杂度为2m 与异步算法相同. 只是特例，并不是所有算法都相同,36,伪代码约定,在形式模型中，一个算法将根据状态转换来描述。但实际上很少这样做，因为这样做难于理解。 实际描述算法有两种方法： 叙述性：对于简单问题 伪码形式：对于复杂问题,37,伪代码约定,异步算法：对每个处理器，用中断驱动来描述异步算法。 在形式模型中，每个计算事件1次处理所有输入缓冲区中的msgs。而在算法中，一般须描述每个msg是如何逐个处理的 一个计算事件中的局部计算的描述类似于顺序算法的伪代码描述 同步算法：逐轮描述 伪代码约定： 在pi的局部变量中，无须用i做下标，但在讨论和证明中，加上下标i以示区别。,3.消息传递系统基本算法,生成树上的广播,设进程已经有关于信道拓扑的有根生成树的信息 树: 无环连通图 生成树: 包含所有进程 有根: 有唯一的根节点 通过每个进程的 parent和children 局部变量记录生成树的结构 表示在生成树中从父节点到子节点的边,由于分布式系统中，每个节点并不知道全局拓扑，但某些算法需要在特定结构下才能达到最优，比如广播/敛播在树结构下才能达到消息复杂度最优，因此构造生成树是必要的，是其他算法的基础。,算法步骤示例,生成树上的广播,每个进程的状态包含： 变量parenti，保存一个进程索引或为空 变量childreni，保存一组进程索引 布尔量terminatedi，指示pi是否处在终止状态 所有terminatedi初始为假,生成树上的广播,根节点将消息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) to all children 5: terminate,复杂性分析,对同步模型中广播算法的每一次合法执行，生成树中距离pr为t的每个进程在第t轮接收到消息。 当一颗有根的生成树，其深度d已知时，存在一个同步的广播算法，其消息复杂度为n-1，时间复杂度为d,45,复杂性分析-同步模型,引理1：在同步模型中，在广播算法的每个合法执行里，树中每个距离pr为t的处理器在第t轮里接收消息M。 证明：对距离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的消息M 定理： 当生成树高度为d时，存在一个消息复杂度为n-1，时间复杂度为d的同步广播算法,46,复杂性分析-异步模型,引理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的M至多在t时刻到达。,复杂性分析,同步模型: 时间复杂度为生成树的深度d 消息数为 n - 1 异步模型: 与同步模型相同,敛播,做与广播相反的操作: 叶结点将消息发送给它的父节点 非叶节点等待接收每个子节点发送的消息,然后将其合并发送至父节点.,敛播,虚线:非生成树边,实心箭头: 父子关系,生成树的构造,如何构造生成树？ 假设有进程作为根 修改洪泛算法,生成树的构造,根进程发送消息M给它的所有邻居 非根进程首次收到消息M: 将消息M的发送者设为它的父节点 回复“parent“ 消息给发送者 将 M 发送给所有其他邻居 (如没有则终止) 非首次收到消息M 回复“already”消息给发送者,52,基本思想 首先，pr发送M给所有邻居，pr为根 当pi从某邻居pj收到的M是第1个来自邻居的msg时，pj是pi的双亲；若pi首次收到的M同时来自多个邻居，则用一个comp事件处理自上一comp事件以来的所有已收到的msgs，故此时，pi可在这些邻居中任选一个邻居pj做双亲。 当pi确定双亲是pj时，发送给pj，并向此后收到发来M的处理器发送msg,生成树的构造-基本思路,53,基本思想 因为pi收到pj的M是第1个M，就不可能已收到其他结点的M，当然可能同时收到(说明pi与这些邻居间不是父子关系，或说它们不是生成树中的边)；同时pi将M转发给其余邻居，这些邻居尚未发M给pi，或虽然已发M给pi，但pi尚未收到。 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: parent :=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 then 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,55,算法分析,引理：在异步模型的每个合法执行中，上述算法构造一棵根为pr的生成树。(正确性) 证明：算法代码告诉我们两个重要事实 一旦处理器设置了parent变量，它绝不改变，即它只有一个双亲 处理器的孩子集合决不会减小。 因此，最终由parent和children确定的图结构G是静止的，且parent和children变量在不同结点上是一致的，即若pj是pi的孩子，则pi是pj的双亲。 下述证明结果图G是根为pr的有向生成树。,56,为何从根能到达每一结点？(连通) 反证：假设某结点在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变量设置为j。矛盾！,算法分析,57,为何无环？(无环) 假设有一环，pi1,pi