分布式系统中容错计算的合意问题与快照算法的研究

摘要

分布式计算机系统近二十多年来获得了很大的发展，广泛地受到学术界的高度重视，它的应用也越来越引人注目。在未来，几乎绝大多数有效的计算机系统都将是一个分布式计算机系统，这就极大地促进了分布式计算理论、方法与技术的发展。同时，随着通信技术和计算机技术的飞速发展，网络带宽和CPU速度的不断提高，对分布式系统的性能要求也日益受到重视。于是，分布式系统的高性能成为人们追求的主要目标之一。根据不同的应用任务(问题)决定不同的软硬件系统结构可进一步提高系统性能，而所有这一切，都需要高质量的分布式算法作为支撑。 计算全局一致性快照是分布式系统和分布式计算面临的主要的基础问题之一。快照计算了所有进程的状态和通道的状态，它能从逻辑上反映出某一时刻各个进程及通道的情况，形成系统的一个形态(全局状态)。因此，我们可以利用快照算法的反复执行来检测稳定性质，常见的如终止性检测，死锁检测等。本文在通道为FIFO的前提下，讨论了一类特殊的快照，即无消息在传递途中(in_transit)的快照，并在快照的基础上进行终止性检测。这类特殊的算法不仅可以有效地解决了系统的终止性检测问题，还节省了存储空间。 容错计算是当前分布式计算的一个热点，合意协议则是容错系统的核心。因为FLP不可能性结果，Chandra和Toueg引入了不可靠故障检测器的概念来解决合意。他们证明了：在一般情况下，故障检测器类S与◇P类是不可比较的。本文从两类故障检测器实际解决合意问题能力的角度出发，分析得出S类故障检测器将会比◇P类强。之后我们在S类故障检测器的基础上对精确性进行修改，定义了一个最小从未受到怀疑的参数ι，改进经典的基于S类的合意协议。改进的协议在通讯轮和消息复杂度方面都与参数ι有密切的联系，且这两方面相对Chandra-Toueg提出的经典合意协议有所改善，可以达到提高协议性能的目的。

目录

文摘

英文文摘

厦门大学学位论文原创性声明及著作权使用声明

第一章 分布式系统与分布式算法概述

1.1 分布式系统

1.2 分布式算法

1.3 本文的工作

第二章 基于无in_transit消息快照的终止性检测

2.1 快照算法概述

2.2 预备知识

2.3 两个快照算法

2.3.1 Chandy-Lamport算法

2.3.2 Lai-Yang算法

2.4 无in-transit消息的快照算法

2.4.1 一致性

2.4.2 基于快照的全局时钟

2.4.3 本文算法模型

2.4.4 本文算法证明与分析

2.5 小结

第三章 基于ι-精确的S类故障检测器的合意问题

3.1 合意问题概述

3.2 异步系统和不可靠故障检测器

3.2.1 异步系统及其故障类型

3.2.2 不可靠故障检测器

3.3 S类故障检测器与◇P类故障检测器比较

3.3.1 合意问题与FLP不可能性结果

3.3.2 S类故障检测器与◇P类故障检测器

3.4 基于ι-精确的S类故障检测器的合意问题

3.4.1 问题的提出

3.4.2 协议的改进

3.4.3 协议性能分析

3.5 小结

第四章 总结与讨论

参考文献

硕士研究生学习期间已发表的论文

致谢