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

摘要

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

主权项

1.一种分布式系统有限状态机扩展模型，其特征是，它将分布式系统视为若干个进程的集合，有限状态机扩展模型则是由这些有限个进程组成的集合：P＝{P1，P2，…Pn}，Pi表示进程，i＝1，2，3…n；n≥2；i为进程序号，n为自然数；Pi＝{I，O，SP，Q，F}，其中：a)I＝Ein×Eout是分布式系统进程输入事件集合，为内部输入事件集Ein与外部输入事件集Eout的笛卡积；其中，Ein＝{eik|k＝1，2…m}，eik为分布式系统的内部输入事件；i表示输入事件，k为内部输入事件序号，m为自然数；Eout＝{eok|k＝1，2…n}，eok为分布式系统的外部输入事件；o表示输出事件，k为外部输入事件序号，n为自然数；b)O＝Oin×Oout是分布式系统进程输出事件的集合，为对内输出事件集Oin与对外输出事件集Oout的笛卡积，其中，Oin＝{oik|k＝1，2…l}，oik为分布式系统的对内输出事件；i表示对内输出，k为对内输出事件序号；Oout{ook|k＝1，2…w}，ook为分布式系统的对外输出事件；下标o表示对外输出，k为对外输出事件序号；c)SP＝S×K×M×T×U是分布式系统进程状态的集合，为进程内部状态集S、信道输入状态集K、信道输出状态集M、改进的向量逻辑时钟集T和发送向量U集的笛卡积；其中，S＝{Sm|m＝1，2，…k}为进程内部状态集合，Sm是进程的内部状态，内部状态记忆了内部输入事件，m表示内部状态序号，k为自然数；K＝{Kt|t＝1，2…r}为信道输入状态集合，Kt是信道的输入状态，其记忆了信道所接收报文的信息，t表示信道输入状态序号，r为自然数；Kt可进一步描述为：Kt＝{{Ftk，Btk}|k＝1，2，…w}，其中{Fwk，Bwk}表示进程所接收某份报文的信息，Ftk为发送此报文进程的标识，Btk是报文的标识，Ftk和Btk均来自于其他报文发送进程，t表示信道输入状态序号，k为进程所接收报文序号，w为自然数；M＝{Mw|w＝1，2…l}为信道输出状态集合，Mw是信道的输出状态其记忆了信道所发送报文的信息，w为信道输出状态序号，l为自然数；Mw可进一步描述为：Mw＝{{Fwk，Bwk}|k＝1，2，…z}其中{Fwk，Bwk}表示进程所发送某份报文的信息，Fwk是发送进程的标识，Bwk是报文的标识；w为信道输出状态序号，k表示发送报文序号，z为自然数；T＝{Ti(k)|k＝1，2…l}为进程Pi信道改进的向量逻辑时钟集合，Ti(k)是进程Pi信道的向量逻辑时钟，k表示进程的状态时间变量，l为自然数，i表示进程Pi的序号；Ti(k)＝(Ti1(k)，Ti2(k)…Tin(k))其中Tii(k)表示进程pi在当前信道状态时间k内发送报文的数目，其初值是零，每发送一份报文其值加一；Tij(k)表示进程pi在当前信道状态时间内所接收的进程pj的报文的数目；其中，i≠j，j＝1，2…n，i为进程pi的序号，j为进程pj的序号，k是进程状态时间变量；U＝{Ui(k)|k＝1，2…w}为进程Pi的发送向量集合，Ui(k)为进程Pi的发送向量，k是进程状态时间变量，i为进程Pi序号，k为进程Pi发送向量序号，w为自然数；Ui(k)＝(Ui1(k)，Ui2(k)…Uin(k))其中，若i≠j，则Uij(k)为进程Pi发送至进程Pj的报文数目；若i＝j，则Uij(k)＝0；i表示进程Pi的序号，j表示进程Pj的序号，k为进程状态时间变量；d)Q＝I×SP-＞O，是进程的输出函数；e)F＝I×SP-＞SP，是进程状态转移函数。