分布式算法设计基础(第二章)

分布式算法导论,中文电子版,厦大赵致琢教授课件,有些内容做了改动。

分布式算法设计基础

第二章 分布式计算模型

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

1． 变迁系统与分布式算法

一个系统如果它的状态变化是离散的，状态的改变由事件驱动，通常可以用变迁系统来描述。观察计算，可以从函数计算、计算前后必须满足的条件(逻辑公式刻画)、代数运算的角度进行，也可以从语言操作指令执行的前后状态变化的角度进行。如果从状态变化的角度进行观察，就必须要建立一种数学机器模型，能够严格、准确地执行语言的操作指令。这样一种机器，通常称为计算模型。 变迁系统

变迁系统由系统所有可能的状态的集合构成，系统的“变迁”可以在此状态集合中进行。一个选定的状态的子集合中的每一个状态可以使系统启动，这个子集合称为初始状态集合。

在分布式系统中，系统的分布式算法的一个状态通常由构成该系统分布式算法的所有进程的状态和通道的状态组成，为了避免系统中单个进程的状态和整个分布式系统的分布式算法状态之间产生混淆，我们今后将把单个进程的“状态”称为状态，将分布式算法的“全局状态”称为形态（Configuration）。 定义 2.1 一个变迁系统是一个三元组S (C, ,I)，其中，C 是一个形态的集合， 是C上的一个二元变迁关系，I 是C中初始形态的一个集合。

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

定义 2.2 令 S (C, ,I) 是一个变迁系统，S的一次执行是一个形态的极大序列E ( 0， 1， 2，...)，其中， 0 I，且对所有的 i≥0， i i 1 。 形态 称为终止形态，如果不存在形态 使得 。 注意：对所有的i，具有 i i 1 的一个序列E ( 0， 1， 2，...) 是极大的，如果它是无穷的，或者它以一个终止形态结束。

定义 2.3 形态 是由 可达的，记为 ，如果存在一个序列： ( 0， 1， 2， ， k ) ，

满足对所有的 0 ≤i< k ， i i 1 。

形态 是由可达的，如果 可以由一个初始形态可达。 具有异步消息传递机制的变迁系统

分布式算法导论,中文电子版,厦大赵致琢教授课件,有些内容做了改动。

一个分布式系统由一组进程和一个通信子系统组成，每一个进程本身是一个变迁系统，并能够与通信子系统交互。

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

为了与通信系统交互，一个进程的内部不仅有通常的事件，而且还有发送事件和接收事件，消息会被产生或被消费。设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 分别对应于进程的内部事件、发送事件和接收事件。 今后，我们将使用p, q, r, p1 ,p2 ,p3 , 来表记进程，用P来表记一个

系统进程的集合。

定义2.4可以充当进程的一个理论模型。一个进程的执行实际上是进程的一系列动作或操作(事件)的执行，也是变迁系统S (C, ,I)的执行。

我们感兴趣的是整个系统的执行，而在这样一次执行中，各进程的执行通过通信子系统协调交换信息。为了描述这样的通信协调，下面将分布式系统定义为一个变迁系统，其中，形态集、变迁关系、初始状态根据进程对应的成分构造。

定义2.5 进程集合P={ p1，p2， ，pN} 的一个分布式算法是P中每一个

进程的局部算法组成的一个集合。

分布式算法的行为由后面的变迁系统刻画，形态由每一个进程的状态和变迁过程中的消息集合构成，变迁的发生将最终落实到某个进程或某些进程上的事件，它们不仅影响进程的状态，而且还影响消息集合(或者受到消息集合的影响)。初始形态是这样的形态，系统中的每一个进程此时都处于初始状态，而且消息集合是空集合(对应通道为空)。

定义2.6 由进程p1，p2， ，pN 构成的分布式算法在异步消息传递机制

下引起的变迁系统(这里，每一个pi的局部算法为(Zpi, Ipi, pii, pis, pir ))是一个三元组S (C, ,I)，其中，

⑴ C ={(cp1，cp2 ， ，cpN，M) | ( pi ∈P：cpi ∈ Zpi，1≤i≤N) 且 M∈M(M)} ⑵ =(∪p∈P p)，其中， p 是对应于进程p的状态改变的变迁， pi是下列对集：

(cp1，cp2 ， ，cpi ， ，cpN，M1)，(cp1，cp2 ， ，c’pi， ，cpN，M2)

它们使下面三个条件之一成立：

① (cpi，c’pi )∈ pii 且 M1 = M2 ；

② 对某个m∈M，(cpi，m，c’pi )∈ pis 且 M2 = M1∪{m} ；

分布式算法导论,中文电子版,厦大赵致琢教授课件,有些内容做了改动。

③ 对某个m∈M，(cpi，m，c’pi )∈ pir 且 M1 = M2∪{m} ；

⑶ I ={(cp1，cp2， ，cpN，M) | ( pi ∈P：cpi ∈ Ipi)且M = φ，1≤i≤N }

分布式算法的执行是一种由变迁系统引起的执行，一个执行的事件清楚地表明了下面的注解：

消息用m表示，问题：两条消息内容相同怎么办？如何区分？

二元对(c，d)∈ pi 被称为是进程p的可能的内部事件，而 ps 和 pr中的三元组分别称为进程p的发送事件和接收事件。据此，我们引入下列术语：

由p的e = (c,d) 给定的内部事件称为在形态 =(cp1，cp2 ， ，cp ， ，cpN，M)上可应用的（或称为可应用于形态 ），如果cp = c 。此时，e( )定义为形态(cp1，cp2 ， ，d ， ，cpN，M) 。

由p的e = (c, m，d) 给定的发送事件称为可应用于形态 =(cp1，cp2 ， ，cp ， ，cpN，M)，如果cp = c 。此时，e( )定义为形态(cp1，cp2 ， ，d ， ，cpN，M∪{m}) 。

由p的e = (c, m，d) 给定的接收事件称为可应用于形态 =(cp1，cp2 ， ，cp ， ，cpN，M)，如果cp = c 且m∈M 。此时，e( )定义为形态(cp1，cp2 ， ，d ， ，cpN，M-{m}) 。

注意：这里要假定，对于每一个消息，存在能接收此消息的唯一的进程，该进程称为此消息的目的地。否则，M-{m}可能会丢失向其他结点发送的消息。

具有同步消息传递机制的变迁系统

消息传递称为是同步的，如果一个发送事件和对应的接收事件被协调成系统的一个单独的变迁。这就是说，一个进程只有当消息的目的地进程准备好接收这个消息时才能发送消息。结果，系统的变迁分为两类，一类对应于进程的内部状态的改变，另一类对应于把两个进程的通信事件组合在一起。技术上，这样的同步消息传递用通信原语来实现。

定义2.7 由进程p1 , p2 , ，pN 构成的分布式算法在同步消息传递机制下引

起的变迁系统(这里，每一个pi的局部算法为(Zpi, Ipi, pii, pis, pir ))是一个三元组S (C, ,I)，其中，

⑴ C ={(cp1，cp2 ， ，cpi ， ，cpN) | pi ∈P：cpi∈ Zpi，1≤i≤N }

⑵ =(∪p∈P p)∪(∪p, q∈P: p≠q pq)， …… 此处隐藏：16207字，全部文档内容请下载后查看。喜欢就下载吧 ……