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

1、隨著大型分布式系統(tǒng)的不斷發(fā)展，人們越來越關注系統(tǒng)的可靠性。例如中國研制的天河一號系統(tǒng)、航空火車等分布式控制交通系統(tǒng)以及基于MPI的FT-MPI系統(tǒng)等。分布式系統(tǒng)不僅關系到經濟社會各方面的發(fā)展，而且與我們每個人息息相關。分布式系統(tǒng)容錯性的質量保證的特性決定了其應用的廣泛性以及重要性。分布式系統(tǒng)的容錯性可以理解為容忍錯誤，消除錯誤影響。分布式系統(tǒng)容錯主要分為前向容錯和后向容錯?？紤]到存儲量以及恢復過程，與前向容錯技術相比，后向容錯技術在實際

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

3、驗模型。通過研究進程間消息接收事件數(shù)目與消息發(fā)送事件數(shù)目的關系，本文提出消息數(shù)目檢驗模型。在此模型中，若一個全局狀態(tài)中不含孤兒消息，則判定此全局狀態(tài)是一致的。
　　 (2)基于消息數(shù)目檢驗模型，提出一種新的求解包含給定檢查集的最大最小全局一致檢查點算法。此算法首先利用消息數(shù)目檢驗方法判定給定的檢查點集中是否存在孤兒消息。如果存在孤兒消息，則分布式系統(tǒng)中不存在包含給定檢查點集的最大最小全局一致檢查點，減少搜索時間開銷。否則，通過全

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