文档介绍：厦门大学
硕士学位论文
异步分布式系统中故障检测器的设计与实现
姓名:王良明
申请学位级别:硕士
专业:计算机应用技术
指导教师:赵致琢
20050601
摘要
摘要
由于存在结点失灵的可能,Fischer 等人证明了异步系统中不存在一
致合意的确定性求解算法[1] ,为此,Sam Toueg 等人提出了异步分布式系
统中的故障检测器技术[2] 。故障检测器作为一个模块独立运行,并输出可
疑结点列表,其他进程通过查询该列表来判断通讯对方结点的好坏。
以◇P 类1不可靠故障检测器为基础,采用模块化的体系结构,运用面
向对象的编程语言,本文设计和实现了一个异步系统中的故障检测器
FD = {}d1 ,d 2 ,
,d n ,使得运行在第i 台计算机上的故障检测服务模块 di 为本
机上的所有结点提供故障检测服务,因此故障检测器 FD = {}d1 ,d 2 ,
,d n 也
就能为整个网络上的结点提供检测服务。 FD 把一个物理故障检测器映射
为若干个逻辑故障检测器,逻辑故障检测器与本地结点一一“捆绑”在了
一起,即FD 对申请者来说是透明的。
FD 包含“结点接口”、“故障检测器”、“网络接口”和“结点和组群
管理”四个模块,这四个模块相互协同工作,对外共同实现若干个逻辑故
障检测器并“绑定”到本地的每一个应用结点(申请者)。
本文第三章对FD 进行了全面的测试和性能分析,内容包括 FD 本身的正
确性和健壮性(设计是否达到预期目标,能否在后台长时间无故障运行,各种
数据表格维护是否正确,消息收发是否顺畅等)和 FD 性能分析(包括资源耗
费情况,时间复杂性情况,消息复杂性和位复杂性情况,收敛快慢情况,发现
结点失灵的响应时间情况等)。实验结果表明,本文设计的 FD 是实用的、可靠
的和高效的。
关键词:分布式系统; FD ;故障检测器;收敛性;失灵

1 具有强完全性(所有失灵结点最终被每个正确结点怀疑)和最终强精确性(在某个时刻之后,
正确结点不被怀疑)属性的故障检测器统称为◇P 类。
i
Abstract
Abstract
Fischer et al. had proved that there is no deterministic algorithm to solve
consensus in asynchronous distributed systems, in which processes may crash.
Hence Sam Toueg et al. had proposed unreliable failure detecttion technology.
As a module, failure detector runs independently and outputs a list of
suspected nodes. Other processes can access the list to judge whether the
remote nodes are crrect or not.
Using Object-Oriented Language, we designed and implemented a Failure
Detection Service, namely FD = {}d1,d 2 ,
,dn , which has modular architecture
and is based on unreliable failure detector class ◇P. The failure detection
service module named di running on the i th host serves all of local nodes
(subscribers) with failure detection service, it follows that FD serve all
nodes in the distributed system with detection service. FD establishes a
mapping of a physical failure detector to several logical failure detectors, and
each of ones is associated with a subscriber. As a result, FD is transparent to
subscribers.
FD c