一种低费用协调检查点算法.doc

一种低费用协调检查点算法 　　摘要：检查点算法作为一种有效的故障技术及容错手段，已广泛地运用在网格、分布式和云计算系统中。该文提出了一种非阻塞协调检查点算法，该算法增加了系统的可靠性，并允许检查点灵活设置，充分缩减了同步信息数量，加速了检查点形成时间。和典型的相关算法比较，该文提出的算法使用更少的同步控制消息，具有更低的费用，引入同步控制消息的时间复杂度由一般的[O（n2）]降到[O（n）]，且同步消息数仅仅为[n-1]。 关键词：检查点；分布式系统；云计算系统；容错 中图分类号：TP302 文献标识码：A 文章编号：1009-3044（2014）10-2394-03 Abstract： The technology of checkpoint as an effective method of fault tolerance has been widely used in grid ，distributed and cloud systems. In this paper， a non-blocking cooperative checkpoint algorithm， which increases the reliability of the system and set up checkpoints flexible. At the same time， it fully reduces the synchronization information quantity， speeds up the formation checkpoint time， fully reduced the amount of information synchronized， the checkpoint accelerated development time. When compared to noted recent algorithms， the proposed algorithm uses less synchronous control messages with lower overhead. While the time complexity of control message during synchronous phase is reduced from O（n2） to O（n）， the algorithm’s controlling messages are reduced to n-1. Key words： checkpoint； distributed system； cloud computing systems； fault-tolerant 众所周知，检查点和回卷恢复技术是实现容错和处理故障的有效方式，已广泛地运用在网格、分布式、普适计算和云计算系统中。K. MANI采用了一种新颖的可保障全局性能稳定的算法[1]，但必须首先获取全局状态一致的点。文献[2]提出一种低开销的适用于错误恢复的协调检查点算法，允许频率检查点仅由可靠性来确定。文献[3，5]针对特殊应用提出了自己的算法，文献[3]提出的检查点算法，适用于共享内存式系统而并非分布式或者云计算系统。文献[4，5]提出了一种能很好获取全局状态的检查点算法，能有效驱赶孤儿消息和中途消息。而S.Monnet[6]提出一种混合式同异步检查点算法，能够实现获取的并行性。G.CAO[7]采用经典的两阶段提交算法，其总时间耗费有一定的降低。汪东升[8]采用辅助信息计数的同步运算，其同步信息数为[3n]。 1 系统模型 本文算法可应用于开放的网格、云计算、P2P等分布式系统，因此做文献[9，10]的相同假设，对底层硬件和软件不做特别要求。[Pn]为分布式系统中的进程，各进程有自己的运行速度，利用通信信道交换信息，它们之间的传输延迟是有限的、任意的。 另外一些术语定义： [Sflag=0 相应进程未发送应用消息 1 相应进程发送了应用消息 ；][CiN]、[SiN]代表进程[Pii=1，2，…，n]的序号。C（N）表示算法执行，S（N）表示消息成功发送 。[Ci，x]表示进程Pi的第[x]个进程节点。[MAapplication message]：应用消息， 通过通信实现计算目标；[MCcontrol message]：控制信息， 负责[Pk] 行为的协调运行。[ORM] ：孤儿信息（orphan message）。[msg]：表示进程发送的[M（A）] ，[msgn]：表示[Pk] 发出的第[n] 个[M（A）] 。 2 协调检查点算法 2.1 算法描述 本文的检查点算法将进程分为启动进程IPR