分布式算法设计基础课程学时数：每周4学时Gerard Tel，《Introduction to Distributed Algorithms(Second Edition)》，1999分布式算法导论（第二版）（英文版）外语水平高的可以直接用原版教材，其他同学可以中文版为主，参考原版教材。

第一章分布式系统分布式算法的研究，来源于分布式系统开发活动中的基础研究，其内容构成了分布式计算的核心技术。

1.1什么是分布式系统？定义.一个分布式系统是指以某种方式合作的若干计算机或处理器上的所有计算机应用。

该定义覆盖：广域计算机通讯网络、局域网、每个处理器具有自己控制部件的多处理器计算机，以及合作、协同处理系统。

术语：“分布式系统”一般是指自治计算机、进程和处理器的集合。

作为分布式系统的一个结点，计算机、进程、处理器，每一个都是自治的，它们都必须有自己的控制。

分布式系统与并行计算机体系结构之间的联系：SISD(传统机器，不是)；MISD（没有对应的系统）；SIMD(不是)；MIMD(是): 要求各结点具有并发或并行执行的能力，交换信息的能力。

进程能够起到一个分布式系统结点的作用，单机上的多进程系统是分布式系统的早期雏形，也归属于分布式系统的范畴，是分布式系统的特殊情况。

除了单机上的分布式系统之外，大多数情况下，一个分布式系统至少包含n个由通讯硬件互联在一起的处理器，包括现在的多核系统。

在分布式系统中，进程与1980年代早期出现的Agent 之间存在密切的联系，是Agent实现的重要支撑技术。

进程→ 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)非确定性●分布式算法无论一个分布式系统如何设计，采用何种开发方法进行设计，也无论整个系统的架构如何设计，作为支撑分布式计算的核心基础和技术，分布式算法在分布式系统开发和分布式应用中担当了十分重要的角色，其或者独立、完整地出现在某一层软件之中，也可能内嵌在整个分布式系统之中。

其中，分布式基础算法具有特别重要的作用，因为大量分布式计算提出的问题，往往具有共同的特性、特点和相似性，解决这些问题在方法论上归结为一些分布式基础算法的研究。

分布式算法与顺序算法(或集中式算法)的比较(1) 缺乏全局状态知识(2)缺乏全局时钟框架(3)非确定性与通信延迟(4)故障与容错(5)高性能计算带来的计算密集性、数据密集性、通信密集性问题，引发的可信计算问题等高性能计算：计算密集性、数据密集性、通信密集性1.2分布式程序设计环境(1) 以程序设计语言为基础的环境如并发Pascal，CSP，Ada，等等(2) 分布式程序设计的环境在操作系统上增加一层分布式(并行)程序设计环境，将一批系统调用向用户开放，如增加UNIX系统调用，PV/M、MPI机制和功能等，支持分布式(并行)程序设计。

(3) 支持分布式程序设计和集成软件开发的环境CORBA，COM .NET，J2EE等(4) 支撑分布式程序设计与软件开发的方法学OOP，组件软件开发方法，软件重用，软件系统架构等1.3分布式算法的理论基础算法的研究，离不开抽象的计算模型，分布式算法也不例外。

为了便于算法的分析、理解、设计、比较和对算法的性质进行比较、分析、研究，有必要引入和发展恰当的分布式计算模型，使得算法能够在抽象的分布式计算模型上运行，便于对算法进行性能分析。

于是，分布式计算模型就成为分布式算法研究的一个切入点。

第二章 分布式计算模型研究计算，离不开计算模型。

计算模型有不同层次之分。

此处介绍的计算模型，是指具有状态转换机制的能够支撑分布式算法运行的抽象数学模型——分布式数学机器。

1． 变迁系统与分布式算法一个系统如果它的状态变化是离散的，状态的改变由事件驱动，通常可以用变迁系统来描述。

观察计算，可以从函数计算、计算前后必须满足的条件(逻辑公式刻画)、代数运算的角度进行，也可以从语言操作指令执行的前后状态变化的角度进行。

如果从状态变化的角度进行观察，就必须要建立一种数学机器模型，能够严格、准确地执行语言的操作指令。

这样一种机器，通常称为计算模型。

∙ 变迁系统变迁系统由系统所有可能的状态的集合构成，系统的“变迁”可以在此状态集合中进行。

一个选定的状态的子集合中的每一个状态可以使系统启动，这个子集合称为初始状态集合。

在分布式系统中，系统的分布式算法的一个状态通常由构成该系统分布式算法的所有进程的状态和通道的状态组成，为了避免系统中单个进程的状态和整个分布式系统的分布式算法状态之间产生混淆，我们今后将把单个进程的“状态”称为状态，将分布式算法的“全局状态”称为形态（Configuration ）。

定义 2.1 一个变迁系统是一个三元组),,(I C S →=，其中，C 是一个形态的集合，→ 是C 上的一个二元变迁关系，I 是C 中初始形态的一个集合。

变迁关系是C ×C 的一个子集合，我们有时也用 ∈→),(δγ 来更方便地表达记号δγ→ 。

定义 2.2 令 ),,(I C S →= 是一个变迁系统，S 的一次执行是一个形态的极大序列...)(210，，，γγγ=E ，其中，I ∈0γ，且对所有的 i ≥0，1+→i i γγ 。

形态 γ 称为终止形态，如果不存在形态 δ 使得 δγ→ 。

注意：对所有的i ，具有1+→i i γγ 的一个序列...)(210，，，γγγ=E 是极大的，如果它是无穷的，或者它以一个终止形态结束。

定义 2.3 形态 δ 是由 γ 可达的，记为 γ⇝δ，如果存在一个序列： )(210δγγγγγ==k ，，，， ，满足对所有的 0 ≤i < k ，1+→i i γγ 。

形态 δ 是由可达的，如果 δ 可以由一个初始形态可达。

∙ 具有异步消息传递机制的变迁系统一个分布式系统由一组进程和一个通信子系统组成，每一个进程本身是一个变迁系统，并能够与通信子系统交互。

为了避免分布式系统的属性和单一进程的属性之间发生混淆，我们约定：术语“变迁”和“形态”用于整个系统的属性描述，而(另一等价的)术语“事件”和“状态”用于进程的属性的描述。

为了与通信系统交互，一个进程的内部不仅有通常的事件，而且还有发送事件和接收事件，消息会被产生或被消费。

设M 表示一个可能的消息的集合，M (M)表示由多个M 的消息集合组成的集合(注：此处为集合的集合，但不是指幂集合)。

定义 2.4 一个进程的局部算法是一个五元组(Z, I, ⊢i , ⊢s , ⊢r )，其中，Z 是一个状态的集合，I 是Z 中初始状态的一个子集合，⊢i 是Z×Z 上的一个关系，⊢s 和 ⊢r 是Z×M ×Z 上的关系。

Z 上的事件关系 ⊢ 定义为：c ⊢d ⇔ (c,d) ∈ ⊢i ∨ ∃m ∈ M((c ，m ，d )∈ ⊢s ∪ ⊢r )关系⊢i 、⊢s 、⊢r 分别对应于进程的内部事件、发送事件和接收事件。