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

【相似文獻(xiàn)】

相關(guān)會(huì)議論文 前10條

1 聞新;劉志言;胡恒章;周露;;傳感器故障檢測(cè)的閾值選取原則[A];1995中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];1995年

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

本文編號(hào)：2622884