一种基于信道不可靠环境的协调式检查点协议.pdfVIP

维普资讯 第 l8卷 第 2期 计 算 机 技 术 与 发 展 Voi．18 Nc)．2 2008年 2月 COMPUTER TECHNOLOGY AND DEVE1X)PMENI’ Feb． 2008 一 种基于信道不可靠环境的协调式检查点协议 张杰智，任 国林 (东南大学计算机科学与工程学院，江苏 南京 210096) 摘 要 ：在分布式计算环境中经常使用检查点 ／恢复策略来进行容错。文中主要研究在信道不可靠的环境中通过协调使 相互通信的各进程所做的检查点保持全局一致性的方法。通过分析中途消息与信道可靠性之闯的关系以及已有检查点 协议对于中途消息处理方法 ，提出了一种应用于信道不可靠环境下的协调式检查点方法 ，其消息复杂度为O(N)且不引 入其他的计算负担，只通过一次同步即可达到全局一致性状态 ，相比于以往的协调式检查点协议大大减小了时间开销 ，提 高了在不可靠信道环境中做全局一致检查点的效率。 关键词：检查点协议；全局一致性；协调式检查点 中图分类号：11)3l1 文献标识码 ：A 文章编号 ：1673—629X(2008)02—0o55一O4 A CoordinatedCheckpointingProtocolBasedon UnreliableChannels ZHANGJie-zhi，RENGuo-lin (SchoolofComputerScienceandEngineering，SoutheastUniversity，Nnajing 210096，China) Al~met：Indistributedcomputingenvironments．checkpoint／rollbackrecoverymcehanism iswidelyusedtoachievefaulttolerance．Fo· cllse8onagloballyconsistnetcheckpointprotocoldevelopedfordistributedprocessesthatctmm~unicatewith魄chotherthroughunreliable channels．Afteranalysing themeth~ adoptde byexisting globalehcekpointing protocolsdealingwithin—transmitm~sages，bring for· wardanovelmethodthatisappliacbleinunreliablecommunicationchanne1．Themessagecomplexityinvolvde iswithinO(N )，withno otherrelatde computationaverh∞d．ItcanachieveglDbalconsistnecythroughonesynchronization，thusgreatlyreducesthetimeoverhead ocmpanng withtheexisting methods．Tests indiactetha tit 肌 soverexisting mcehanism ofchannelclearing Ormessageocunting ． Keywords：ehcekpointing protocol；glohalconsistnecy；ocordinatde checkpoint O 引 言 点设置必须符合全局一致性，即要做全局检查点。 在大规模集群计算环境中，许多大型程序运行时 全局检查点按其检查点协议主要分三种 J：独立 间较长，有的需要几天、几周甚至几个月。由于机群 自 式检查点、消息驱动式检查点-2J和