文档介绍：第二部分分布式算法
黄刘生
中国科学技术大学计算机系
国家高性能计算中心(合肥)
1
导论
§ 分布式系统
Def:一个分布式系统是一个能彼此通信的单个计算装置的集合(计算单元:硬——处理器;软——进程)
包括:紧耦合系统----如共享内存多处理机
松散系统-----cow、
与并行处理的分别(具有更高程度的不确定性和行为的独立性)
并行处理的目标是使用所有处理器来执行一个大任务
而分布式系统中,每个处理器一般都有自己独立的任务,但由于各种原因(为共享资源,可用性和容错等),处理机之间需要协调彼此的动作。
分布式系统无处不在,其作用是:
①共享资源
②改善性能:并行地解决问题
③改善可用性:提高可靠性,以防某些成分发生故障
2
§ 分布式系统
分布式系统面临的困难
异质性:软硬件环境
异步性:事件发生的绝对、甚至相对时间不可能总是精确地知道
局部性:每个计算实体只有全局情况的一个局部视图
故障:各计算实体会独立地出故障,影响其他计算实体的工作。
3
§ 分布式计算的理论
目标:针对分布式系统完成类似于顺序式计算中对算法的研究
具体:对各种分布式情况发生的问题进行抽象,精确地陈述这些问题,设计和分析有效算法解决这些问题,证明这些算法的最优性。
计算模型:
通信:计算实体间msg传递还是共享变量?
哪些计时信息和行为是可用的?
容许哪些错误
复杂性度量标准
时间,空间
通信成本:msg的个数,共享变量的大小及个数
故障和非故障的数目
4
§ 分布式计算的理论
否定结果、下界和不可能的结果
常常要证明在一个特定的分布式系统中,某个特定问题的不可解性。
就像NP-完全问题一样,表示我们不应该总花精力去求解这些问题。
当然,可以改变规则,在一种较弱的情况下去求解问题。
我们侧重研究:
可计算性:问题是否可解?
计算复杂性:求解问题的代价是什么?
5
§ 理论和实际之关系
主要的分布式系统的种类,分布式计算理论中常用的形式模型之间的关系
种类
支持多任务的OS:互斥,死锁检测和防止等技术在分布式系统中同样存在。
MIMD机器:紧耦合系统,它由分离的硬件运行共同的软件构成。
更松散的分布式系统:由网络(局域、广域等)连接起来的自治主机构成
特点是由分离的硬件运行分离的软件。实体间通过诸如TCP/IP栈、CORBA或某些其它组件或中间件等接口互相作用。
6
消息传递系统中的基本算法
本章介绍无故障的msg传递系统,考虑两个主要的计时模型:同步及异步。
定义主要的复杂性度量、描述伪代码约定,最后介绍几个简单算法
§ 消息传递系统的形式化模型
§ 系统
拓扑:无向图结点——处理机
边——双向信道
9
§ 系统
算法:由系统中每个处理器上的局部程序构成
局部程序执行局部计算——本地机器
发送和接收msg——邻居
形式地:一个系统或一个算法是由n个处理器p0, p1,…pn-1构成,每个处理器pi可以模型化为一个具有状态集Qi的状态机(可能是无限的)
10