分布式算法.ppt

分布式算法
§ 理论和实际之关系
错误的种类
Crash failure崩溃错误
指处理机没有任何警告而在某点上停止操作。
Byzantine failure拜占庭错误
一个出错可引起任意的动作
8
Ch.,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。
18
§ 系统
执行：一个执行是一个执行片断C0, Φ1, C1, Φ2, … ,这里C0是一个初始配置。
调度：一个调度(或调度片段)总是和执行(或执行片断)联系在一起的，它是执行中的事件序列：Φ1, Φ2, … 。
并非每个事件序列都是调度。例如，del(1,2,m)不是调度，因为此事件之前，p1没有步骤发送(send)m。
若局部程序是确定的，则执行(或执行片断)就由初始配置C0和调度(或调度片断)σ唯一确定，可表示为exec(C0 , σ)。
19
§ 系统
容许执行：(满足活跃性条件)
异步系统中，若某个处理器有无限个计算事件，每个发送的msg都最终被传递，则执行称为容许的。
Note: 无限个计算事件是指处理器没有出错，但它不蕴含处理器的局部程序必须包括一个无限循环
非形式地说：一个算法终止是指在某点后转换函数不改变处理器的状态。
容许的调度：
若它是一个容许执行的调度。
20
§ 系统

在同步模型中，处理器按锁步骤(lock-step)执行：
执行被划分为轮，每轮里，①每个处理器能够发送一个msg到每个邻居，这些msg被传递。②每个处理器一接到msg就进行计算。
虽然特殊的分布系统里一般达不到，但这种模型对于设计算法非常方便，因为无需和更多的不确定性打交道。当按此模型设计算法后，能够很容易模拟得到异步算法。
轮：在同步系统中，配置和事件序列可以划分成不相交的轮，每轮由一个传递事件(将outbuf的消息传送到信道上使outbuf变空)，后跟一个计算事件(处理所有传递的msg)组成。
21
§ 系统
容许的执行：指无限的执行。
因为轮的结构，所以
每个处理器执行无限数目的计算步，
每个被发送的msg最终被传递
同步与异步系统的区别
在一个无错的同步系统中，一个算法的执行只取决于初始配置
但在一个异步系统中，对于相同的初始配置及无错假定，因为处理器步骤间隔及消息延迟均不确定，故同一算法可能有不同的执行。
22
§ 复杂性度量
分布式算法的性能：msg个数和时间。
最坏性能、期望性能
终止：假定每个处理器的状态集包括终止状态子集，每个的pi的转换函数对终止状态只能映射到终止状态
当所有处理机均处于终止状态且没有msg在传输时，称系统(算法)已终止。
算法的msg复杂性(最坏情况)：算法在所有容许的执行上发送msg总数的最大值(同步和异步系统)
23
§ 复杂性度量
时间复杂度
①同步系统：最大轮数，即算法的任何容许执行直到终止的最大轮数。
②异步系统：假定任何执行里的msg延迟至多是1个单位的时间，然后计算直到终止的运行时间
计时执行(timed execution)
指：每个事件关联一个非负实数，表示事件发生的时间。时间起始于零，且须是非递减的。但对每个单个的处理器而言是严格增的。
若执行是无限的，则执行的时间是无界的。因此执行中的事件可根据其发生时间来排序
不在同一处理器上的多个事件可以同时发生，在任何有限时间之前只有有限数目的事件发生。
24
§ 复杂性度量
消息的延迟
发送msg的计算事件和处理该msg的计算事件之间所逝去的时间
它主要由msg在发送者的outbuf中的等待时间和在接收者的inbuf中的等待时间所构成。
异步算法的时间复杂性
异步算法的时间复杂性是所有计时容许执行中直到终止的最大时间，其中每个msg延时至多为1。
25
§ 伪代码约定
在形式模型中，一个算法将根据状态转换来描述。但实际上很少这样做