CN101572723B - 分布式系统有限状态机扩展模型及检查点准同步方法 - Google Patents

Abstract

本发明公开了一种分布式系统有限状态机扩展模型及检查点准同步方法，它解决了分布式系统检查点建立过程其精确性和稳定性较差问题。其扩展模型为：它将分布式系统视为若干个进程的集合，有限状态机扩展模型则是由这些有限个进程组成的集合：P＝{P₁，P₂，…P₀}，P_i表示进程，i＝1，2，…n；n≥2。准同步方法分为二个阶段，第一阶段由协调进程采集各进程信道信息，判别当前分布式系统状态是否是全局一致性状态，若是则各进程分别保存各自状态，算法结束；第二阶段为核实阶段，若不是一致性状态则确定丢失报文的进程，并由协调进程通知丢失报文的发送进程重发所失报文直到所有报文均被接收或由于超时所有进程非正常退出。

Description

分布式系统有限状态机扩展模型及检查点准同步方法

技术领域

本发明涉及分布式系统容错方法，尤其是涉及一种分布式系统有限状态机扩展模型及检查点准同步方法。 

背景技术

在应用层分布式系统可视为由若干个既各自独立又进行复杂交互的进程组成，此类进程相互协作共同完成一任务、通过报文交换完成进程间的通信进而实现系统资源的共享。分布式系统的常见故障主要有：崩溃性故障、遗漏性故障和时序故障、响应故障和随意性故障等。故障处理方法有基于硬件和软件的两种方案，软件方案主要有主动复制和被动复制。被动复制可采用前向恢复和后向恢复两种方法：前向恢复是假定可准确得到故障的性质并可排除此类故障从而使系统继续向前执行，前向恢复系统运行效率高但通常很难实现；后向恢复适用于系统故障无法预知和排除的情况，因此需定时存储系统的状态，一旦出现故障系统可恢复到先前状态执行。 

后向恢复主要涉及全局一致分布式系统状态的建立、存储和更新，其方法主要有同步检查点算法和异步检查点算法。所谓检查点是指进程执行过程中的某些点(进程的状态)。由没有丢失报文和孤儿报文的诸进程状信道状态和其进程内部状态构成的分布式系统状态称之为全局一致性状态或一致性检查点。同步检查点算法在一致性检查点建立过程中，诸进程协调各自局部检查点建立行为，以确保由诸进程局部检查点组成的系统全局检查点是一个一致性检查点。异步检查点算法在检查点建立过程中，诸进程无需协商独自建立自己的局部检查点，然而在恢复过程中需采用复杂算法恢复到一个系统一致性检查点。同步和异步检查点算法的关键是一致性检查点的建立，即满足所有报文均被接收的进程状态的获取，而无丢失报文和孤儿报文则是一致性检查点建立需满足的充分条件，然而上述算法均未对进程及其信道的输入输出特性进行精确的数学描述，丢失报文进程的判定缺乏统一准则，致使算法的精确性稳定性受到影响。 

发明内容

本发明的目的就是针对分布式系统全局一致性检查点的建立过程中的精确性和稳定性较差问题，提供一种分布式系统有限状态机扩展模型及检查点准同步方法，它通过对分布式系统输入输出特性的精确数学描述，建立具有容错信息的系统数学模型，进而导出一致性检查点的判定式和信道输入输出特性关系式，并提供一种基于具有容错信息分布式系统数学模型的一致性检查点建立方法，从根本上解决算法的精确性和稳定性问题。 

为实现上述目的，本发明采用如下技术方案： 

一种分布式系统有限状态机扩展模型，它将分布式系统视为若干个进程的集合，有限状态机扩展模型则是由这些有限个进程组成的集合： 

P＝{P₁，P₂，…P_n}，P_i表示进程，i＝1，2，3…n；n≥2。 

P_i＝{I，O，S_P，Q，F}，其中： 

a.I＝E_in×E_out是分布式系统进程输入事件集合，为内部输入事件集E_in与外部输入事件集E_out的笛卡积； 

其中，E_in＝{e_ik|k＝1，2…m}，e_ik为分布式系统的内部输入事件；i表示输入事件，k为内部输入事件序号，m为自然数。 

E_out＝{e_ok|k＝1，2…n}，e_ok为分布式系统的外部输入事件；o表示输出事件，k为外部输入事件序号，n为自然数。 

b.O＝O_in×O_out是分布式系统进程输出事件的集合，为对内输出事件集O_in与对外输出事件集O_out的笛卡积， 

其中，O_in＝{o_ik|k＝1，2…l}，o_ik为分布式系统的对内输出事件；i表示对内输出， 

k为对内输出事件序号。 

O_out＝{o_ok|k＝1，2…w}，o_ok为分布式系统的对外输出事件；下标o表示对外输出， 

k为对外输出事件序号。 

c.S_P＝S×K×M×T×U是分布式系统进程状态的集合，为进程内部状态集S、信道输入状态集K、信道输出状态集M、改进的向量逻辑时钟集T和发送向量集U的笛卡积； 

其中， 

S＝{S_m|m＝1，2，…k}为进程内部状态集合，S_m是进程的内部状态，内部状态记忆了内部输入事件，m表示内部状态序号，k为自然数。 

K＝{K_t|t＝1，2…r}为信道输入状态集合，K_t是信道的输入状态，其记忆了信道所接收报文的信息，t表示信道输入状态序号，r为自然数。 

K_t可进一步描述为： 

K_t＝{K_tk|k＝1，2，…w}，K_tk＝{F_tk，B_tk}；K_tk表示进程所发送某份报文的信息，F_tk为发送此报文进程的标识，B_tk是报文的标识，F_tk和B_tk均来自于其他报文发送进程，t表示信道输入状态序号，k为进程所接收报文序号，w为自然数。 

M＝{M_w|w＝1，2…l}为信道输出状态集合，M_w是信道的输出状态其记忆了信道所发送报文的信息，w为信道输出状态序号，l为自然数。 

M_w可进一步描述为： 

M_w＝{{F_wk，B_wk}|k＝1，2，…z} 

其中{F_wk，B_wk}表示进程所发送某份报文的信息，F_wk是发送进程的标识，B_wk是报文的标识；w为信道输出状态序号，k表示发送报文序号，z为自然数。 

T＝{T_i ^(k)|k＝1，2…l}为进程P_i信道改进的向量逻辑时钟集合，T_i ^(k)是进程P_i信道的向量逻辑时钟，k表示进程的状态时间变量，l为自然数，i表示进程P_i的序号。 

T_i ^(k)＝(T_i1 ^(k)，T_i2 ^(k)…T_in ^(k)) 

其中T_ii ^(k)表示进程p_i在当前信道状态时间k内发送报文的数目，其初值是零，每发送一份报文其值加一；T_ij ^(k)(i≠j，j＝1，2…n)表示进程p_i在当前信道状态时间内所接收的进程p_j的报文的数目；i为进程p_i的序号，j为进程p_j的序号，k是进程状态时间变量。 

U＝{U_i ^(k)|k＝1，2…w}为进程P_i的发送向量集合，U_i ^(k)为进程P_i的发送向量，k是进程状态时间变量，i为进程P_i序号，k为进程状态时间变量，w为自然数。 

U_i ^(k)＝(U_i1 ^(k)，U_i2 ^(k)…U_in ^(k)) 

其中，若i≠j，则U_ij ^(k)为进程P_i发送至进程P_j的报文数目；若i＝j，则U_ij ^(k)＝0；i表示进程P_i的序号，j表示进程P_j的序号，k为进程状态时间变量。 

d.Q＝I×S_P-＞O，是进程的输出函数， 

e.F＝I×S_P-＞S_P，是进程状态转移函数。 

一种基于分布式系统有限状态机扩展模型的检查点准同步方法，它的步骤为： 

(1)协调进程 

a.向所有进程发出检查点更新报文NB； 

b.判断检查点建立过程是否超时，若超时则发送超时报文FB至普通进程并退出检查点建立过程。 

c.等待接收各进程的信道信息报文SB。 

d.判断是否收到所有进程的信息报文，若未收到转至b，若收到转至e。 

e.核实各进程收发报文数量： 

若 ${T_{\mathrm{ii}}}^{\left(k\right)}=\underset{j=1}{\overset{i-1}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)}+\underset{j=i+1}{\overset{n}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)},$ i＝1，2…n，其中，T_ii ^(k)表示进程p_i所发送报文数目，T_ji ^(k)表示进程p_j所接收进程p_i发送的报文数目，n为自然数；则向所有进程发送结束报 文EB，通知其退出检查点建立过程；此后协调进程亦退出检查点建立过程。 

f.若 ${T_{\mathrm{ii}}}^{\left(k\right)}\≠\underset{j=1}{\overset{i-1}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)}+\underset{j=i+1}{\overset{n}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)},$ i＝1，2…n，其中，T_ii ^(k)表示进程p_i所发送报文数目，T_ji ^(k)表示进程p_j所接收进程p_i发送的报文数目，n为自然数；则进入检查点建立、更新的第二个阶段，找出所有丢失报文的发送进程p_i和接收进程p_j，并通知发送进程p_i重发所失报文。 

比较T_ji ^(k)和U_ij ^(k)，其中i＝1，2，…n，j＝1，2…n，i≠j，T_ji ^(k)表示进程p_j所接收的p_i发送报文数目，U_ij ^(k)表示进程p_i发送至p_j报文数目。若T_ji≠U_ij，表明p_i进程发送至p_j进程的报文丢失，则比较p_i进程信道输出状态和p_j进程信道输入状态，找出所丢失报文的标识，继而向进程p_i发送带有接收进程标识p_j的核实报文CB，通知p_i进程向p_j进程重发所丢失报文。 

g.在限定时间内接收普通进程的信息报文SB。 

h.判断检查点建立过程是否超时，若超时则发送超时报文FB至普通进程并退出检查点建立过程。若未超时进入步骤e。 

(2)普通进程p_i

(a)接收报文 

(b)若是建立更新报文转入C。若是数据报文，则更新信道输入状态变量K_t、信道输出状态变量M_w、向量逻辑时钟T_i ^(k)和发送向量U_i ^(k)，而后转至a。 

(c)停止发送数据报文，延迟一段时间后发送信息报文SB至协调进程。 

(d)接收报文。 

(e)若是结束报文EB保存进程内部状态信息，清空信道状态变量K_t、M_w，清除向量逻辑时钟T_i(k)和发送向量U_i(k)，而后退出检查点建立更新过程。 

(f)若是超时报文，退出检查点建立更新过程。 

(g)若是核实报文，向进程p_j重发丢失报文 

(h)若是数据报文，更新向量逻辑时间T_i(k)和发送向量U_i(k)，向协调进程重发信道信息报文SB，转至d。若是非数据报文，直接转至d。 

本发明的有益效果是：通过对分布式系统输入输出特性的精确数学描述，建立具有容错信息的系统数学模型，进而导出一致性检查点的判定式和信道输入输出特性关系式，并提供一种基于具有容错信息分布式系统数学模型的一致性检查点建立方法，从根本上解决算法的精确性和稳定性问题。 

附图说明

图1为进程P₁状态迁移图； 

图2为星型节点拓扑图； 

图3为总线型节点拓扑图； 

图4为环型节点拓扑图； 

图5为协调进程流程图； 

图6为普通进程流程图； 

图7为更新报文NB结构图； 

图8为超时报文FB结构图； 

图9为结束报文EB结构图； 

图10为核实报文CB结构图； 

图11为信道信息报文SB结构图； 

图12为数据报文结构图。 

具体实施方式

下面结合实施例对本发明作进一步说明。 

在工程科学如计算机科学中，凡是一种情况或一种活动的发生都可称作一个事件，为此将分布式系统视为事件系统，即在事件的驱动下系统发生状态迁移并产生相应的操作。 

根据事件对分布式系统的影响，可将事件分为输入和输出两种类型： 

1、输入事件，来自进程内部或外部输入操作所对应的事件。分布式系统的输入事件或来自于进程自身或来自于进程外部环境，如其它进程；此类事件不仅影响进程自身的状态迁移，而且有可能影响其他进程的状态变化。 

输入事件按其的来源进一步分为： 

(1)内部输入事件，是由于时钟的滴答所引起的进程的一条计算机指令或一段程序的执行等事件。内部输入事件源于进程所处节点计算机的系统时钟，并引起进程的内部状态迁移。显然，内部输入事件对应于外部不可见的进程内部操作和进程内部状态的迁移，是引起系统内部运动的主要因素。 

(2)外部输入事件，此类事件来自于进程外部或系统的其他进程，如进程的报文发送而导致其他进程的报文接收事件。此类事件主要引起进程通信信道状态的变化。 

2、输出事件，在输入事件的作用下进程状态迁移并产生的输出事件。 

输出事件按其作用的对象分，可分为： 

(1)对内输出事件，此类事件在进程内部状态迁移时出现且仅作用于此进程或进程所在计算机环境。如，引起变量值的更新、外设的动作等。 

(2)对外输出事件，此类事件作用于其它进程，体现了进程对分布式计算环境的影响。典型的对外输出事件，如进程的报文发送事件，此类事件作为其他进程的外部输入事件直接影响其通信信道的状态。 

分布式系统有限状态机扩展模型及其准同步方法： 

一个系统被定义为一组元素的集合，为了实现某些目标这些元素以特定规则相互作用和相互关联而集合在一起，从分布式应用和资源共享的角度，分布式系统可定义为若干个进程的集合。 

分布式系统有限状态机扩展模型是由有限个进程组成的集合： 

P＝{P₁，P₂，…P_n}，P_i表示进程，i＝1，2，3…n；n≥2。 

P_i＝{I，O，S_P，Q，F}，其中： 

a.I＝E_in×E_out是分布式系统进程输入事件集合，为内部输入事件集E_in与外部输入事件 

集E_out的笛卡积。其中，E_in＝{e_ik|k＝1，2…m}，e_ik为分布式系统的内部输入事件；E_out＝{e_ok|k＝1，2…n}，e_ok为分布式系统的外部输入事件。 

b.O＝O_in×O_out是分布式系统进程输出事件的集合，为对内输出事件集O_in与对外输出事件集O_out的笛卡积。其中，O_in＝{o_ik|k＝1，2…l}，o_ik为分布式系统的对内输出事件；O_out＝{o_ok|k＝1，2…w}，o_ok为分布式系统的对外输出事件； 

c.S_P＝S×K×M×T×U是分布式系统进程状态的集合，为进程内部状态集S、信道输入状态集K、信道输出状态集M、改进的向量逻辑时钟集T和发送向量U的笛卡积。 

其中，S＝{S_m|m＝1，2，…k}为进程内部状态集合，S_m是进程的内部状态。内部状态记忆了内部输入事件。 

K＝{K_t|t＝1，2…r}为信道输入状态集合，K_t是信道的输入状态，其记忆了信道所接收报文的信息，t表示信道输入状态序号，r为自然数；K_t可进一步描述为： 

K_t＝{{F_tk，B_tk}|k＝1，2，…w}，其中{F_tk，B_tk}表示进程所接收某份报文的信息，F_tk为发送此报文进程的标识，B_tk是报文的标识，F_tk和B_tk均来自于其他报文发送进程，t表示信道输入状态序号，k为进程所接收报文序号，w为自然数； 

M＝{M_w|w＝1，2…l}为信道输出状态集合，M_w是信道的输出状态其记忆了信道所发送报文的信息，w为信道输出状态序号，l为自然数。 

M_w可进一步描述为： 

M_w＝{{F_wk，B_wk}|k＝1，2，…z}，其中{F_wk，B_wk}表示进程所发送某份报文的信息，F_wk是发送进程的标识，B_wk是报文的标识；w为信道输出状态序号，k表示发送报文序号，z为自然数。 

T＝{T_i ^(k)|k＝1，2…l}为进程P_i信道改进的向量逻辑时钟集合，T_i ^(k)是进程P_i信道的向量逻辑时钟，k是进程的状态时间变量。T_i ^(k)＝(T_i1 ^(k)，T_i2 ^(k)…T_in ^(k))，其中T_ii ^(k)表示进程p_k在当前信道状态时间内发送报文的数目，其初值是零，每发送一份报文其值加一；T_ij ^(k)(i≠j)表示进程p_i在当前信道状态时间内所接收的进程p_j的报文的数目。 

U＝{U_i ^(k)|k＝1，2…w}为进程P_i的发送向量集合，U_i ^(k)为进程P_i的发送向量，k是进程的状态时间变量。 

U_i ^(k)＝(U_i1 ^(k)，U_i2 ^(k)…U_in ^(k))其中，若i≠j，则U_ij ^(k)为进程P_i发送至进程P_j的报文数目；若i＝j，则U_ij ^(k)＝0。 

d.Q＝I×S_P-＞O，是进程的输出函数。 

e.F＝I×S_P-＞S_P，是进程状态转移函数。 

实例： 

假设分布式系统由进程P₁、P₂和P₃组成，简单起见设每个进程内部状态时间内仅发送或接收一份报文，o1、o2和o3表示进程P₁对内输出事件，e₁、e₂和e₃表示进程P₁的内部输入事件，e₁′表示进程P₁外部输入事件(进程P₂发送报文至P₁)，o1′表示P₁的对外输出事件(P₁发送报文至P₃)，Ф表示进程P₁外部输入和对外输出的空事件，S₁、S₂和S₃表示进程P₁的内部状态，K₁和K₂表示进程P₁信道的输入状态，M₁和M₂表示进程P₁信道的输出状态，在系统内部输入事件和外部输入事件的作用下进程P₁的状态迁移图如图1所示。 

在内部输入事件e₁的作用下，P₁内部状态为S₁，信道输入和输出状态分别为K₁和M₁，向量时钟为[0，0，0]，发送向量为{0，0，0}。在内部输入事件e₂的作用下，P₁内部状态变为S₂，在外部输入事件e₁′作用下信道输入状态变为K₂，向量时钟变为[0，1，0]，发送向量仍为{0，0，0}。在内部输入事件e₃的作用下，P₁内部状态变为S₃，由于产生了对外输出事件o1′信道的输出状态变为M₂，向量时钟变为[1，1，0]，发送向量变为{0，0，1}。 

全局一致性状态及丢失报文之进程判定： 

设分布式系统的进程为：p₁、p₂、p₃、…p_n，与其对应的向量时钟为：T₁ ^(k)、T₂ ^(k)、T₃ ^(k)…T_n ^(k)。 

令 $T=\left(\begin{array}{c}{T_1}^{\left(k\right)}\\ {T_2}^{\left(k\right)}\\ {T_3}^{\left(k\right)}\\ \·\·\·\\ {T_n}^{\left(k\right)}\end{array}\right)=\left(\begin{array}{cccc}{T_{11}}^{\left(k\right)}& {T_{12}}^{\left(k\right)}& ...& {T_{1n}}^{\left(k\right)}\\ {T_{21}}^{\left(k\right)}& {T_{22}}^{\left(k\right)}& ...& {T_{2n}}^{\left(k\right)}\\ {T_{31}}^{\left(k\right)}& {T_{32}}^{\left(k\right)}& ...& {T_{3n}}^{\left(k\right)}\\ & ...& & \\ {T_{n1}}^{\left(k\right)}& {T_{n2}}^{\left(k\right)}& ...& {T_{\mathrm{nn}}}^{\left(k\right)}\end{array}\right)---\left(1\right)$

上式矩阵的主对角元素T_ii ^(k)对应于进程p_i所发送报文数目，T_ij ^(k)(i≠j)对应于进程p_i所接收p_j进程的报文数目。 

定理1，分布式系统的全局一致性状态充分条件 

若上式所对应矩阵主对角线的所有元素T_ii与其对应的第i列的元素的代数和都相等，即  ${T_{\mathrm{ii}}}^{\left(k\right)}=\underset{j=1}{\overset{i-1}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)}+\underset{j=i+1}{\overset{n}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)},$ i＝1，2…n    (2) 

则所有进程所发送的每份报文必定都被接收，即此刻的分布式系统的状态是一个全局一 致性状态。 

证：因为T_ii ^(k)表示p_i进程发送报文数目，T_ji ^(k)(j≠i)表示进程p_j所接收p_i进程发送的报文数目，(2)式表明任一进程p_i所发送的报文都被其他进程接收；所以所有进程所发送的报文必然都被接收，此刻的分布式系统状态必然是一个全局一致性状态。 

设分布式系统的进程p₁、p₂、p₃、…p_n对应的发送向量为：U₁ ^(k)、U₂ ^(k)、U₃ ^(k)…U_n ^(k)。 

令 $U=\left(\begin{array}{c}{U}_{1^{\left(k\right)}}\\ U_{2^{\left(k\right)}}\\ U_{3^{\left(k\right)}}\\ ...\\ U_{n^{\left(k\right)}}\end{array}\right)=\left(\begin{array}{cccc}{U}_{{11}^{\left(k\right)}}& U_{{12}^{\left(k\right)}}& ...& U_{{1n}^{\left(l\right)}}\\ U_{{21}^{\left(k\right)}}& U_{{22}^{\left(k\right)}}& ...& U_{{2n}^{\left(k\right)}}\\ U_{{31}^{\left(k\right)}}& U_{{32}^{\left(k\right)}}& ...& U_{{3n}^{\left(k\right)}}\\ & ...& & \\ U_{{n1}^{\left(k\right)}}& U_{N2\left(k\right)}& ...& U_{{\mathrm{nn}}^{\left(k\right)}}\end{array}\right)---\left(3\right)$

定理2，报文发送接收无遗漏充分条件 

若T_ji ^(k)＝U_ij ^(k)(j≠i)，则进程p_j所接收p_i进程的报文数目与进程p_i发送至进程p_j的报文数目相等，即进程p_i发送至进程p_j的报文无遗漏。 

证：因为T_ji ^(k)表示进程p_j所接收p_i进程的报文数目，U_ij ^(k)表示进程p_i发送至进程p_j的报文数目，所以由题设条件可知结论成立。 

定理3，判定丢失报文发送接收进程充分条件 

若T_ji ^(k)≠U_ij ^(k)，则表明p_i发送至进程p_j的报文至少有一份未被接收，且丢失报文的发送进程是p_i，接受进程是p_j。 

证：由所设条件可知，进程p_i发送至进程p_j的报文数目与p_j所接收p_i进程的报文数目不等，必然有U_ij ^(k)＞T_ji ^(k)，即p_i发送至进程p_j的报文至少有一份未被接收，由此可得丢失报文的发送进程是p_i、接收进程是p_j。 

基于有限状态机扩展模型的检查点建立准同步方法： 

假设： 

1、分布式系统的拓扑结构可为星型(图2)、总线型(图3)、环型(图4)和树型等。 

2、分布式系统是由普通进程P₁，P₂，…P_n和协调进程组成，其中n为自然数；每个进程均位于系统若干个节点之一。 

3、系统进程之间的报文直接可达或间接可达。 

算法由协调进程负责检查点的建立、更新过程的控制，各普通进程分别对其外部输入事件和对外输出事件计数并存储至向量逻辑时钟T_i ^(k)和发送向量U_i(k)。检查点的建立或更新过程分为二个阶段，第一阶段由协调进程采集各进程的信道信息，按定理1判别当前分布式系统的状态是否是全局一致性状态，若是一致性状态则各进程分别保存各自状态，算法结束；第二阶段为核实阶段，若不是一致性状态则由定理3确定丢失报文的发送、接收进程，并由协调进程通知丢失报文的发送进程重发所失报文直到所有报文均被接收或由于超时所有进程非正常退出。 

算法的控制报文类型为： 

1.检查点建立、更新报文NB(图7)，其中，源进程为分布式系统中发送报文之进程，源进程标识一个字节，目的进程为分布式系统中接收报文之进程，目的进程标识一个字节，报文类型一个字节；其功能是启动算法，由协调进程发送至各进程。 

2.超时报文FB(图8)，其中，源进程标识一个字节，目的进程标识一个字节，报文类型一个字节；由协调进程发送至各进程，通知各进程算法超时，进程接收后非正常退出算法。 

3.结束报文EB(图9)，结束算法，其中，源进程标识一个字节，目的进程标识一个字 节，报文类型一个字节；由协调进程发送至各进程，进程接收后正常退出算法。 

4.核实报文CB(图10)，其中，源进程标识一个字节，目的进程标识一个字节，报文类型一个字节，丢失报文的接收进程标识一个字节，丢失报文标识一个字节；此报文包含丢失报文标识和丢失报文的接收进程标识，由协调进程发送至丢失报文的发送进程。 

5.信道信息报文SB(图11)，其中，源进程标识一个字节，目的进程标识一个字节，报文类型一个字节，进程的向量逻辑时钟n个字节(n为普通进程个数，每个分量占用1个字节)、发送向量n个字节(n为普通进程个数，每个分量占用1个字节)、信道输入状态10个字节和信道输出状态10个字节，此报文由普通进程发送至协调进程。 

6.数据报文(图12)，其中，源进程标识一个字节，目的进程标识一个字节，报文类型一个字节，报文标识一个字节，数据k个字节，k为自然数。 

各进程检查点建立更新过程如下： 

(1)协调进程(见图5) 

a.向所有进程发出检查点更新报文NB； 

b.判断检查点建立过程是否超时，若超时则发送超时报文FB至普通进程并退出检查点建立过程。 

c.等待接收各进程的信道信息报文SB。 

d.判断是否收到所有进程的信息报文，若未收到转至b，若收到转至e。 

e.核实各进程收发报文数量： 

若 ${T_{\mathrm{ii}}}^{\left(k\right)}=\underset{j=1}{\overset{i-1}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)}+\underset{j=i+1}{\overset{n}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)},$ i＝1，2…n，其中，T_ii ^(k)表示进程p_i所发送报文数目，T_ji ^(k)表示进程p_j所接收进程p_i发送的报文数目，n为自然数；则向所有进程发送结束报文EB，通知其退出检查点建立过程；此后协调进程亦退出检查点建立过程。 

f.若 ${T_{\mathrm{ii}}}^{\left(k\right)}\≠\underset{j=1}{\overset{i-1}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)}+\underset{j=i+1}{\overset{n}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)},$ i＝1，2…n，其中，T_ii ^(k)表示进程p_i所发送报文数目，T_ji ^(k)表示进程p_j所接收进程p_i发送的报文数目，n为自然数；则进入检查点建立、更新的第二个阶段，找出所有丢失报文的发送进程p_i和接收进程p_j，并通知发送进程p_i重发所失报文。 

比较T_ji ^(k)和U_ij ^(k)，其中i＝1，2，…n，j＝1，2…n，i≠j，T_ji ^(k)表示进程p_j所接收的p_i发送报文数目，U_ij ^(k)表示进程p_i发送至p_j报文数目。若T_ji≠U_ij，表明p_i进程发送至p_j进程的报文丢失，则比较p_i进程信道输出状态和p_j进程信道输入状态，找出所丢失报文的标识，继而向进程p_i发送带有接收进程标识p_j的核实报文CB，通知p_i进程向p_j进程重发所丢失报文。 

g.在限定时间内接收普通进程的信息报文SB。 

h.判断检查点建立过程是否超时，若超时则发送超时报文FB至普通进程并退出检查点建立过程。若未超时进入步骤e。 

(2)普通进程p_i(详见图6) 

a.接收报文 

b.若是建立更新报文转入C。若是数据报文，则更新信道输入状态变量K_t、信道输出状态变量M_w、向量逻辑时钟T_i ^(k)和发送向量U_i ^(k)，而后转至a。 

c.停止发送数据报文，延迟一段时间后发送信息报文SB至协调进程。 

d.接收报文。 

e.若是结束报文EB保存进程内部状态信息，清空信道状态变量K_t、M_w，清除向量逻辑时钟T_i(k)和发送向量U_i(k)，而后退出检查点建立更新过程。 

f.若是超时报文，退出检查点建立更新过程。 

g.若是核实报文，向进程p_j重发丢失报文 

h.若是数据报文，更新向量逻辑时间T_i(k)和发送向量U_i(k)，向协调进程重发信道信息报文SB，转至d。若是非数据报文，直接转至d。 

算法分析： 

在算法的第一阶段，协调进程发送更新报文NB，各进程接收到NB后发送信息报文SB，协调进程收到SB后定理1核实之。若定理1所述条件满足则所有进程发送的报文必然都被接收。因为各进程已停止发送非控制报文，各进程信道的状态不再变化，所以协调进程向所有进程发送结束报文EB，各进程接收到EB后，保存各自状态信息，系统保存的必然是全局一致的状态信息。此阶段控制报文的数目为3n。 

在算法的第二阶段，若定理1所述条件不满足，协调进程按定理3所述条件(T_ji≠U_ij)找出丢失报文的发送进程，向其发送核实报文CB通知其重新发送，丢失报文的发送进程收到CB后重发丢失报文。此后有两种可能，其一所有丢失报文的发送进程收到CB后重发丢失报文，所有丢失报文的接收进程均收到所丢失报文并向协调进程重发向量逻辑时钟和发送向量，协调进程重新核实后定理1所述条件必然满足，此后系统保存的必然是一致性的状态信息；其二若丢失报文的发送进程未收到核实报文CB或接收进程未收到重发的丢失报文等，协调进程延时等待一段时间后发送超时报文FB，各进程收到FB后不保存状态信息，检查点建立过程非正常结束，系统原来所存状态信息不变。此种情况下控制报文的数目最多增加至5n。 

总之，算法要么正常结束，一个一致的全局状态得以保存；要么非正常结束，先前系统的状态保持不变；算法具有较高的稳定性。 

此算法控制报文的数目为0(n)，n为进程的数目，理想情况算法在检查点建立过程的第一阶段结束，报文数目为3n；在丢失报文的情况下算法在建立过程的第二阶段结束，报文数目最多为5n；与典型的Chandy-Lamport算法控制报文数目0(n²)相比，进程数目较多时报文数目有较大减少。此外，由于采用了改进的向量逻辑时钟和发送向量对信道发送接收报文统计计数，协调进程不仅可以判断当前分布式系统状态是否为全局一致性状态，而且可以确定丢失报文的发送和接收进程，因此算法的可靠性和稳定性较高。 

Claims (7)

1.一种基于分布式系统有限状态机扩展模型的检查点准同步方法，其特征是，它将分布式系统视为若干个进程的集合，有限状态机扩展模型则是由这些有限个进程组成的集合：

P＝{P₁，P₂，…P_n}，P_i表示进程，i＝1，2，3…n；n≥2；i为进程序号，n为自然数；

P_i＝{I，O，S_P，Q，F}，其中：

a)I＝E_in×E_out是分布式系统进程输入事件集合，为内部输入事件集E_in与外部输入事件集E_out的笛卡积；

其中，E_in＝{e_ik|k＝1，2…m}，e_ik为分布式系统的内部输入事件；i表示输入事件，k为内部输入事件序号，m为自然数；E_out＝{e_ok|k＝1，2…n}，e_ok为分布式系统的外部输入事件；o表示输出事件，k为外部输入事件序号，n为自然数；

b)O＝O_in×O_out是分布式系统进程输出事件的集合，为对内输出事件集O_in与对外输出事件集O_out的笛卡积，

其中，O_in＝{O_ik|k＝1，2…l}，o_ik为分布式系统的对内输出事件；i表示对内输出，k为对内输出事件序号；O_out＝{o_ok|k＝1，2…w}，o_ok为分布式系统的对外输出事件；下标o表示对外输出，k为对外输出事件序号；

c)S_P＝S×K×M×T×U是分布式系统进程状态的集合，为进程内部状态集S、信道输入状态集K、信道输出状态集M、改进的向量逻辑时钟集T和发送向量U集的笛卡积；

其中，S＝{S_m|m＝1，2，…k}为进程内部状态集合，S_m是进程的内部状态，内部状态记忆了内部输入事件，m表示内部状态序号，k为自然数；

K＝{K_t|t＝1，2…r}为信道输入状态集合，K_t是信道的输入状态，其记忆了信道所接收报文的信息，t表示信道输入状态序号，r为自然数；K_t可进一步描述为：

K_t＝{{F_tk，B_tk}|k＝1，2，…w}，其中{F_tk，B_tk}表示进程所接收某份报文的信息，F_tk为发送此报文进程的标识，B_tk是报文的标识，F_tk和B_tk均来自于其他报文发送进程，t表示信道输入状态序号，k为进程所接收报文序号，w为自然数；

M＝{M_w|w＝1，2…l}为信道输出状态集合，M_w是信道的输出状态其记忆了信道所发送报文的信息，w为信道输出状态序号，l为自然数；M_w可进一步描述为：

M_w＝{{F_wk，B_wk}|k＝1，2，…z}

其中{F_wk，B_wk}表示进程所发送某份报文的信息，F_wk是发送进程的标识，B_wk是报文的标识；w为信道输出状态序号，k表示发送报文序号，z为自然数；

T＝{T_i ^(k)|k＝1，2…l}为进程P_i信道改进的向量逻辑时钟集合，T_i ^(k)是进程P_i信道的向量逻辑时钟，k表示进程的状态时间变量，l为自然数，i表示进程P_i的序号；

T_i ^(k)＝(T_i1 ^(k)，T_i2 ^(k)…T_in ^(k))

其中T_ii ^(k)表示进程p_i在当前信道状态时间k内发送报文的数目，其初值是零，每发送一份报文其值加一；T_ij ^(k)表示进程p_i在当前信道状态时间内所接收的进程p_j的报文的数目；其中，i≠j，j＝1，2…n，i为进程p_i的序号，j为进程p_j的序号，k是进程状态时间变量；

U＝{U_i ^(k)|k＝1，2…w}为进程P_i的发送向量集合，U_i ^(k)为进程P_i的发送向量，k是进程状态时间变量，i为进程P_i序号，k为进程状态时间变量，w为自然数；

U_i ^(k)＝(U_i1 ^(k)，U_i2 ^(k)…U_in ^(k))

其中，若i≠j，则U_ij ^(k)为进程P_i发送至进程P_j的报文数目；若i＝j，则U_ij ^(k)＝0；i表示进程P_i的序号，j表示进程P_j的序号，k为进程状态时间变量；

d)Q＝I×S_P-＞O，是进程的输出函数；

e)F＝I×S_P-＞S_P，是进程状态转移函数；

它的步骤为：

(1)协调进程

a.向所有进程发出检查点更新报文NB；

b.判断检查点建立过程是否超时，若超时则发送超时报文FB至普通进程并退出检查点建立过程；

c.等待接收各进程的信道信息报文SB；

d.判断是否收到所有进程的信息报文，若未收到转至步骤b，若收到转至步骤e；

e.核实各进程收发报文数量：

若 ${T_{\mathrm{ii}}}^{\left(k\right)}=\underset{j=1}{\overset{i-1}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)}+\underset{j=i+1}{\overset{n}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)},$ i＝1，2…n，其中，T_ii ^(k)表示进程p_i所发送报文数目，T_ji ^(k)表示进程p_j所接收进程p_i发送的报文数目，n为自然数；则向所有进程发送结束报文EB，通知其退出检查点建立过程；此后协调进程亦退出检查点建立过程；

f.若 ${T_{\mathrm{ii}}}^{\left(k\right)}\≠\underset{j=1}{\overset{i-1}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)}+\underset{j=i+1}{\overset{n}{\mathrm{\Σ}}}{T_{\mathrm{ji}}}^{\left(k\right)},$ i＝1，2…n，其中，T_ii ^(k)表示进程p_i所发送报文数目，T_ji ^(k)表示进程p_j所接收进程p_i发送的报文数目，n为自然数；则进入检查点建立、更新的第二个阶段，找出所有丢失报文的发送进程p_i和接收进程p_j，并通知发送进程p_i重发所失报文；

比较T_ji ^(k)和U_ij ^(k)，其中i＝1，2，…n，j＝1，2…n，i≠j，T_ji ^(k)表示进程p_j所接收的p_i发送报文数目，U_ij ^(k)表示进程p_i发送至p_j报文数目；若T_ji≠U_ij，表明p_i进程发送至p_j进程的报文丢失，则比较p_i进程信道输出状态和p_j进程信道输入状态，找出所丢失报文的标识，继而向进程p_i发送带有接收进程标识p_j的核实报文CB，通知p_i进程向p_j进程重发所丢失报文；

g.在限定时间内接收普通进程的信息报文SB；

h.判断检查点建立过程是否超时，若超时则发送超时报文FB至普通进程并退出检查点建立过程，若未超时进入步骤e。

(2)普通进程p_i

(a)接收报文；

(b)若是建立、更新报文则转入(c)；若是数据报文，则更新信道输入状态变量K_t、信道输出状态变量M_w、向量逻辑时钟T_i ^(k)和发送向量U_i ^(k)，而后转至(a)；

(c)停止发送数据报文，延迟一段时间后发送信息报文SB至协调进程；

(d)接收报文；

(e)若是结束报文EB则保存进程内部状态信息，清空信道状态变量K_t、M_w，清除向量逻辑时钟T_i(k)和发送向量U_i(k)，而后退出检查点建立更新过程；

(f)若是超时报文，退出检查点建立更新过程；

(g)若是核实报文，向进程p_j重发丢失报文；

(h)若是数据报文，更新向量逻辑时间T_i(k)和发送向量U_i(k)，向协调进程重发信道信息报文SB，转至(d)；若是非数据报文，直接转至(d)。

2.如权利要求1所述的基于分布式系统有限状态机扩展模型的检查点准同步方法，其特征是，所述更新报文NB由源进程标识、目的进程标识和报文类型组成，其中，报文类型为00000001b。

3.如权利要求1所述的基于分布式系统有限状态机扩展模型的检查点准同步方法，其特征是，所述超时报文FB由源进程标识、目的进程标识和报文类型组成，其中，报文类型为00000011b。

4.如权利要求1所述的基于分布式系统有限状态机扩展模型的检查点准同步方法，其特征是，所述结束报文EB由源进程标识、目的进程标识和报文类型组成，其中报文类型为00000010b。

5.如权利要求1所述的基于分布式系统有限状态机扩展模型的检查点准同步方法，其特征是，所述核实报文CB由源进程标识、目的进程标识、报文类型、丢失报文接收进程标识、丢失报文标识组成，其中报文类型为00000100b。

6.如权利要求1所述的基于分布式系统有限状态机扩展模型的检查点准同步方法，其特征是，所述信道信息报文SB由源进程标识、目的进程标识、报文类型、向量时逻辑钟、发送向量、信道输入状态、信道输出状态组成，其中，报文类型为00000101b；向量时逻辑钟由T_i1 ^(k)，T_i2 ^(k)…T_in ^(k)组成；发送向量由U_i1 ^(k)，U_i2 ^(k)…U_in ^(k)组成；信道当前输入状态由F_tlB_tl……F_twB_tw组成；信道当前输出状态由F_wlB_wl……F_wzB_wz组成。

7.如权利要求1所述的基于分布式系统有限状态机扩展模型的检查点准同步方法，其特征是，所述数据报文由源进程标识、目的进程标识、报文类型、报文标识和数据组成，其中报文类型为00000110b。

Images