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

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

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

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