(分布式算法.doc

分布式算法设计基础 赵致琢 博士 教授 （厦门大学计算机科学系） 课程学时数：每周4学时 Gerard Tel，《Introduction to Distributed Algorithms(Second Edition)》? Agent（软计算结点）? 网络计算 ? 网格计算 选择分布式系统的动机 (1) 信息交换 (2) 资源共享 (3) 通过重复提高可靠性 (4) 通过并行化提高性能 (5) 通过专门化简化设计 (6) 问题本身的特点决定 计算机网络 计算机网络是用通信机构连接的一个计算机的集合。计算机相互之间能够交换信息。通信机构、计算机集合之间可能分别有层次之分，它们之间的某些互连关系、控制关系等形成了分布式网络体系结构。 计算机网络的类型： 局域网：主要目的是交换信息和协同计算 广域网：主要目的是交换信息和资源共享 两种网络之间并没有严格的界限。从算法的角度看，如果不考虑实现，没有必要严格区分。对分布式算法而言，两种网络可能影响的差别因素主要包括： (1) 可靠性参数 (2) 通信时间(包括通信延迟) (3) 同种(齐性)或异质(非齐性) (4) 相互间的信任 广域网络(略) 广域网络的组织结构和算法问题 互连方式一般是采用点对点方式连接，两个结点之间的通信总是通过专属于这个结点的一个机制进行，可以是电话线、光纤等。互连结构在数学上可以抽象为图论中的无向或有向图，故有关图论的基础理论和计算方法广泛应用于分布式系统的研究与开发。为了实现可靠的信息交换，需要解决下列算法问题： (1) 点对点数据交换的可靠性 用通信协议保证，要考虑容错能力 (2) 通信路径的选择 用路由协议算法保证 (3) 拥挤控制 采用中心结点机的控制或分散控制策略 (4) 防止死锁 死锁预防和死锁检测 (5) 必威体育官网网址 数据加密、身份认证技术、防入侵检测技术等 以上仅涉及网络组织结构方面必须解决的问题，属系统层面而非应用层面的问题。应用层面的问题由具体问题处理算法的计算方法和算法来负责解决。 局域网（略） 局域网络的组织结构和算法问题 组织结构：一般为总线连接，每个进程每次只能发送一个消息，在此基础上可发展进程级模拟通信系统。早期的局域网一般采用总线结构，但并非所有的局域网都使用总线结构，如IBM的SNA，可构建局域网。 局域网的计算需要解决下列算法问题： (1) 广播与同步 广播通信与同步算法 (2) Election—投票，即选择某个进程解决某个任务 (3) 终止性检测 检测某个处理机(或进程任务是否已 经完成或终止执行) (4) 资源分配 分配网络上的各种资源 (5) 互斥 对某些共享资源进行互斥管理 (6) 死锁检测和化解 (7) 分布式文件维护 保持分布式文件系统的完整性 和一致性 多处理器计算机 1．Transputer 计算机 2．Connection Machine (连接机器) node：一个快速处理器，结点内部具有并行处理方式。 一个向量处理部件，可以构成外部并行处理方式。 多处理器计算机设计的一种非常流行的处理器是Transputer片： 包含：一个CPU，一个专用浮点处理部件FPU，一个局部存储器，四个专用的通信处理器 这样一个Transputer片子很容易与四个片子相连构成四度网络，内部采用CSP理论(通信顺序进程)与技术。 Connection Machine机器除了由许多结点提供并行处理方式外，还提供了结点的内部(向量)并行处理方式。 3．机群系统 目前在硬件技术上已经相当成熟。 多处理器计算机(包括多计算机系统)的构造需要解决几个算法问题，其中一些类似于网络中的问题： (1) 消息传递系统的实现 (2) 虚拟共享存储的实现 (3) 负载平衡 与应用密切相关 (4) 防不可检测故障的鲁棒性 合作处理 将复杂计算的设计构造成一个合作处理的多处理器(机)集合可能更好。但须考虑： (1) 存储操作的原子性 (2) 生产与消费问题 (3) 废料回收 通过共享存储器实现进程之间的通信可解决上述问题，但需要操作系统和程序设计环境提供： (1) 信号灯 (2) 管程 (3) 管道 (4) 消息发送 (5) 远程访问 体系结构 一个分布式系统的通信子系统在执行任务时的复杂性决定了子系统的设计需要实现分层，由多层协议来分担执行网络通信的任务，由此形成了网络的通信协议技术。 ISO组织提出网络开放系统互连的七层协议(OSI) 语言支持 并行与分布式程序设计语言，具有下列表达能力 (1) 并行 (2) 通信 (3) 非确定性 分布式算法 无论一个分布式系统如何设计，采用何种开发方法进行设计，也无论整个系统的架构如何设计，作为支撑分布式计算的核心基础和技术，分布式算法在分布式系统