分布式计算中的共识问题研究

发布时间：2020-04-11 00:09

【摘要】：本文的主要研究对象是分布式计算中的共识问题。共识问题是分布式计算中最重要的理论问题之一,它刻画了不同处理器之间的协调问题,即如何从互相冲突的输入值产生一致的输出值。共识问题在同步系统中有很多有效实现算法,但早在1985年,它就被证明在异步系统中是无法实现的[1]。之后的20多年中,人们为了规避这个不可能结果提出了很多模型和方法,其中故障检测器是由Chandra与Toueg在1991提出的方法[2]。它通过给处理器提供故障的信息,刻画共识问题所需要的同步条件。之后多年的研究工作证明这个方法对刻画很多分布式计算问题所需的系统同步条件都是一个强有力的工具。其中,共识问题的推广 k-共识是一个备受关注的研究问题,本文的主要工作之一就是研究该问题最弱的故障检测器。本文首先基于Ω_k构造了两类新的故障检测器Ω′k,Ω_k′′。他们虽然与Ω_k等价,但各有特点;而且利用Ω′k′能够设计完全忠实于Paxos算法的k-共识实现算法。这些结果加深了人们对k-共识问题的故障检测器以及Paxos算法的理解,同时也是之后划分框架的基础。本文接着提出了划分框架,并利用这个框架分别在消息传递模型和公共内存模型中定义了一系列划分故障检测器。这些新设计的故障检测器不仅有能力解决相对应的k-共识问题,而且比已知的故障检测器都要严格弱,即对应更弱的系统同步条件。这些结果说明(1)划分框架开创了减弱共识相关问题故障检测器的方法,(2)划分框架能够有效检验某个故障检测器是否是最弱故障检测器,(3)之前提出的k-共识问题的几个候选检测器都不可能是最弱的故障检测器。共识问题有两种最自然的表达形式:二值共识与多值共识,这两者的等价性是很基本的理论问题。本文在可靠信道的异步消息传递模型中,提出了两个更有效的用二值共识实现多值共识的算法;接着,又在公平丢失信道模型中再次证明了两者的等价性。后者实际上等价于利用二值共识实现一致可靠广播。本文不仅提出了实现算法,而且证明任何算法都必须调用无限次二值共识。
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2010
【分类号】：TP338.8

【相似文献】