算法设计与设计课件2.ppt

第二部分 分布式算法 黄刘生 中国科学技术大学计算机系 国家高性能计算中心（合肥） 2008.10 Ch.1 导论 §1.1 分布式系统 Def：一个分布式系统是一个能彼此通信的单个计算装置的集合（计算单元：硬——处理器；软——进程） 包括：紧耦合系统----如共享内存多处理机 松散系统-----cow、Internet 与并行处理的分别(具有更高程度的不确定性和行为的独立性) 并行处理的目标是使用所有处理器来执行一个大任务 而分布式系统中，每个处理器一般都有自己独立的任务，但由于各种原因（为共享资源，可用性和容错等），处理机之间需要协调彼此的动作。 分布式系统无处不在，其作用是： ①共享资源 ②改善性能：并行地解决问题 ③改善可用性：提高可靠性，以防某些成分发生故障 §1.1 分布式系统 分布式系统面临的困难 异质性：软硬件环境 异步性：事件发生的绝对、甚至相对时间不可能总是精确地知道 局部性：每个计算实体只有全局情况的一个局部视图 故障：各计算实体会独立地出故障，影响其他计算实体的工作。 §1.2 分布式计算的理论 目标：针对分布式系统完成类似于顺序式计算中对算法的研究 具体：对各种分布式情况发生的问题进行抽象，精确地陈述这些问题，设计和分析有效算法解决这些问题，证明这些算法的最优性。 计算模型： 通信：计算实体间msg传递还是共享变量？ 哪些计时信息和行为是可用的？ 容许哪些错误 复杂性度量标准 时间，空间 通信成本：msg的个数，共享变量的大小及个数 故障和非故障的数目 §1.2 分布式计算的理论 否定结果、下界和不可能的结果 常常要证明在一个特定的分布式系统中，某个特定问题的不可解性。 就像NP-完全问题一样，表示我们不应该总花精力去求解这些问题。 当然，可以改变规则，在一种较弱的情况下去求解问题。 我们侧重研究： 可计算性：问题是否可解？ 计算复杂性：求解问题的代价是什么？ §1.3 理论和实际之关系 主要的分布式系统的种类，分布式计算理论中常用的形式模型之间的关系 种类 支持多任务的OS：互斥，死锁检测和防止等技术在分布式系统中同样存在。 MIMD机器：紧耦合系统，它由分离的硬件运行共同的软件构成。 更松散的分布式系统：由网络（局域、广域等）连接起来的自治主机构成 特点是由分离的硬件运行分离的软件。实体间通过诸如TCP/IP栈、CORBA或某些其它组件或中间件等接口互相作用。 §1.3 理论和实际之关系 模型 模型太多。这里主要考虑三种，基于通信介质和同步程度考虑。 异步共享存储模型：用于紧耦合机器，通常情况下各处理机的时钟信号不是来源于同一信号源 异步msg传递模型：用于松散耦合机器及广域网 同步msg传递模型：这是一个理想的msg传递系统。该系统中，某些计时信息（如msg延迟上界）是已知的，更实际系统能够模拟同步msg传递模型。 该模型便于设计算法，然后将其翻译成更实际的模型。 §1.3 理论和实际之关系 错误的种类 Crash failure崩溃错误 指处理机没有任何警告而在某点上停止操作。 Byzantine failure拜占庭错误 一个出错可引起任意的动作 Ch.2 消息传递系统中的基本算法 本章介绍无故障的msg传递系统，考虑两个主要的计时模型：同步及异步。 定义主要的复杂性度量、描述伪代码约定，最后介绍几个简单算法 §2.1 消息传递系统的形式化模型 §2.1.1 系统 1.基本概念 拓扑：无向图 结点——处理机 边 ——双向信道 §2.1.1 系统 算法：由系统中每个处理器上的局部程序构成 局部程序 执行局部计算——本地机器 发送和接收msg——邻居 形式地：一个系统或一个算法是由n个处理器p0, p1,…pn-1构成，每个处理器pi可以模型化为一个具有状态集Qi的状态机（可能是无限的） §2.1.1 系统 状态（进程的局部状态） 由pi的变量，pi的msgs构成。 pi的每个状态由2r个msg集构成： outbufi[l](1≤l≤r): pi经第l条关联的信道发送给邻居，但尚未传到邻居的msg。 inbufi[l](1≤l≤r): 在pi的第l条信道上已传递到pi，但尚未经pi内部计算步骤处理的msg。 模拟在信道上传输的msgs §2.1.1 系统 初始状态： Qi包含一个特殊的初始状态子集：每个inbufi[l]必须为空，但outbufi[l]未必为空。 转换函数(transition)： 处理器pi的转换函数(实际上是一个局部程序) 输入：pi