四模冗余拜占庭容錯計算機可靠性分析*

肖愛斌，胡明明，任憲朝，李 森，楊 樑

(1.北京控制工程研究所，北京100190;2.北京空間科技信息研究所，北京100190;3.中國空間技術研究院，北京100094)

0 引 言

工業界往往采用最小的硬件冗余來提高可靠性，只能容忍少數的幾種故障模式;國防應用研究領域，尤其是載人航天器一般采用足夠的硬件冗余來提高系統可靠性，具備容忍所有故障模式的能力.

星載控制計算機是衛星的關鍵部件，其可靠性直接關系到衛星能否正常運行和完成預定任務.為了保證計算機能在惡劣太空輻射環境中長期可靠工作，需要對其進行專門的加固和冗余容錯設計.對于載人航天器，由于涉及到乘員的安全性，控制計算機在完善單機設計外，通過精巧的冗余設計來增強整個計算機系統的容忍故障的能力尤為必要.學術界和防御研究機構建議，對于載人航天器這樣有關鍵安全性需求的設備或系統可以使用足夠硬件冗余來滿足容忍任意故障模式的需求.容忍任意故障模式稱作拜占庭恢復(Byzantine resilience)[1].由于拜占庭恢復系統通過硬件冗余來屏蔽隱藏的未知故障引起的模塊或單機失效，因此具有極高的可靠性，使得星載計算機在關鍵安全、可靠性方面的指標能得到有效保障.

本文采用馬爾可夫鏈分析拜占庭容錯模型的可靠性，為四模冗余拜占庭容錯計算機設計提供參考.

1 拜占庭容錯計算機模型

在容錯計算機里多機間通信是實現容錯的瓶頸，為盡可能減少開銷，需要采用硬件實現多機間的通信.采用額外硬件——網絡單元(NE，network element)來連接冗余多機.NE實現冗余多機間同步、數據通信和數據表決等容錯相關功能，而處理器負責執行應用程序、調度和重構等復雜任務.使用這種體系結構就是為了解決上述3個問題:①通過獨立的硬件實現并維持多機間的數據一致性，避免主處理器進行頻繁的數據通信和數據表決等任務，減輕主處理器的容錯開銷;②提供多機實現的靈活性，使得支持異構處理器、操作系統和應用軟件的多機成為可能;③層次化的容錯策略可以使應用軟件盡可能少的與容錯策略實現的細節耦合[2].

根據拜占庭恢復的理論需求，采用的拜占庭恢復容錯計算機的結構方案[2]為:4個故障包容區域(FCR，fault containment region)，每個包含一個處理單元(PE)和一個NE，其中PE是執行應用程序、調度和重構任務的單板計算機，NE是實現同步、數據傳遞和數據表決等容錯相關功能的硬件，4個NE通過完全連接提供1-拜占庭故障恢復，如圖1所示.

圖1 拜占庭容錯系統模型Fig.1 Byzantine fault tolerantmodel

此系統中每個處理器都連接自己的傳感器組，通過兩輪輸入一致交換使得系統中所有處理器都獲得此傳感器組的值(解決輸入一致問題);每個處理器都連接執行機構，通過仲裁算法確定某個無故障處理器當班控制輸出(解決輸出沖突).

2 可靠性分析

本節采用馬爾可夫鏈分析拜占庭容錯模型的可靠性.系統失效概率記為Psysloss，可靠性定義為1-Psysloss.系統失效概率又可分為停機失效概率Pshutdown和不安全失效概率Punsafe，其中停機失效定義為系統檢測到故障的主動停機狀態，而不安全失效定義為系統發生故障未被檢測的不安全狀態.對于空間應用的星載計算機來說，Psysloss是Pshutdown與Punsafe的總和，由于傳統的容錯方法通過冗余備份能夠很好地解決系統停機失效的問題，因此本節的可靠性分析著重于拜占庭容錯對改善系統不安全失效的概率上.PE和NE的失效概率分別記為λPE和λNE，根據文獻[3]λPE的典型數值取10-4h-1;由于NE比PE簡單，因此NE的失效概率要低，根據文獻[4]λNE的值取1.4×10-5h-1.PE和NE的故障恢復率(故障恢復時間的倒數)分別記為uPE和uNE，為簡便起見，uPE和uNE的值都取103h-1[5].參數fc指故障能夠被系統檢測到的概率，稱之為故障檢測率.對于單機系統，可以采用自測試、超時、重試和滾回等操作來恢復故障，其故障檢測率fc通常在0.8到0.95之間，這里取0.8來分析.本文的方案滿足1-拜占庭恢復條件[2]，因此，對于單個故障可以達到100%的檢測率，即fc=1.ft指當發生故障時，瞬時故障所占的比率，這里取0.5.

2.1 單機系統可靠性分析

傳統單機系統的馬爾可夫模型如圖2所示，共包括以下4種狀態:狀態1，零故障狀態;狀態2，檢測故障的重試或滾回狀態;狀態3，發生永久故障的停機失效狀態;狀態4，未檢測故障的不安全失效狀態.當系統檢測到故障時進入狀態2，如果發生的是瞬時故障，系統通過重試或滾回操作可以恢復故障返回狀態1;如果發生的是永久故障，系統將進入狀態3.當系統發生故障而沒有被檢測到時，系統進入狀態4.圖3是單機系統在fc=0.8時停機失效Pshutdown和不安全失效Punsafe的概率.

圖2 單機系統馬爾可夫鏈Fig.2 Markov chain for simplex system

單機系統在工作10h后Psysloss為其中為這不滿足文獻[1]中的10h運行的需求.

2.2 本文模型可靠性分析

由于本文拜占庭容錯模型的馬爾可夫鏈取決于所采用的容錯方案，下面根據不同的容錯方案分析第1節拜占庭容錯系統模型的可靠性.

方案1.系統一直工作在拜占庭恢復模式，當出現第一個NE永久故障(不滿足拜占庭恢復條件)時系統安全停機.由于本文的系統模型是拜占庭恢復結構，當出現任意單個故障，系統都能夠容忍，也就是說fc等于1.方案1的馬爾可夫鏈如圖4所示，其中包括兩組工作狀態:停機失效以及不安全失效狀態.第一組工作狀態包括狀態1、2、3和5.狀態1是初始零故障狀態，當PE故障時，系統轉換到狀態2(PE故障恢復狀態)，相應的，任意單個NE故障時，將使系統從狀態1轉換到狀態3(NE故障恢復狀態).如果上面發生的是瞬時故障，系統將返回狀態1;如果在狀態2或3發生第二個故障，系統將轉換到狀態10(不安全系統失效狀態)，但當發生的這兩個故障是一個FCR內的PE和NE時系統轉移到狀態5.狀態5同時存在PE和NE故障，此時將首先恢復NE故障.在狀態3和狀態5時，如果發生的是NE永久故障，將導致系統轉換到狀態11(停機失效狀態)，因為NE故障意味著相應的FCR故障，此時無故障FCR不滿足最少拜占庭恢復的基數需求.在狀態5，重構一個瞬時NE故障將返回狀態2.如果狀態2的PE是永久故障，系統將進入狀態4.

狀態4時系統進入第二組工作狀態(狀態4、6、7、8和9)，此時系統包含3個工作PE和4個工作NE，系統仍然滿足1-拜占庭恢復條件，因此仍然能夠容忍任意單個故障.其中3個處理器提供故障屏蔽能力，4個NE滿足1-拜占庭恢復的基數、互連和同步需求.因此，狀態4是降級拜占庭恢復結構的初始狀態.

在狀態4，PE故障將轉換到狀態6，如果發生的是瞬時故障，系統將返回狀態4;如果是永久故障，系統將進入停機失效狀態.如果在狀態6時又發生一個部件故障將使得系統進入不安全失效狀態.同樣，如果發生的是PE/NE故障對，使得系統進入狀態9.在狀態4，如果帶有工作PE的NE故障將進入狀態8，如果發生的是瞬時故障，系統返回狀態4，否則進入停機狀態.在狀態8，如果又發生故障，系統進入不安全失效狀態.同樣，PE/NE對失效時進入狀態9.在狀態4時，如果不含PE的NE故障，系統將進入狀態7，狀態7和狀態8不同的是它不能進入狀態9(PE/NE故障狀態).狀態9和狀態5一樣，系統首先恢復NE，如果成功恢復則進入狀態6，否則進入狀態11.此方案中，如圖5所示.

從圖5中可以看出，Punsafe比Pshutdown低5個數量級，因此Psysloss基本等于Pshutdown的值.在10h運行后，這比單模系統的Pshutdown還高，這是因為系統的4個FCR中有一個FCR故障的概率比單模系統FCR故障的概率要高.但如果系統仍有冗余備份資源，通過對故障機的替換繼續工作在拜占庭恢復模式，可以使系統停機失效的概率即Pshutdown的值接近于0，此時系統失效的概率基本等于不安全失效的概率即

圖4 方案1的馬爾可夫鏈Fig.4 Markov chains for redundancy scheme 1

圖5 方案1的 P shutdown和 P unsafe概率Fig.5 P shutdown and P unsafe for redundancy scheme 1

方案2.當出現第一個NE永久故障時系統降級為單模系統繼續工作.在圖4的基礎上將狀態11替換為圖6的4個狀態，即可得到此方案的馬爾可夫鏈，其中如圖7所示.10h運行后，h-1，這比方案1要低好幾個數量級，但是比方案1要高一個數量級，這是因為方案2允許系統在非拜占庭恢復模式工作，這降低了Pshutdown，同時增加了Punsafe.

圖6 方案2增加的馬爾可夫鏈Fig.6 Additive Markov chains for redundancy scheme 2

方案3.當出現第一個NE永久故障時系統降級為三模系統繼續工作，當出現第二個NE永久故障時系統安全停機.在圖4的基礎上，將狀態11替換為圖8的8個狀態，即可得到此方案的馬爾可夫鏈.圖8中狀態11是3個FCR工作狀態，從圖4的狀態3、5、7中而來.這里的狀態13、14和圖4中的狀態2、3相似，所不同的是，三模系統是非拜占庭恢復結構，當系統發生拜占庭故障時系統不能檢測.因此在狀態11時，如果發生檢測到的NE故障，系統進入狀態13(NE故障恢復狀態);否則，如果發生未檢測的拜占庭故障，系統將進入狀態18.同樣，如果發生檢測的PE故障，系統進入狀態14，否則，系統進入狀態18.圖8中狀態12是4個NE和兩個PE工作狀態，這是從圖4的狀態6進入的，也不滿足拜占庭恢復條件.

圖7 方案2的 P shutdown和 P unsafe概率Fig.7 P shutdown and P unsafe for redundancy scheme 2

圖8 方案3增加的馬爾可夫鏈Fig.8 Additive Markov chains for redundancy scheme 3

不同容錯方案在工作10h的可靠性分析總結如表1所示.

表1 可靠性分析總結Tab.1 Reliability analysis summary h-1

3 結 論

通過本文分析可以看出，工作在拜占庭恢復模式下系統具有最小的不安全失效概率.如果系統有額外備份資源可用，通過對故障機的替換，系統就不會發生停機失效，因此系統的失效概率等于不安全失效的概率，所以系統一直工作在拜占庭恢復模式可以獲得最高的可靠性.如果系統沒有額外的備份資源，通過降級工作在非拜占庭恢復模式下，這可以降低系統停機失效的概率，同時增加系統的不安全失效概率，當兩者的和最小時系統獲得最高可靠性.因此，系統采用何種方案降級工作取決于系統Pshutdown和Punsafe之間的關系.

圖9 方案3的 P shutdown和 P unsafe概率Fig.9 P shutdown and P unsafe for redundancy scheme 3

[1]LALA JH，HARPER R E.Architectural principles for safety-critical real-time applications[C]//Proceedings of the IEEE.Cambridge:IEEE，1994:25-40.

[2]XIAO A B，YANG M F，LIU B.Design and validation of Byzantine fault tolerance for on-board computer[J].Aerospace Control and Application， 2008，34(4):17-22.

[3]WENSLEY J.SIFT:the design and analysis of a fault tolerant computer for aircraft control[C]//Proceedings of the IEEE.Cambridge:IEEE，1978:1240-1255.

[4]HARPER R.Critical issues in ultra-reliable parallel processing[D].Cambridge:Massachusetts Institute of Technology，1987.

[5]HOPKINS A L，SMITH T B，LALA J H.FTMP-A highly reliable fault-tolerant multiprocessor for aircraft[C]//Proceedings of the IEEE.Cambridge:IEEE，1978:1221-1239.