1、1第二部分第二部分 分布式算法分布式算法汪炀汪炀第二次课第二次课中国科学技术大学计算机系中国科学技术大学计算机系 国家高性能计算中心（合肥）国家高性能计算中心（合肥）22.1.1 系统系统2.异步系统异步系统n 异步：异步：msg传递的时间和一个处理器的两个相继步骤之间的传递的时间和一个处理器的两个相继步骤之间的时间无固定上界时间无固定上界例如，例如，Internet中，中，email虽然常常是几秒种到达，但也可能虽然常常是几秒种到达，但也可能要数天到达。当然要数天到达。当然msg延迟有上界，但它可能很大，且随时延迟有上界，但它可能很大，且随时间而改变。间而改变。因此异步算法设计时，须使之独立
2、于特殊的计时参数，不能因此异步算法设计时，须使之独立于特殊的计时参数，不能依赖于该上界。依赖于该上界。n 执行片断执行片断一个异步一个异步msg传递系统的一个执行片断传递系统的一个执行片断是一个有限或无限是一个有限或无限的序列：的序列： C0, 1, C1, 2, C2, 3, , (C0不一定是初始配置不一定是初始配置)这里这里Ck是一个配置，是一个配置， k是一个事件。若是一个事件。若是有限的，则它是有限的，则它须结束于某个配置，且须满足下述条件：须结束于某个配置，且须满足下述条件：32.1.1 系统系统v若若k =del(i,j,m)，则，则m必是必是Ck-1里的里的outbufill的
3、一个元素，这的一个元素，这里里ll是是pi的信道的信道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里里)上进行上进行操作，清空
4、操作，清空inbufill，(1llr)发送发送msg：将转换函数指定的消息集合加到：将转换函数指定的消息集合加到Ck里的变量里的变量outbufi上。上。(Note:发送发送send，传递，传递delivery之区别之区别)即：即： pi以当前状态以当前状态(在在Ck-1中中)为基础按转换函数改变状态并发为基础按转换函数改变状态并发出出msg。42.1.1 系统系统n 执行：执行：一个执行是一个执行片断一个执行是一个执行片断C0, 1, C1, 2, ,这里这里C0是一个初始配置。是一个初始配置。n 调度：调度：一个调度一个调度(或调度片段或调度片段)总是和执行总是和执行(或执行片或执行片断
5、断)联系在一起的，它是执行中的事件序列：联系在一起的，它是执行中的事件序列：1, 2, 。并非每个事件序列都是调度。例如，并非每个事件序列都是调度。例如，del(1,2,m)不不是调度，因为此事件之前，是调度，因为此事件之前，p1没有步骤发送没有步骤发送(send)m。若局部程序是确定的，则执行若局部程序是确定的，则执行(或执行片断或执行片断)就由初就由初始配置始配置C0和调度和调度(或调度片断或调度片断)唯一确定，可表示为唯一确定，可表示为exec(C0 , )。52.1.1 系统系统n 容许执行：容许执行：(满足活跃性条件满足活跃性条件)异步系统中，若某个处理器有无限个计算事件，每异步系统
6、中，若某个处理器有无限个计算事件，每个发送的个发送的msg都最终被传递，则执行称为容许的。都最终被传递，则执行称为容许的。Note: 无限个计算事件是指处理器没有出错无限个计算事件是指处理器没有出错，但它，但它不蕴含处理器的局部程序必须包括一个无限循环不蕴含处理器的局部程序必须包括一个无限循环非形式地说：非形式地说：一个算法终止是指在某点后转换函数一个算法终止是指在某点后转换函数不改变处理器的状态。不改变处理器的状态。n 容许的调度：容许的调度：若它是一个容许执行的调度。若它是一个容许执行的调度。62.1.1 系统系统3.同步系统同步系统在同步模型中，处理器按锁步骤在同步模型中，处理器按锁步骤
7、(lock-step)执行：执行：执行被划分为轮，每轮里，执行被划分为轮，每轮里，每个处理器能够发送一个每个处理器能够发送一个msg到每个邻居，这些到每个邻居，这些msg被传递。被传递。每个处理器一接到每个处理器一接到msg就进行计算。就进行计算。虽然特殊的分布系统里一般达不到，但这种模型对于设虽然特殊的分布系统里一般达不到，但这种模型对于设计算法非常方便，因为无需和更多的不确定性打交道。当计算法非常方便，因为无需和更多的不确定性打交道。当按此模型设计算法后，能够很容易模拟得到异步算法。按此模型设计算法后，能够很容易模拟得到异步算法。n 轮：轮：在同步系统中，配置和事件序列可以划分成不相交的在
8、同步系统中，配置和事件序列可以划分成不相交的轮，每轮由一个传递事件轮，每轮由一个传递事件(将将outbuf的消息传送到信道上使的消息传送到信道上使outbuf变空变空)，后跟一个计算事件，后跟一个计算事件(处理所有传递的处理所有传递的msg)组组成。成。72.1.1 系统系统n 容许的执行：容许的执行：指无限的执行。指无限的执行。因为轮的结构，所以因为轮的结构，所以每个处理器执行无限数目的计算步，每个处理器执行无限数目的计算步，每个被发送的每个被发送的msg最终被传递最终被传递n 同步与异步系统的区别同步与异步系统的区别在一个无错的同步系统中，一个算法的执行只取决在一个无错的同步系统中，一个算
9、法的执行只取决于初始配置于初始配置但在一个异步系统中，对于相同的初始配置及无错但在一个异步系统中，对于相同的初始配置及无错假定，因为处理器步骤间隔及消息延迟均不确定，假定，因为处理器步骤间隔及消息延迟均不确定，故同一算法可能有不同的执行。故同一算法可能有不同的执行。82.1.2 复杂性度量复杂性度量n 分布式算法的性能：分布式算法的性能：v消息复杂度消息复杂度v时间复杂度时间复杂度v空间复杂度空间复杂度v性能衡量：最坏性能、期望性能性能衡量：最坏性能、期望性能n 终止：终止：假定每个处理器的状态集包括终止状态子集，假定每个处理器的状态集包括终止状态子集，每个的每个的pi的转换函数对终止状态只能
10、映射到终止状的转换函数对终止状态只能映射到终止状态态当所有处理机当所有处理机均处于终止状态且没有均处于终止状态且没有msg在传输时在传输时，称系统称系统(算法算法)已终止。已终止。92.1.2 复杂性度量复杂性度量n 算法的算法的msg复杂性复杂性(最坏情况最坏情况)：算法在所有算法在所有容许容许的的执行上发送执行上发送msg总数的最大值总数的最大值(同步和异步系统同步和异步系统)n 消息复杂度度量消息复杂度度量v消息复杂度：消息总数消息复杂度：消息总数/消息中总的位数长度消息中总的位数长度v消息总数：消息总数：4/4v消息位数总长度消息位数总长度(位复杂度位复杂度)：14/8102.1.2
11、复杂性度量复杂性度量n 时间复杂度时间复杂度同步系统：最大轮数，即算法的任何容许执行直到终止的同步系统：最大轮数，即算法的任何容许执行直到终止的最大轮数。最大轮数。异步系统：假设：异步系统：假设：节点计算任何有限数目事件的时间为节点计算任何有限数目事件的时间为0；一条消息发送和接收之间的时间至多为一条消息发送和接收之间的时间至多为1个时间单位，定义个时间单位，定义为：所有计时容许执行中直到终止的最大时间。为：所有计时容许执行中直到终止的最大时间。n 计时执行计时执行(timed execution)指：指：每个事件关联一个非负实数每个事件关联一个非负实数，表示事件发生的时间。时，表示事件发生的
12、时间。时间起始于零，且须是非递减的。但对间起始于零，且须是非递减的。但对每个单个的处理器而言每个单个的处理器而言是严格增的是严格增的。若执行是无限的，则执行的时间是无界的。因此执行中若执行是无限的，则执行的时间是无界的。因此执行中的事件可根据其发生时间来排序的事件可根据其发生时间来排序不在同一处理器上的多个事件可以同时发生，在任何有不在同一处理器上的多个事件可以同时发生，在任何有限时间之前只有有限数目的事件发生。限时间之前只有有限数目的事件发生。112.1.2 复杂性度量复杂性度量n 消息的延迟消息的延迟v 发送发送msg的计算事件和处理该的计算事件和处理该msg的计算事件之间所逝去的时间的计
13、算事件之间所逝去的时间v 它主要由它主要由msg在发送者的在发送者的outbuf中的等待时间和在接收者的中的等待时间和在接收者的inbuf中的等待时间所构成中的等待时间所构成n 异步算法的时间复杂性异步算法的时间复杂性定义中，每个定义中，每个msg延时至多为延时至多为1，但，但实际中，至多实际中，至多1个时间个时间单位会很难计算，因此修改假设：单位会很难计算，因此修改假设： 一条消息发送和接收之间时间恰好为一条消息发送和接收之间时间恰好为1个时间单位个时间单位 一条消息发送和接收之间时间介于一条消息发送和接收之间时间介于和和1之间之间(0 1) 假设消息传递的延迟满足某种概率分布，并由此来计算
14、假设消息传递的延迟满足某种概率分布，并由此来计算122.1.3 伪代码约定伪代码约定在形式模型中，一个算法将根据状态转换在形式模型中，一个算法将根据状态转换来描述。但实际上很少这样做，因为这样做来描述。但实际上很少这样做，因为这样做难于理解。难于理解。 实际描述算法有两种方法：实际描述算法有两种方法： 叙述性：对于简单问题叙述性：对于简单问题 伪码形式：对于复杂问题伪码形式：对于复杂问题132.1.3 伪代码约定伪代码约定n 异步算法：异步算法：对每个处理器，用对每个处理器，用中断驱动中断驱动来描述异步算法。来描述异步算法。在形式模型中，每个计算事件在形式模型中，每个计算事件1次处理所有输入缓
15、冲区中的次处理所有输入缓冲区中的msgs。而在算法中，一般须描述每个。而在算法中，一般须描述每个msg是如何逐个处理是如何逐个处理的的异步算法也可在同步系统中工作，因为同步系统是异步系异步算法也可在同步系统中工作，因为同步系统是异步系统的一个特例。统的一个特例。一个计算事件中的局部计算的描述类似于顺序算法的伪代一个计算事件中的局部计算的描述类似于顺序算法的伪代码描述码描述。n 同步算法：同步算法：逐轮描述逐轮描述n 伪代码约定：伪代码约定：在在pi的局部变量中，无须用的局部变量中，无须用i做下标，但在讨论和证明中，做下标，但在讨论和证明中，加上下标加上下标i以示区别。以示区别。“/”后跟注释后
16、跟注释142.2 生成树上的广播和汇集生成树上的广播和汇集n 为什么广播和汇集算法为什么广播和汇集算法 信息收集（信息收集（敛播敛播/汇集汇集）及分发）及分发(广播广播)是许多分布式是许多分布式算法的基础。故通过介绍这两个算法来说明模型、算法的基础。故通过介绍这两个算法来说明模型、伪码、正确性证明及复杂性度量等概念。伪码、正确性证明及复杂性度量等概念。n 为什么生成树上？为什么生成树上？由于分布式系统中，每个节点并不知道全局拓扑状由于分布式系统中，每个节点并不知道全局拓扑状态，但某些算法需要在特定的结构下才能达到最优。态，但某些算法需要在特定的结构下才能达到最优。例如：广播例如：广播/敛播在树
17、结构下才能达到消息复杂度敛播在树结构下才能达到消息复杂度最优，因此构造生成树是必要的，且是其他算法的最优，因此构造生成树是必要的，且是其他算法的基础。基础。152.2 生成树上的广播和汇集生成树上的广播和汇集n生成树生成树 一个无向连通图一个无向连通图G的的生成树生成树(Spanning Tree)是指满足下列条是指满足下列条件的件的G的子图的子图T： G和和T具有相同的顶点数；具有相同的顶点数； 在在T中有足够的边能够连接中有足够的边能够连接G的所有顶点且不出现回路。的所有顶点且不出现回路。n最小生成树最小生成树 如果图的每一条边都指定有一个权，那么所有的边权最小的如果图的每一条边都指定有一
18、个权，那么所有的边权最小的生成树，就成为最小代价生成树生成树，就成为最小代价生成树(Minimum Cost Spanning Tree, MCST) ，简称，简称最小生成树最小生成树(MST)。生成树一共有生成树一共有16棵棵34C最小生成树最小生成树162.2 生成树上的广播和汇集生成树上的广播和汇集2.2.1 广播广播 (Broadcast) 假定网络的生成假定网络的生成树已给定。某处理器树已给定。某处理器pr希望将消息希望将消息M发送至其发送至其余处理器。余处理器。 假定生成树的假定生成树的根根为为pr ，每个处理器有，每个处理器有一个信道连接其双亲一个信道连接其双亲(pr除外除外)，
19、有若干个信，有若干个信道连接其孩子。道连接其孩子。172.2.1 广播广播l 根根pr发送发送M给给所有孩子。所有孩子。(a)l 当某节点收到当某节点收到父节点的父节点的M时，时，发送发送M到自己到自己的所有孩子的所有孩子(b)。182.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
20、M from parent:4. send M to all children;5. terminate;2.用状态转换来分析算法用状态转换来分析算法n 每个处理器每个处理器pi包含状态包含状态变量变量parenti：表示处理器：表示处理器pi双亲节点的标号或为双亲节点的标号或为nil(若若i=r) 变量变量childreni：pi的孩子节点标号的集合的孩子节点标号的集合布尔变量布尔变量terminatedi：表示：表示pi是否处于终止状态是否处于终止状态192.2.1 广播广播n初始状态初始状态vparent和和children的值是形成生成树时确定的的值是形成生成树时确定的v所有所有ter
21、minated的值均为假的值均为假voutbufr j , jchildrenr持有消息持有消息M，注意，注意j不是信道标号，而是不是信道标号，而是r的邻居号。（任何系统中，的邻居号。（任何系统中，均假定各节点标号互不相等）均假定各节点标号互不相等）v所有其他节点的所有其他节点的outbuf变量均为空。变量均为空。ncomp(i)的结果的结果若对于某个若对于某个k，M在在inbufik里，则里，则M被放到被放到outbufi j 里，里， jchildreni202.2.1 广播广播n pi进入终止状态进入终止状态将将terminatedi置为置为true；若；若i=r且且terminated
22、r为为false，则，则terminatedr立即置为立即置为true，否则空操作。，否则空操作。n 该算法对同步及异步系统均正确，且在两模型中，该算法对同步及异步系统均正确，且在两模型中，msg和时间复杂度相同。和时间复杂度相同。n Msg复杂度复杂度无论在同步还是异步模型中，无论在同步还是异步模型中，msg M在生成树的每条边上恰在生成树的每条边上恰好发送一次。好发送一次。因此，因此，msg复杂性为复杂性为n-1，即，即O(n)。 时间复杂度为时间复杂度为h，即，即O(h)，其中，其中h为生成树的高度。为生成树的高度。212.2.1 广播广播输入：根节点上的消息输入：根节点上的消息输出：每
23、个节点都收到消息输出：每个节点都收到消息Code for PiBegin while (receiving no message) do (1) if i=r then 此节点为根节点此节点为根节点 (1.1) send to all children (1.2) terminates end if end while while (receiving from Pj) do (1) send to all children (2) terminates end whileend 说明：说明：本算法中本算法中While并不代并不代表循环，而是代表满足表循环，而是代表满足条件时，节点所做的动作条
24、件时，节点所做的动作222.2.1 广播广播n 时间复杂性：时间复杂性：同步模型：同步模型：时间由轮来度量。时间由轮来度量。Lemma2.1 在同步模型中，在广播算法的每个容许执行在同步模型中，在广播算法的每个容许执行里，树中每个距离里，树中每个距离pr为为t的处理器在第的处理器在第t轮里接收消息轮里接收消息M。pf：对距离对距离t使用归纳法。使用归纳法。归纳基础归纳基础：t=1，pr的每个孩子在第的每个孩子在第1轮里接收来自于轮里接收来自于pr的消息的消息M归纳假设归纳假设：假设树上每个距：假设树上每个距pr为为t-11的处理器在第的处理器在第t-1轮轮里已收到里已收到M。归纳步骤：归纳步骤
25、：设设pi到到pr距离为距离为t，设，设pj是是pi的双亲，因的双亲，因pj到到pr的距离为的距离为t-1，由归纳假设，在第，由归纳假设，在第t-1轮轮pj收到收到M。由算法。由算法描述知，在第描述知，在第t轮里轮里pi收到来自于收到来自于pj的消息的消息MTh2.2 当生成树高度为当生成树高度为d时，存在一个消息复杂度为时，存在一个消息复杂度为n-1，时间复杂度为时间复杂度为d的同步广播算法的同步广播算法232.2.1 广播广播异步异步模型模型Lemma2.3 在异步模型的广播算法的每个容许执行里，在异步模型的广播算法的每个容许执行里，树中每个距离树中每个距离pr为为t的处理器至多在时刻的处
26、理器至多在时刻t接收消息接收消息M。pf：对距离对距离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时刻到达。时刻到达。Th2.4 同同Th2.224下次继续！下次继续！
