分布式失效检测算法研究.pdf

分布式失效检测算法的研究






重庆大学硕士学位论文


学生姓名:蒋传健
指导老师:夏云霓副教授
专业:计算机软件与理论
学科门类:工学



重庆大学计算机学院
二 O 一一年四月
Failure detection algorithm for reliable
distributed systems



A Thesis Submitted to Chongqing University
in Partial Fulfillment of the Requirement for the
Degree of Master of Engineering
By
Chuanjian Jiang

Supervised by Associate Prof. YunNi Xia
Major: Computer Software and theory




College puter Science of Chongqing
University, Chongqing,China
April 2011
重庆大学硕士学位论文中文摘要

摘要

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























II
重庆大学硕士学位论文英文摘要

ABSTRACT

Nowadays, the development and application puter technologies,
munication works make the style of information processing
shift from the traditional centralized way into decentralized pattern. In other words,
people can now