在算法每次执行的某些配置中，断言P为真


满足全部所要求的安全性条件的序列，称为一个 执行。 如果某次执性满足全部所要求的活跃性条件，则 称该执行是合法的(admissible)。
异步执行

异步模型中，如果某次执行满足以下条件，称该执行是 合法的：


每条发送的消息都被提交 每个进程都有无限的计算事件数


非确定性


故障


分布式算法具有更高的不确定性和行为独立性！！
5
不确定性和行为独立性




处理器数目未知 网络拓扑结构未知 不同位置上的独立输入 几个程序立即运行，在不同的时间开始，以不同的 速度运行 处理器的不确定性 不确定的消息传递次数 不确定的消息顺序 处理器和通信故障
洪泛算法的复杂度



定义终止状态为color = green的状态. 消息复杂度: 消息在每条边双向传递,故 共需2m个消息，其中m 为 边的个数 时间复杂度: 网络直径个时间单位
同步消息传递系统


在同步系统中，如果一个执行有无限“轮 (round)”，则称它是合法的执行 什么是“轮”? 执行按论划分，每一轮中:
round 1 events
round 2 events
p0
p2
p1
CPSC 668
34
Set 1: Introduction
同步洪泛算法的复杂度


时间复杂度为diameter 消息复杂度为2m 与异步算法相同. 只是特例，并不是所有算法都相同…
伪代码约定
在形式模型中，一个算法将根据状态转换 来描述。但实际上很少这样做，因为这样做 难于理解。 实际描述算法有两种方法：
幸运的是，并不是每个算法都要面对所有这些不确定性！！
6

分布式计算的特点




行为很难理解：多处理器并行执行，算法 存在多种不同表现。 准确预测算法的行为是不可能的。 否定结论、下界和不可能性结论增加 复杂度分析：通信开销（消息数），故障 单元和非故障单元的数量
7
研究分布式算法的方法



从各种分布式情况中提取基本问题，给出 形式化的数学模型 设计解决问题的分布式算法。 算法正确性证明
课程网站


分布协同计算基础
第二章:
分布式算法(1)
张锡哲 副教授 计算机应用技术研究所 东北大学信息科学与工程学院
主要内容

1.分布式算法概述 2. 形式化模型 3.消息传递系统基本算法

生成树上广播和敛播 生成树的构造

①叙述性：对于简单问题
②伪码形式：对于复杂问题
36
伪代码约定

异步算法：对每个处理器，用中断驱动来描述异步算法。 在形式模型中，每个计算事件 1 次处理所有输入缓冲区中的 msgs。而在算法中，一般须描述每个msg是如何逐个处理的 一个计算事件中的局部计算的描述类似于顺序算法的伪代码 描述

同步算法：逐轮描述

所有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: 2: terminate
例子 : 洪泛算法


将洪泛算法描述为状态机交互的集合. 进程的局部状态包括变量color={red，green} 初始: p0: color = green, 所有outbufs包含M others: color = red, 所有的outbufs 为空 转移函数: If M 在inbuf中并且 color = red, 那么 令color= green ,将M 发送至所有的outbufs
4.因果关系和时间 5.选举算法 6.容错一致性
1. 分布式算法概述
分布式计算的困难

异步

不能精确的知道事件发生的绝对时间，甚至相对时间
每个计算实体只知道它自己所获得的信息，只是全局 情况的一个局部视图。 由于系统各组件执行速度的差异,执行通常具有不确定 性 各计算实体可能独立发生故障

有限的局部知识

执行段是如下格式的序列：
C0 , 1 , C1 , 2 , C2 , 3 ,

其中每个Ck是一个配置，每个 k 是一个事件 执行是一个执行段 C0 , 1 , C1 , 2 , C2 , 3 , ,其中C0是初始配置。 调度σ是执行中的事件序列，即 1, 2 , 3 , . 如果局部程序是确定的，执行由初始配置C0和调度σ唯一 确定，表示为exec(C0, σ)


各处理器可以发送消息给每个邻居，消息被提 交； 每个处理器基于刚刚接收到的消息进行计算。

时间复杂度是在算法所有合法的执行中最 大的终止前轮数。
同步模型的例子

洪泛算法在同步系统中的执行 第一轮:



将M从p0提交到 p1 将M从p0提交到 p2 p0 does nothing p1 color=green，将M发送到 p0 and p2 p2 color=green，将M发送到 p0 and p1
15
提交事件

将消息m从进程pi提交到pj 将消息从发送者的outbufs移到接受者的 inbufs中; 消息将在下一次处理时可用
p1 m3 m2 m1 p2
p1
m3 m2
m1
p2
计算事 (局部变量+ 到来 消息) 将转移函数应用到进程的当前可存取状态， 处理所有的到来消息 以新的可存取状态结束，将inbufs清空，将新 消息放入outbufs中
不确定性



以上的执行不是洪泛算法在网络拓扑上的 唯一合法执行 合法执行有很多，依赖于消息提交的顺序 例如, p0 的消息可能在p1 消息前到达p2
终止性



为了模拟进程不发生故障，定义合法的执行的计 算事件是无限的 这样算法终止性如何表示？ 每个进程的状态集包括一个终止状态子集，并且 每个进程的转移函数将终止状态仅映射成终止状 态。 当所有进程处于终止状态并且没有消息在传送， 称算法已终止。
复杂性度量



集中考虑最坏情况 消息复杂度:算法所有合法的执行中最大的 发送消息总数。 时间复杂度: 任意合法执行中终止所需的最 大时间。 异步系统的时间复杂度如何衡量?
异步系统的时间复杂度




计时（timed）执行是指执行中每个事件关联一个 非负的实数，即事件发生的时间。 消息的延迟（delay ) ，是指在发送消息的计算事 件和处理消息的计算事件之间流逝的时间。 时间复杂度:所有计时的、合法的执行中，当各消 息延迟最多为1 时，在终止前的最大时间 这一度量仍然允许事件的任意交替，可以看做是 考虑了算法的任意执行，且进行了标准化，使最 长的消息延迟变成一个单位的时间。
例子: 洪泛算法(续)
p0 M M p2 M p0 M M p2 p1 M p1 M M M M p2 M p0 M p1 p0
deliver event at p1 from p2
computation event by p1
M
M
deliver event at p0 from p1
p2
p1
etc. to deliver rest of msgs

证明不可能性结果和下限，给出问题如何才能 可解的限制以及其求解代价。

算法复杂度分析。
8
2. 形式化模型
消息传递系统模型




消息传递系统模型由一组位于有向网络图节点位置 的计算元素组成。 表示为G(V,E),其中节点集V={p0, p1, …, pn-1 …}代表 进程的集合，边集E代表间的信道的集合。 每个进程pi用整数1~r标记与之相连的信道，其中r是 pi的度。 算法由各进程上的局部程序所组成。
异步执行

执行必须满足以下两个条件：


如果 k = del(i,j,m)，那么m必定是ck-1中outbufi[l] 的一 个元素，其中l是信道{pi, pj}中pi的标号。从ck-1到ck 的唯一改变是：在ck 中，m已从outbufi[l]中移走并加 入到inbufj[h] 中，其中h是信道{pi,pj }中pj的标号。 如果 k =comp(i)，那么从ck-1到ck的的唯一改变是：pi 依照其转移函数来改变状态，转移函数对ck-1 中pi 的 可存取状态进行操作，并将所确定的消息集合加入 到ck 的outbufi变量中，这些消息在这一事件上称为被 发送的。
计算事件
a b c d e
旧局部状态
新局部状态
执行

执行是随事件而改变的配置序列,其形式是:
配置, 事件,配置, 事件,配置, …


初始配置中: 每个进程都处于初始状态,所有的 inbufs都为空 对于每个连续配置(config, event, config), 新旧配 置不变，除非发生以下事件:
13
事件

系统中发生的事情用事件模拟，考虑两种 事件：

计算事件(Computational event)，表示为comp(i)
表示进程pi的处理步骤，将pi的转移函数应用到它当前 的可存取状态