论文部分内容阅读
计算机通信和网络技术的普及和发展,使信息的处理方式发生了根本性的变化。由原来传统的集中式处理转变成分布式处理方式。分布在不同的地点、基于不同的平台与环境的多个计算实体与信息资源。在具体的任务要求下,组合在一起相互协作完成指定的工作。 与传统的集中式处理相比,分布式系统下处理的完成依靠良好的网络通信。由于网络通信容易受到链路的故障、通信阻塞和消息丢失等多种不利因素的影响。所以,在分布式领域中的一个重要研究方向是在分布式环境下怎样保证算法的正确性与服务质量。近十几年来,应用失效检测机制来实现和设计分布式系统下的容错协议和算法是该领域研究的一个新课题。该课题研究的主要目标是要在通信容易受到链路的故障、通信阻塞、消息丢失和消息延迟不可预期等多种不利因素下,设计出满足完全性和精确性的失效检测算法。其解决方法应用到许多实际的分布式系统中,例如:HARP、PAXOS、BOXWOOD、Chain Replication等等。 在受限异步假设的前提下,本文提出了基于“存活授权/自杀失效”方法的失效检测算法。算法包括一个被检测进程(即主进程p)、多个观测进程X(用于监控主进程的状态)和一个用户进程q。在本文设计的算法中,采用“存活授权/自杀失效”机制来保证算法满足完整性和精确性。 本文从用户进程角度给出了完整性和精确性的定义。若主进程p在失效后,最终能够被用户进程q判为失效,则称系统满足用户完整性。若用户进程q永远不会在主进程p失效前将其判为失效,则称系统满足用户永久精确性。并分析了所提出的失效检测算法满足完整性和精确性两个性质。 对算法的服务质量进行分析。其服务质量包含三项指标:主进程自杀失效间隔时间的期望、失效检测时间的期望和正常响应时间的期望。本文还对失效检测算法的运行过程建立了数学模型,并对算法的服务质量的三项指标应用随机过程与概率方法进行理论上的分析。 最后,运用计算机模拟和参数估计技术对失效检测算法的服务质量的理论数据进行精准度的分析。用蒙特卡洛方法模拟失效检测算法的运行过程,来获得算法服务质量的三个指标在模拟运行中得到的数据。把模拟的数据作为理论值的采样,得到了理论结果的95%置信区间。其结果显示出,在绝大部分的参数设置下,模拟数据接近于理论结果,覆盖在相同的置信区间,从而理论模型具有可信度。