论文部分内容阅读
分布式一致性是指n个处理器组成的分布式系统，其中最多有m个处理器发生故障，要求所有的无故障处理器都能做出相同的决定，并且决定值必须是合理的。区域故障模型是多个局域网中处理器的故障模型。本文提出了区域故障模型下分布式一致性的改进算法，将其通信复杂度将为O（n3（?）min（f+2,t+1））。 分布式一致性和Byzantine一致性是等价的，而Byzantine一致性是分布式计算领域最基本的问题之一。首先对Byzantine一致性进行分类，然后证明了当且仅当n＞3m时才存在对应的Byzantine一致性算法，给出了n＞3m时的Byzantine一致性算法和其正确性证明。接下来描述了分布式一致性，给出了n＞3m时实现分布式一致性的指数级算法以及算法对应的几条性质，跟着用Phase King协议解决分布式一致性并给出证明。然后将n＞3m的情况扩展到使用对手结构，介绍了使用对手结构时的分布式一致性算法，证明了算法的几条性质。在接下来的部分定义了区域故障模型，分析了区域故障模型下分布式一致性的特征，据此给出了区域故障下实现分布式一致性的充要条件即A1∪A2∪A3≠P或者Ai（i=1，2，3）在（A，（?））上是可验证的，并且给出了相应的证明。接着利用上一部分证明充要条件时采用的思想，如果一个对手结构中三个元素覆盖处理器集合，那么这个对手结构可以用虚拟处理器来代替，这样虚拟处理器和真实处理器共同组成的集合满足Q3，在真实处理器和虚拟处理器上可以定义一个分布式协议，然后再根据协议的特性进一步改进。 最后提出了未来的研究方向，可以通过增强问题模型或者改进使用对手结构时的分布式一致性算法降低算法的通信开销。