【摘要】：本文的主要研究對象是分布式計算中的共識問題。共識問題是分布式計算中最重要的理論問題之一,它刻畫了不同處理器之間的協調問題,即如何從互相沖突的輸入值產生一致的輸出值。 共識問題在同步系統(tǒng)中有很多有效實現算法,但早在1985年,它就被證明在異步系統(tǒng)中是無法實現的[1]。之后的20多年中,人們?yōu)榱艘?guī)避這個不可能結果提出了很多模型和方法,其中故障檢測器是由Chandra與Toueg在1991提出的方法[2]。它通過給處理器提供故障的信息,刻畫共識問題所需要的同步條件。之后多年的研究工作證明這個方法對刻畫很多分布式計算問題所需的系統(tǒng)同步條件都是一個強有力的工具。其中,共識問題的推廣  k-共識是一個備受關注的研究問題,本文的主要工作之一就是研究該問題最弱的故障檢測器。本文首先基于Ω_k構造了兩類新的故障檢測器Ω′k,Ω_k′′。他們雖然與Ω_k等價,但各有特點;而且利用Ω′k′能夠設計完全忠實于Paxos算法的k-共識實現算法。這些結果加深了人們對k-共識問題的故障檢測器以及Paxos算法的理解,同時也是之后劃分框架的基礎。本文接著提出了劃分框架,并利用這個框架分別在消息傳遞模型和公共內存模型中定義了一系列劃分故障檢測器。這些新設計的故障檢測器不僅有能力解決相對應的k-共識問題,而且比已知的故障檢測器都要嚴格弱,即對應更弱的系統(tǒng)同步條件。這些結果說明(1)劃分框架開創(chuàng)了減弱共識相關問題故障檢測器的方法,(2)劃分框架能夠有效檢驗某個故障檢測器是否是最弱故障檢測器,(3)之前提出的k-共識問題的幾個候選檢測器都不可能是最弱的故障檢測器。 共識問題有兩種最自然的表達形式:二值共識與多值共識,這兩者的等價性是很基本的理論問題。本文在可靠信道的異步消息傳遞模型中,提出了兩個更有效的用二值共識實現多值共識的算法;接著,又在公平丟失信道模型中再次證明了兩者的等價性。后者實際上等價于利用二值共識實現一致可靠廣播。本文不僅提出了實現算法,而且證明任何算法都必須調用無限次二值共識。
【學位授予單位】：清華大學
【學位級別】：博士
【學位授予年份】：2010
【分類號】：TP338.8

【相似文獻】

相關會議論文 前10條

1 聞新;劉志言;胡恒章;周露;;傳感器故障檢測的閾值選取原則[A];1995中國控制與決策學術年會論文集[C];1995年

2 王衛(wèi)民;許家s，

本文編號：2622884