基于消息數(shù)目檢驗(yàn)和消息重排序理論的檢查點(diǎn)算法的研究.pdf

1、隨著大型分布式系統(tǒng)的不斷發(fā)展，人們?cè)絹?lái)越關(guān)注系統(tǒng)的可靠性。例如中國(guó)研制的天河一號(hào)系統(tǒng)、航空火車等分布式控制交通系統(tǒng)以及基于MPI的FT-MPI系統(tǒng)等。分布式系統(tǒng)不僅關(guān)系到經(jīng)濟(jì)社會(huì)各方面的發(fā)展，而且與我們每個(gè)人息息相關(guān)。分布式系統(tǒng)容錯(cuò)性的質(zhì)量保證的特性決定了其應(yīng)用的廣泛性以及重要性。分布式系統(tǒng)的容錯(cuò)性可以理解為容忍錯(cuò)誤，消除錯(cuò)誤影響。分布式系統(tǒng)容錯(cuò)主要分為前向容錯(cuò)和后向容錯(cuò)。考慮到存儲(chǔ)量以及恢復(fù)過(guò)程，與前向容錯(cuò)技術(shù)相比，后向容錯(cuò)技術(shù)在實(shí)際

2、應(yīng)用中更為廣泛。
　　 本課題來(lái)自于“基于后向恢復(fù)的異構(gòu)分布式系統(tǒng)容錯(cuò)技術(shù)的研究與實(shí)現(xiàn)”的山東省自然科學(xué)基金項(xiàng)目。后向容錯(cuò)技術(shù)分為兩種;基于檢查點(diǎn)的容錯(cuò)算法與基于消息日志的容錯(cuò)協(xié)議。如何保存分布式系統(tǒng)的系統(tǒng)狀態(tài)以及當(dāng)系統(tǒng)失效時(shí)如何使進(jìn)程恢復(fù)到全局一致?tīng)顟B(tài)是后向容錯(cuò)技術(shù)中的兩個(gè)主要問(wèn)題?，F(xiàn)存文獻(xiàn)中存在很多判定分布式全局狀態(tài)一致的方法，但存在不同程度的缺陷。
　　 本文主要?jiǎng)?chuàng)新點(diǎn)及貢獻(xiàn)為;
　　 (1)提出消息數(shù)目檢

3、驗(yàn)?zāi)Ｐ汀Ｍㄟ^(guò)研究進(jìn)程間消息接收事件數(shù)目與消息發(fā)送事件數(shù)目的關(guān)系，本文提出消息數(shù)目檢驗(yàn)?zāi)Ｐ?。在此模型中，若一個(gè)全局狀態(tài)中不含孤兒消息，則判定此全局狀態(tài)是一致的。
　　 (2)基于消息數(shù)目檢驗(yàn)?zāi)Ｐ停岢鲆环N新的求解包含給定檢查集的最大最小全局一致檢查點(diǎn)算法。此算法首先利用消息數(shù)目檢驗(yàn)方法判定給定的檢查點(diǎn)集中是否存在孤兒消息。如果存在孤兒消息，則分布式系統(tǒng)中不存在包含給定檢查點(diǎn)集的最大最小全局一致檢查點(diǎn)，減少搜索時(shí)間開(kāi)銷。否則，通過(guò)全

4、局搜索算法查找包含給定檢查點(diǎn)集的最大最小全局一致檢查點(diǎn)。
　　 (3)提出了消息重排序理論。首先此理論描述了消息發(fā)送事件與接收事件間的總是在先發(fā)生關(guān)系，并利用進(jìn)程改進(jìn)的邏輯時(shí)鐘標(biāo)記事件間的總是在先發(fā)生關(guān)系。其次此理論引入了等價(jià)消息接收序列的概念。在消息恢復(fù)過(guò)程中不存在和進(jìn)程失效前執(zhí)行結(jié)果完全一致的等價(jià)的消息接收序列。最后此理論解決了在樂(lè)觀消息日志恢復(fù)協(xié)議中，進(jìn)程的接收消息次序由于故障丟失的問(wèn)題。
　　 (4)在消息數(shù)目檢