分布式失效檢測(cè)算法的研究.pdf

1、計(jì)算機(jī)通信和網(wǎng)絡(luò)技術(shù)的普及和發(fā)展，使信息的處理方式發(fā)生了根本性的變化。由原來傳統(tǒng)的集中式處理轉(zhuǎn)變成分布式處理方式。分布在不同的地點(diǎn)、基于不同的平臺(tái)與環(huán)境的多個(gè)計(jì)算實(shí)體與信息資源。在具體的任務(wù)要求下，組合在一起相互協(xié)作完成指定的工作。
　　與傳統(tǒng)的集中式處理相比，分布式系統(tǒng)下處理的完成依靠良好的網(wǎng)絡(luò)通信。由于網(wǎng)絡(luò)通信容易受到鏈路的故障、通信阻塞和消息丟失等多種不利因素的影響。所以，在分布式領(lǐng)域中的一個(gè)重要研究方向是在分布式環(huán)境下怎樣

2、保證算法的正確性與服務(wù)質(zhì)量。近十幾年來，應(yīng)用失效檢測(cè)機(jī)制來實(shí)現(xiàn)和設(shè)計(jì)分布式系統(tǒng)下的容錯(cuò)協(xié)議和算法是該領(lǐng)域研究的一個(gè)新課題。該課題研究的主要目標(biāo)是要在通信容易受到鏈路的故障、通信阻塞、消息丟失和消息延遲不可預(yù)期等多種不利因素下，設(shè)計(jì)出滿足完全性和精確性的失效檢測(cè)算法。其解決方法應(yīng)用到許多實(shí)際的分布式系統(tǒng)中，例如：HARP、PAXOS、BOXWOOD、Chain Replication等等。
　　在受限異步假設(shè)的前提下，本文提出了基于

3、“存活授權(quán)/自殺失效”方法的失效檢測(cè)算法。算法包括一個(gè)被檢測(cè)進(jìn)程(即主進(jìn)程p)、多個(gè)觀測(cè)進(jìn)程X(用于監(jiān)控主進(jìn)程的狀態(tài))和一個(gè)用戶進(jìn)程q。在本文設(shè)計(jì)的算法中，采用“存活授權(quán)/自殺失效”機(jī)制來保證算法滿足完整性和精確性。
　　本文從用戶進(jìn)程角度給出了完整性和精確性的定義。若主進(jìn)程ｐ在失效后，最終能夠被用戶進(jìn)程q判為失效，則稱系統(tǒng)滿足用戶完整性。若用戶進(jìn)程q永遠(yuǎn)不會(huì)在主進(jìn)程ｐ失效前將其判為失效，則稱系統(tǒng)滿足用戶永久精確性。并分析了所提出

4、的失效檢測(cè)算法滿足完整性和精確性兩個(gè)性質(zhì)。
　　對(duì)算法的服務(wù)質(zhì)量進(jìn)行分析。其服務(wù)質(zhì)量包含三項(xiàng)指標(biāo)：主進(jìn)程自殺失效間隔時(shí)間的期望、失效檢測(cè)時(shí)間的期望和正常響應(yīng)時(shí)間的期望。本文還對(duì)失效檢測(cè)算法的運(yùn)行過程建立了數(shù)學(xué)模型，并對(duì)算法的服務(wù)質(zhì)量的三項(xiàng)指標(biāo)應(yīng)用隨機(jī)過程與概率方法進(jìn)行理論上的分析。
　　最后，運(yùn)用計(jì)算機(jī)模擬和參數(shù)估計(jì)技術(shù)對(duì)失效檢測(cè)算法的服務(wù)質(zhì)量的理論數(shù)據(jù)進(jìn)行精準(zhǔn)度的分析。用蒙特卡洛方法模擬失效檢測(cè)算法的運(yùn)行過程，來獲得算法服