MM-模型下的悲觀診斷算法研究.pdf

1、多機系統(tǒng)為人類實現(xiàn)高性能計算、大容量分布式信息存儲提供了強大的工具，多機系統(tǒng)的廣泛使用已經(jīng)成為衡量一個國家經(jīng)濟發(fā)展和信息化水平高低的一個重要標(biāo)志。隨著系統(tǒng)規(guī)模的日益擴大，系統(tǒng)中出現(xiàn)故障的可能性也隨之增大。因此，如何維持系統(tǒng)的高可靠性和可用性就成為一個迫切需要解決的問題。提高系統(tǒng)可靠性的一個主要手段就是及時診斷出系統(tǒng)中發(fā)生故障的結(jié)點，然后對其替換或修復(fù)，使系統(tǒng)恢復(fù)到正常工作狀態(tài)。系統(tǒng)級故障診斷作為故障診斷的一個強有力工具，在容錯領(lǐng)域得到了

2、廣泛的應(yīng)用。這種診斷方法因不使用額外的設(shè)備對系統(tǒng)進行診斷而具有極高的應(yīng)用價值。
　　 t1/t1-可診斷系統(tǒng)與tp-可診斷系統(tǒng)相比，前者只需付出可能把至多一個正常結(jié)點誤診斷為故障結(jié)點的代價就可以顯著地提高系統(tǒng)的自診斷能力。因此，對t1/t1-可診斷系統(tǒng)進行研究具有極高的價值。本論文的主要工作是在MM*模型下，對t1/t1-可診斷系統(tǒng)的診斷算法進行了研究，取得的主要成果描述如下：
　　 在對t1/t1-可診斷系統(tǒng)的研究過程

3、中，得到了一些t1/t1-可診斷系統(tǒng)的性質(zhì)，并對MM*模型下的癥候進行了分析，最后根據(jù)這些性質(zhì)提出了一個在MM*模型下t1/t1-可診斷系統(tǒng)的診斷算法，其時間復(fù)雜度為O(n2.5)，其中n為系統(tǒng)中的結(jié)點總數(shù)。應(yīng)用這個算法，可以把t1/t1-可診斷系統(tǒng)中的故障結(jié)點集F隔離到一個結(jié)點集U里，其中|F|≤t1，|U|≤min{t1，|F|+1}。應(yīng)用算法計算之后返回的結(jié)果可以進一步判定在U中的結(jié)點是否全部是故障結(jié)點，或者在U中是否包含一個不能