四模冗余拜占庭容错计算机可靠性分析*

肖爱斌，胡明明，任宪朝，李 森，杨 樑

(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.