分布式算法设计基础.doc

分布式算法设计基础课程学时数：每周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) 分布式文件维护 保持分布式文件系统的完整性和一致性 多处理器计算机1Transputer 计算机2Connection 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 一个变迁系统是一个三元组，其中，C 是一个形态的集合， 是C上的一个二元变迁关系，I 是C中初始形态的一个集合。变迁关系是CC的一个子集合，我们有时也用 来更方便地表达记号 。定义 2.2 令 是一个变迁系统，S的一次执行是一个形态的极大序列，其中，且对所有的 0， 。形态 称为终止形态，如果不存在形态 使得 。注意：对所有的i，具有 的一个序列 是极大的，如果它是无穷的，或者它以一个终止形态结束。定义 2.3 形态 是由 可达的，记为 ，如果存在一个序列： ，满足对所有的 0 i，或P()。定理2.17 设和P分别是给定的变迁系统和断言，如果S恰当地终止且一个范函数f（w.r.t P）存在，则P在S的每个执行的某个形态下为真。证明：设是一个变迁系统，是S的一次执行。如果E是有穷的，该执行的最后一个形态必是终止形态。S恰当地终止，term P 在S下总是为真，这样执行终止时term为真蕴涵了P在这个形态成立。如果E是无穷的，令E是E的不出现P为真的形态的最长(任意极大)前束(即子元组，可能为无穷)序列，且设s是在E中出现的所有形态序列i的范函数值的序列(f(0)，f(1)，f(2), ）。由E的选择和f存在及其性质，s是一个递减序列，因此，由W的良基集性质，s是有穷的。这也隐含了E是E的一个有穷的前束序列，是该执行中的最后一个非终止形态。再据E的选择可知，P(i+1)成立。 如果我们假定系统的公平性性质得到满足，那么，就能从较弱的前提推断P最终为真。范函数的值也不必随每次变迁递减。公平性假设常可以用来证明包含无穷特定类型的变迁，也就是在无穷执行中证明f决不会递增，它只可能随这种类型的每次变迁而递减。定理2.18 如果恰当终止且存在一个数k，使得每个执行至多包含k个变迁，则P在每个执行的某个形态下为真。证明：定理2.18是定理2.17的特殊情况。设和P分别是给定的变迁系统和断言，是S的一次执行。因S恰当终止且E中执行的变迁至多为k个，知E必为有穷。令E中最后得到执行的变迁为，于是就是终止形态。由term P和term在时为true，可得P在时成立，即P()=true。 3事件的因果序次序和逻辑时钟将分布式算法的行为看成是变迁序列自然涉及到时间。变迁a比变迁b早发生，如果在发生的顺序上a在b的前面发生。为了讨论事件之间的因果序关系，对一个执行，我们定义相伴事件序列，其中，ei是将形态由变到的事件。按照这种方式，每个执行就确定了唯一的一个事件序列。这样，一个执行就可以设想为下面图中的样子（时空图）：p1，p2，pN为进程，如上，a，b，c， 等为事件。如果消息m在事件s中被发送而在事件r中被接收，则从s到r画一个前头。（图略）我们很容易举出例子，说明一个分布式算法的执行中，某些事件的次序可以互换，不会影响该执行后面的形态和结果，而且，在实际的分布式计算中，我们无法找到一个办法，建立全局网上统一的、精确的物理时钟，也无法找到一个办法，建立检测全局网上统一的、精确的物理时钟的检测办法，从而也就难以真正弄清楚各个进程上事件发生的时间和次序。这说明单纯把时间作为总的次序的一种度量并不合适，应该考虑事件之间的因果序依赖关系。 事件的独立性与依赖性分布式系统中的变迁影响而且也仅受到形态的影响。因此，我们要注意相邻事件中形态不相关的那部分，它们是独立的，而且还可能以倒序发生，可以交换发生的次序，并不影响计算的结果。定理2.19 令为一个具有异步消息传递机制的分布式系统的形态，并设ep 和eq是两个不同进程p和q的事件，它们在下都是可应用的，则ep在eq()下是可应用的，eq在ep()下也是可应用的，且ep(eq()= eq(ep()。证明：我们用记号(c，x，y，d)表示每一个事件，这里，c和d分别表示事件之前和事件之后的进程状态，x是事件接收的消息集合，y是事件发送的消息集合，因此，内部事件(c，d)用(c，d)表示；一个发送事件(c，m，d)记为(c， m ，d)，而一个接收事件(c，m，d)记为(c， m ，d)。按照这种表示的记法，进程p的事件e =(c，x，y，d)在形态=(cp1，cp2 ，cp ，cpN，M)下是可应用的，如果cp = c且x M。在此情况下：E()=(cp1，cp2 ，d ，cpN，(M - x) y )现在假定ep = (bp，xp ，yp，dp) 和eq = (bq，xq ，yq，dq) 在= (，cp ， ，cq ，M) 下是可应用的，即cp = bp，cq = bq，xp M ，且xq M 。(两个消息可能相同，但目的地标识不同)。注意到xp和xq是不相交的，xp中的消息(如果有的话)目的地是p，而xq中的消息(如果有的话)目的地是q。我们记 = ep()且注意到 =(，dp，cq，(M- xp) yp)，当xq M 且xq xp = 时，可推断出xq (M- xp yp)，因此，eq 在下是可应用的。记 = eq()且注意到 =(，dp，dq，(M- xp) yp)- xq) yq)，由对称性的讨论可以证明：ep 在= eq()下是可应用的，记= ep()，且注意到 =(，dp，dq，(M- xq) yq)- xp) yp)，因为M是多消息集合，xp M ，且xq M，(M- xp yp)- xq yq)=(M- xq yq)- xp yp)，故 = 。 定理2.19的适用条件ep和eq是一次执行中相继出现的两个事件，即对某个，该执行包含子序列，ep()，eq(ep()，那么，定理2.19 的前提在应用到这些事件时排除了下列两种情况： p = q；或者 ep是发送事件，eq 是对应的接收事件。定理2.19明确地说明了p和q必须是不同的进程。如果eq接收ep发送的消息，那么，接收事件在ep的开始形态下是不能应用的，这就说明了如果两个事件在执行中不能交换，那么，这两个事件之间就存在一种因果序关系。这种关系可以扩展为一次执行事件上的偏序，称为执行的因果序。定义2.20 令E为一次执行，E的事件集上称为因果序的关系 是满足下列条件的最小关系： 如果e和f是同一进程的不同事件，且e在f之前出现，则e f ； 如果s是一个发送事件，r是相应的接收事件，s r ； 是传递的。我们用a b 表示(a b或者a = b)。当是一个偏序时，有可能存在事件a和b，既不满足a b，也不满足b a，这样的事件称为是并发的，用ab来表记。如图2.1中的 bf 和 dl 等。Lamport1978年首先定义了事件的因果序并在有关的分布式算法的研究中起了重要作用。 的定义隐含了因果关联的事件之间因果链的存在性，据此，我们可以说a b隐含了存在一个序列a = e0，e1，e2，ek = b使得该链中相继出现的每对事件满足定义2.20中的或者，图2.1中a，f，g，h，j，k，l是一个因果链。 执行的等价性：计算下面考虑这样一个问题：一次执行的多个事件能够以任何与因果序一致的序被重新排序，但不会影响其执行的结果。对事件进行重新排序，会生成不同的形态序列，但只要结果不变，该执行将被视为与原执行等价。设是一个事件序列，该序列是一个与执行相关联的事件序列。如果对每个i，在下是可应用的且=。在这种情况下，F被称为是f的隐含执行。我们希望f唯一地确定F，但实际情况并非总是如此，取决于是否有一致的因果序。如果对某个进程p，p中的事件没有一个包含在f中，那么，p的状态可以是任意的初始状态。然而，如果f包含了至少一个p的事件，则p中的第一个事件，不妨设为(c，x，y，d)，实际上就定义了p的初始状态将是c。因此，如果f至少包含每个进程的一个事件，就将被唯一地确定，而这就唯一地确定了整个执行。设为一次执行，E的相伴事件序列，且假设事件序列f是的一个置换，即存在非负整数的一个置换(或者存在0，1，2，3，k -1的一个排列，若E是有k个事件的有穷执行)使得 。E的事件的置换与因果序是一致的，如果蕴涵，即没有一个事件在序列中排在它按照因果顺序排列的位置前面。定理2.21 设是的伴随事件的一个置换或排列，它与的因果序一致，则f确定了从E的初始形态开始的唯一执行F，F具有与E同样多的事件，且若E是有穷的，那么F的最后形态与E的最后形态是相同的。证明：的形态是一步一步构造的。为了构造，必须表明在下是可应用的。取。假设对所有的ji, 在形态下是可应用的，且=。令=(cp1，cp2 ，cpN，M)，且设=(c，x，y，d)为进程p中的一个事件，如果，cp = c，则事件在是可应用的。为了证明cp = c，我们分两种情况：情况1. 是f在p中的第一个事件，则cp是p的初始状态，而也是在p中的第一个事件，这就是说c是p的初始状态，故c=cp 。情况2. 不是f在p中的第一个事件，设之前f在p中的最后一个事件为=(c，x，y，d)，则cp = d，而也是中之前p中的最后一个事件，这就是说c = d，故c=cp 。注意：我们讨论的是f在p中的位于之前的最后一个事件，也是中在之前p中的最后一个事件，关键一点在于p中。如果不在p中，而是在另一进程q中，则将转到q中的状态上去处理。为了证明x M，我们注意到对应的发送和接收事件在f和中以相同的序出现，若不是接收事件，则x = 且x M显然成立；若是接收事件，令为对应的发送事件，因，ji，即发送事件在f中先于接收事件发生，可知x M。至此，我们已经说明了对于每个i，在下是可应用的，而可作为产生。最后，我们还要证明F和E的最后形态相重合，如果E是有穷的话。设为E的最后一个形态，如果不包含p中的事件，则中p的状态等于它的初始状态，如同f也不包含p中的事件一样，(它一步一步由变过来)中p的状态也等于初始状态，因此，中p的状态等于中它的状态；否则，中p的状态是在p中最后事件后面的状态，该事件也是f在p中的最后事件，所以，该状态也是在p中的状态。中变迁传递的消息确实是那样一些消息，发送消息的事件并不与中对应的接收事件匹配，但如同和f包含相同的事件集合一样，相同的消息以变迁的形式都在f的最后形态中。 执行E和F隐含具有相同的事件集合，而这些事件的因果序对于E和F来说是相同的。因此，是F隐含的事件的一个置换，它与F的因果序一致，由定理2.21，称E和F是等价执行，记为E F。问题：两个等价的执行是否包含相同的事件集合，它们是否包含相同的形态集合？答：不一定包含相同的事件集合(要放在不同的计算方法上理解，此处等价计算包含相同的事件集合)，自然也不一定包含相同的形态集合。如果计算方法相同，则包含相同的事件集合，但不一定包含相同的形态集合，因为有些事件是可以交换执行顺序的。只要初始形态和最终形态相同，两者之间是执行等价的。注意：进程是局部的概念，而形态才是全局的概念。 显然是一个等价关系，由事件集和这些事件上的因果序可以完整地刻画关于 的等价类，这种等价类称为算法的计算，它们完整地刻画了算法所有可能的执行语义序列(操作语义)和算法的设计。定义2.22 一个分布式算法的计算是该算法执行(在 下)的一个等价类。单纯讨论一个形态是没有意义的，因为计算的不同执行不可能有相同的形态。但讨论一个计算的事件集合是有意义的，因为该计算的所有执行都是由相同的事件集合组成的。偏序理论的一个结果隐含了对一个计算的一对并发事件来说，每个序都能发生。该扩充在保留原来序关系的前提下，对原来没有偏序关系的元素之间建立了一个偏序关系，见事实2.3。事实2.3 设（X，）为一个偏序，a，b X，满足b a，则存在一个的线性扩充1，使得a 1 b 。如果a和b是计算C的两个并发事件，该计算存在两个执行Ea和Eb，使得在Ea中a先于b发生，而在Eb中b先于a发生，则执行中的进程要确定这两个事件哪个先发生是没有意义的，即不必确定。 同步消息传递类似于定理2.19，我们也可以导出具有同步消息传递功能的分布式系统的定理结论。定理2.24 令为一个具有同步消息传递机制的分布式系统的形态，并设e1为进程p和q的一个变迁，且e2为不同于p和q的进程r和s的一个变迁，使得满足e1和e2在 下是可应用的，则e1在e2（）下是可应用的，e2在e1（）下也是可应用的，且e1（e2（）= e2（e1（） 。证明留给大家。 这个定理的证明类似于定理2.19证明的讨论，但要注意证明中e1和e2是两个同步事件，只是它们在两对不同的进程中实现同步，这两对进程不存在进程交叉执行的情况。 逻辑时钟在分布式计算中，我们将时钟表示为一种因果序关系。先引入记号：Q，它是一个事件集合到偏序集合（X，）的映射函数。定义2.25 时钟是一个从事件集合到偏序集合的映射函数Q，满足：ab Q(a) Q(b) 。其中， 是事件集合上的因果序关系，是并发事件集合上的时钟序关系。(1) 按顺序排列的次序设一个执行E对应的事件序列为，设Qg(ei)= i ，满足要求。(2) 实时时钟可对此模型进行扩充，为每一个进程提供一个硬件时钟。用这种方法，可记录每一个事件发生的真实物理时间，其数值也满足时钟的定义。注意：实时时钟的分布式系统不适合定义2.6。(3) Lamport逻辑时钟Lamport提出一个时钟函数，它赋予事件a长度k，其中，k表示最长事件序列(e1 ， ，ek )的长度，满足：e1 e2 ek = a不难看出，如果a b，该序列可以扩展表示成QL(a) Q L(b)。QL的值可由一个分布式算法根据下列关系计算得到（见书）：(a) 如果a是一个内部事件或发送事件，且a是同一进程中的前驱事件，则QL(a)= QL(a) + 1(b) 如果a是一个接收事件，a是同一进程中的前驱事件，且b是与a对应的发送事件，则QL(a)= max QL(a)，QL(b) + 1 算法2.3（直接根据书本讲解）(4) 向量时钟在某些应用中，拥有不仅能表达因果序而且也能表达并发性的时钟是有用的。如果并发事件用唯一的时钟值标记，我们就可以用一个时钟表示并发性，即隐含了用等价代替定义2.25的关系：ab Q(a) Q(b)这样，并发事件的存在就意味着这样一个时钟的定义域（集合X）是一个非全序集合。在Mattern的向量时钟Mat89b X=NN中（N是进程的个数），Qv(a)是长度为N的一个向量。长度为n的向量是按照该向量的序自然排序的，定义如下：（a1，an）（b1，bn） i（1 i n）: ai bi注意，向量序不同于字典序，后者是一个全序，而前者不同的向量之间可能不可比较大小。时钟按照下式定义：Qv(a) =（a1，aN），其中，ai为进程pi中具有e a 的事件e的数目。就象Lamport的时钟一样，该时钟函数也能在分布式算法中求值，更短的向量时钟见Charron-Bost。思考：向量函数时钟初值是什么？如何存储时钟值，什么时候表现出并发？如何设计计算向量时钟的算法？4附加的假设、复杂性分布式计算模型的作用：为引入、介绍和验证算法提供了一个框架，也提供了分布式问题求解不可能性证明的一个框架。下面介绍常用术语和假设。4.1网络拓扑结构 每个消息只能由消息目的地的单个进程接收。 如果进程p能够将消息发送给进程q，那么，称从p到q存在一个通道。除非另有说明，否则通道均是双向的。只能容纳一路单向通信的通道称为是单向或有向通道。 一个分布式系统的进程间的通信互连关系图也叫做它的网络拓扑结构。本书中的图都是连通的。环、树、星型、集团、超立方体等图论的概念请大家自己复习。网络的拓扑结构可以是静态的，也可以是动态的。4.2 通道的性质通过在形态中分别表示每个通道的内容可以对计算模型进行细化，也就是对每一个通道pq，我们用若干集合Mpq 的集合来代替集合M。这样做，无非是要求消息的目的地明确的另一种形式，并不能改变该模型的重要性质。 可靠性一个通道是可靠的，如果该通道中被发送的消息在消息的目的地能接收的前提下严格地被接收一次。这一点由体系结构保证。 先进先出性质每个通道是一个队列。另外，可以有因果序投递假设，也可以有分层投递假设。 通道容量容量是指同一段时间段内可以传递的消息的数目，类似与操作系统中的共享存储区，存在满和空的情况。4.3 实时性假设本书中定义2.6的计算模型的一个基本性质是模型的分布性，即不同进程中的事件是完全独立的，除了外部事件之外。4.4 进程知识进程的网络知识主要包括以下内容： 拓扑信息 进程标识 邻居标识4.5 分布式算法的复杂性分析正确性是分布式算法最重要的性质，其次还需要对算法进行复杂性分析。 消息复杂性 位复杂性 时间复杂性 处理一个事件的时间为0时间单位 传输时间（发送或接收一条消息）最多为一个时间单位。 空间复杂性算法的空间复杂性等于执行算法的进程所需存储量的大小。进程所需的空间是进程状态数的对数。