星载计算机拜占庭容错设计与验证

肖爱斌，杨孟飞，刘 波

（1.北京控制工程研究所，北京100190；2.中国空间技术研究院，北京 100094）

星载计算机拜占庭容错设计与验证

肖爱斌1，杨孟飞2，刘 波1

（1.北京控制工程研究所，北京100190；2.中国空间技术研究院，北京 100094）

为确保载人航天器的安全可靠，载人航天器控制计算机一般需具备拜占庭故障恢复的能力。根据拜占庭恢复理论，提出一种拜占庭容错计算机实现的原理性方案，然后对这种拜占庭容错方案进行了原型实现和验证，实验结果表明了方案的可行性和有效性。

星载计算机；拜占庭恢复；数据一致性；容错

1 引 言

星载控制计算机是卫星的关键部件，其可靠性直接关系到卫星能否正常运行和完成预定任务。为了保证计算机能在恶劣的太空辐射环境中长期可靠工作，需要对其进行专门的加固和冗余容错设计。对于载人航天器，由于涉及到乘员的安全，控制计算机在完善单机设计外，通过精巧的冗余设计来增强整个计算机系统容忍故障的能力尤为必要。学术界和防御研究机构提倡，对于载人航天器这样有关键安全性需求的设备或系统，可以使用足够硬件冗余来满足容忍任意故障模式的需求。容忍任意故障模式称作拜占庭恢复（Byzantine resilience）［1］，由于拜占庭恢复系统通过硬件冗余来屏蔽隐藏的未知故障引起的模块或单机失效，因此具有极高的可靠性，使星载计算机在关键安全、可靠性方面的指标得到有效保障。

星载计算机实现拜占庭容错的关键是要保证冗余部件间的数据一致性，冗余部件基于输入一致进行完全相同的处理，然后根据输出一致来检测和屏蔽任意模式的故障。本文提出一种拜占庭容错计算机实现的原理性方案，重点就是设计与验证了这样一种数据一致性的协议及其实现机制。

2 拜占庭容错理论基础

当单个独立的计算机系统不能满足应用的可靠性需求时，一种解决方案是采用多个冗余系统同时并行处理同一项任务。假设冗余系统里所有的冗余部件相互隔离，则它们全失效的概率小于一个非冗余系统失效的概率。因此，冗余系统能够获得更高的可靠性。

然而构造冗余系统比较困难。例如，由多个节点组成的冗余系统控制航天器，当航天器收到各个节点不一致指令时，一种可能性是给系统另外增加一个仲裁的节点，并且该节点有最高的决定权。如果仲裁的节点失效，整个系统就失效，从而导致系统可能不比单节点系统可靠。对于超可靠的容错系统，一种可能的解决方案是采用如下的表决方案来替代原方案：每个节点都连接到执行机构上，只要有效节点的个数多于失效节点，系统就有效，这个方案主要用来解决输出冲突问题。

对于较难解决的输入一致的问题，需考虑一个系统的多个节点要从传感器上读取信息。这存在两种可能的设计：一种是每个节点配置自己的传感器，这样各节点可能读取不同的信息，从而产生不同行为，最终导致各个节点由于进入不一致的状态而终止运行；另一种设计是采用单一传感器向各个节点发送信息，如果传感器失效，就有可能发送不同的信息到各个节点，同样会引起节点间出现分歧。两种设计的共同问题是需要一种使所有节点达成一致的办法。

使多个节点保持一致的问题可以归纳为如下3种问题［2］：1）一致问题（consensus problem），每个节点有各自的初始值，目标是处理后各个节点都能得到相同的值；2）交互式一致问题（interactive consistency problem），每个节点也有各自的初始值，其目标是处理后各个节点的值应该等于系统中各个节点应有的值序列，即处理后每个节点应该有同样的向量（V1，V2，V3…），其中 Vi是第 i个节点的初始值；3）拜占庭将军问题［3］（Byzantine generals problem），某个节点有要发送到其他节点的值，需要保证所有其他节点对这个值达成一致。它们的相互关系如表1所示。这些问题的难点在于，当一些参与运行的节点失效时，如何正确处理。

拜占庭将军问题是这3种问题中的核心，解决了拜占庭将军问题也就解决了另外两个问题：交互式一致问题可以通过多次简单的重复拜占庭将军问题来解决，使得每个节点的值都达成一致。而且一旦交互式一致问题解决了，每个节点都会有相同的向量值，依据该一致的向量值，每个节点就可以通过简单地挑选多数值（或者平均值，或者任何别的选择函数的结果），从而解决了一致问题。

表1 3种问题的关系

拜占庭将军问题被广泛研究，形成了大家所熟悉的、理论上可论证的容忍f个拜占庭故障必须满足的先决条件：

1）至少存在 3 f+1个故障包容区（FCR，fault containment region）［4］；

2）每个FCR与其他至少2 f+1个FCR维持独立的通信链路［5］；

3）FCR之间必须至少维持f+1轮通信［6］；

4）所有FCR必须同步到一定的时域内（时差上限确定）［7］。

符合以上条件的体系结构，称为f-拜占庭恢复容错结构。其中FCR是指容错计算机中的每个单机都是一个故障包容区域，不同FCR内发生故障的概率统计是独立的。FCR在体系结构上的特点为［8］：物理隔离、电气隔离、独立电源和独立时钟。在1-拜占庭恢复容错结构里，必须拥有4个FCR，每个FCR通过3条独立通信链路和其他FCR相连，FCR之间需要执行两轮交换以获得一致性判决。

3 星载计算机拜占庭容错方案

前节对实现拜占庭容错的理论基础及必要条件进行了分析，为了使输入信息达成一致，系统必须进行两轮交换。这是满足一致性协议必须发生的最低通信轮数，这意味着使信息通信开销小的唯一方法是提供高效实现f+1轮通信的机制。另外，为实现拜占庭容错所有FCR必须同步到一定的时间域内，可以采用硬件同步或软件同步的方法。硬件同步存在的问题一个是系统开销大，另一个很严重的问题是时钟确定性限制，即冗余处理器在给定数目时钟周期内必须执行相同数量的指令，这就限制处理器硬件设计，不适合异构处理器使用。软件同步存在的问题是编程限制，不像硬件同步那样，同步对程序员不透明。总的说来，星载计算机拜占庭容错需要解决以下3个问题：

1）提供高效实现两轮通信的机制；

2）提供适合异构处理器、操作系统和应用软件的同步机制；

3）容错对应用程序员透明。

为解决这3个问题，我们采用了以下的拜占庭恢复系统模型。

3.1 拜占庭容错系统模型

在容错计算机里多机间通信是实现容错的瓶颈，为尽可能减少开销，需要采用硬件实现多机间的通信。我们采用额外硬件——网络单元（NE）来连接多机，NE实现多机间同步、数据通信和数据表决等容错相关功能，而处理器负责执行应用程序、调度和重构等复杂任务。使用这种体系结构就是为了解决下述3个问题：1）通过独立的硬件实现并维持多机间的数据一致性，避免主处理器频繁的数据通信和数据表决等任务，减轻主处理器的容错开销；2）提供多机实现的灵活性，使支持异构处理器、操作系统和应用软件的多机成为可能；3）层次化的容错策略也可以使应用软件尽可能少地耦合进容错策略实现的细节。

基于上述想法，根据拜占庭恢复的理论需求，本文采用的拜占庭恢复容错计算机的结构方案为：4个FCR，每个FCR包含1个处理单元（PE）和1个网络单元（NE），其中 PE是执行应用程序、调度和重构任务的单板计算机，NE是实现同步、数据传递和数据表决等容错相关功能的硬件，4个NE通过完全连接提供1-拜占庭故障恢复，如图1所示。

图1 拜占庭容错模型

此系统中每个处理器都连接自己的传感器组，通过两轮输入一致交换使系统中所有处理器都获得此传感器组的值（解决输入一致问题）。每个处理器都连接执行机构，通过仲裁算法确定某个无故障处理器当班控制输出（解决输出冲突）。

系统的控制周期如图2所示，其工作过程如下：加电后控制周期开始，每个处理器采集各自传感器的数据；将它采集的数据给NE进行两轮一致交换；读出 NE交换后的一致数据（A、B、C、D）；对这些一致的数据进行运算处理；把处理完的结果给NE发送；读出NE交换后的结果；将其传送给执行机构。

图2 系统控制周期

单源信息输入一致的两轮交换是系统拜占庭恢复的基础。在这类交换中，交换的信息是某个处理器专有的信息，例如其传感器的数据或处理器的内部状态数据，因此需要两轮交换。第一轮，发起一致交换的处理器发送其专有信息给其他处理器；第二轮，其他处理器接收到信息后转发其所接收的信息，之后对其所接收的3份信息进行多数表决达成一致。

这里采用的同步称为功能同步［8］，当它在系统控制周期内需要进行一致交换时提供同步请求。处理器间通过信息发送和接收保证同步，在一致交换开始时发送消息给对方，然后等待接收那一消息；在接收消息时，冗余节点通过底层NE集合的操作保证同步。功能同步具有潜在的效率并可实现对程序员透明，还可以避免系统中必须使用同种冗余节点的限制，其优点包括实现时钟非确定、异构处理单元的系统和硬件软件设计多样性能力。

3.2 数据一致性协议设计

系统控制周期中处理器的数据一致交换及表决的过程都是由NE来实现的，处理器之间通过NE的信息交换维持同步和一致。因此这种拜占庭恢复系统维持同步和数据一致最关键的就是NE单元的设计。下面着重对NE的数据一致性协议以及协议的实现进行论述。

处理器之间通过NE信息交换的方法进行通信，维持同步和数据一致。NE信息交换是系统拜占庭恢复的基础，它使得NE集合同步并保持全部信息交换次序而不对处理器增加时钟确定的限制。NE内部设有4个先进先出存储器（CH0FIFO、CH1FIFO、CH2FIFO和 CH3FIFO），分别用于存放自身NE发出的信息以及接收右面、对面和左面NE发出的信息。NE信息交换协议的时序如图3所示。

NE信息交换是4个输入一致两轮交换的优化，让这4个两轮交换的第1轮同时进行，第1轮结束后按照次序一次转发A、B、C、D的数据。这样做的好处是一方面节省了4个两轮交换的时间，另一方面保证了4个NE在相同时间以相同次序向处理器提供两轮交换表决后的4个数据。

处理器在写数据给NE后启动超时，记录从写数据给NE到从NE接收数据的时间，同样NE在发送处理器的数据后启动超时，记录自己发送数据后到接收到其他NE发送数据的时间，当然NE超时时间的设置比处理器的要短。处理器和NE都是通过在发送信息后等待接收相应信息来实现同步的。

NE信息交换发送阶段，每个NE都发送自己的FIFO数据到所有其他NE和它自身（CH0FIFO），然后NE等待直到接收完其他3个NE发出的信息。这一过程同步处理器PE和NE各处理1次。这时每个NE的4个接收FIFO里共存有1份对方的数据。

NE信息交换转发A阶段，每个NE都转发NE A FIFO的数据到所有其他NE和它自身，然后NE等待直到接收完其他3个NE转发A的信息。这一过程同步1次NE。

NE信息交换转发B阶段，每个 NE都转发NE B FIFO的数据到所有其他NE和它自身，然后NE等待直到接收完其他3个NE转发B的信息。这一过程同步1次NE。

NE信息交换转发C阶段，每个 NE都转发NE C FIFO的数据到所有其他NE和它自身，然后NE等待直到接收完其他3个NE转发C的信息。这一过程同步1次NE。

图3 NE信息交换协议时序

NE信息交换转发D阶段，每个NE都转发NE D FIFO的数据到所有其他NE和它自身，然后 NE等待直到接收完其他3个NE转发D的信息。这一过程同步1次NE。这时每个NE FIFO中的数据如图4所示。

这时，每个NE的4个接收FIFO里各存有1份NE数据。注意这4份数据中有2份是有源NE发出的，其中1份是源NE第1轮发送的，另1份是源NE第2轮发送的。根据文献［4］，为满足输入一致需求，在表决这4份数据时必须将第2轮源NE发出的数据屏蔽掉，否则源NE发送的两份数据将损害表决结果。因此，接下来表决的是 A、B、C、D除源NE FIFO以外的3份数据，并将表决后的数据以及表决过程中产生的错误症状、超时错误和链路错误等信息写回接收FIFO，供处理器读取。

图4 NE信息交换转发D阶段

现在分析该信息交换协议是如何容忍拜占庭故障的。假设 A、B、C、D 4机分别发送 1、2、3、4的数据，其中C机发生拜占庭故障。

首先，每机发送自己的消息给对方。其中 A、B、D机发送的是其真实值，而C机可能对其他机发送不同的信息。则在第1步后每机都会有1个所有机的信息矢量，如下所示：

A机：（1，2，x，4）

B机：（1，2，y，4）

C机：（1，2，3，4）

D机：（1，2，z，4）

可以看出C机向其他3机发送了不一样的数据，但现在无故障的机器还不能判定谁发生了故障，因此每机将自己接收到的信息再向其他机器转发，也即将上述的信息矢量发送给其他机器，这样每台机都会生成一个矩阵，如下所示：

最后，每机按照少数服从多数的原则，对矩阵的每一列进行选择，如果在某一列中的某个数占多数（在表决第i列时，应将对应第i行的数除外），则选择这个值作为最后的结果；如果列中没有哪个数占多数，则该列表为 UNKOWN，通过表决，A、B、D 3机一致认为C机发生拜占庭故障，如下所示：

A机：（1，2，UNKOWN，4）

B机：（1，2，UNKOWN，4）

D机：（1，2，UNKOWN，4）

在表决C机的数据时，虽然没有某个数占多数，但各机中参与表决的3个数是一样的，都是（x，y，z），那么各机表决得出得结果也必定是一致的。可见，A、B、D 3机实现了协调一致，得出了共同的结果。

4 方案验证与性能评估

根据前一节的拜占庭容错方案以及数据一致性协议，完成最终电装、调试后的拜占庭容错硬件系统如图5所示。由于系统的核心功能（包括处理器和NE）都集中在FPGA中实现，因此，本系统中的核心器件是Xilinx公司的100万门FPGA XC3S1000。为了实现 NE间的通信，采用了 4路LVDS串口通过网线口连接。另有两路 RS232串口，用于PC机与NE板之间的通信，方便系统的调试。每块板上都有8位拨码开关用作系统的输入，其下方的8盏灯则是系统的输出。另外，板上还有片外SRAM和EEPROM等。

图5 验证平台

4.1 协议功能验证

为了能够对NE信息交换的内部数据进行观测，在 PC机上运行 1个终端程序，终端程序用Microsoft Visual Studio 6.0软件包中的Visual C++6.0开发，其界面如图6所示。其中接收数据列分别表示第1轮接收到的A、B、C、D机的数据；表决后数据是第2轮交换表决后的 A、B、C、D机的数据；表决症状的 5、6、7、8位分别表示在表决 A、B、C、D机的数据时是否发生不一致，1、2、3、4位分别表示在表决过程中A、B、C、D机的数据是否与表决后的数据不一致；超时错误和链路错误的1、2、3、4位表示信息交换过程中A、B、C、D机是否发生超时和链路错误。

现在让 A、B、C、D 4机分别发送 01、02、03、04的8位数据，其中的B机发生拜占庭故障，对 A、C、D机分别发送十六进制为 F4、F2和 F3的数据（通过板上跳线控制实现）。这时 A、B、C、D机的终端程序数据显示如图6～9所示。

从4机终端程序的表决症状（二进制为0010 1011的8位数）可以看出，在表决B机的数据时A、B、D机收到的数据与表决后数据不一致。这存在两种可能：1）B机发生拜占庭故障，发给 A、C、D机不一致的数据；2）A、B、D 3机说谎。由于系统容错的前提是4台机器中只有1台发生任意模式的故障，因此只可能是B机发生拜占庭故障，并且最后A、B、C、D 4机获得的数据集合（ABCD）是一致的，都是（01 F2 03 04），也就是说即使B机发生拜占庭故障，对A、C、D机发送不一致的数据，系统仍能达成一致。这说明此系统具有对拜占庭故障容忍的能力。

图6 A机的串口终端程序

图7 B机的串口终端程序

图8 C机的串口终端程序

4.2 性能评估

本系统中采用的晶振为29.4912 MHz，并通过数字时钟管理模块（DCM）的4倍频处理，因此系统实际时钟为117.9648 MHz，1个时钟为8.4771 ns。根据设计，发送1个码元（即1比特数据）需要16个波特率使能周期，而1个波特率使能周期又需要若干个时钟。

图9 D机的串口终端程序

对于4块NE板之间的串口通信，采用基于低电压差分信号（LVDS）物理层的异步串行总线协议传输，可以达到较高的通信速率。这里设计为2个时钟产生1个波特率使能周期，此4块NE板之间的串口通信速率应为

29.4912×4×1/16×1/2=3.6864MB

对于4块NE板与PC机间的通信部分，采用基于RS-232物理层的异步串行总线协议传输，通信速率较低。这里设计为192个时钟产生1个波特率使能周期，此NE板与PC机之间的串口通信速率应为

29.4912×4×1/16×1/192=0.0384MB

根据异步串行通信协议，NE板之间发送1字节数据包括1起始位、8数据位、1校验位、2停止位共12比特数据，由于发送1比特数据需要32个时钟，因此发送1字节数据需要 384个时钟，合计3.2552μs。

根据信息交换协议，完成1次信息交换最好情况是4机完全同步，每次都不需等待，因此信息交换时间是串口发送5个字节的时间，即16.276μs。

完成1次信息交换最坏情况是有故障机器停止发送信息，这样每次都需等待最长时间。这里设置PE超时为发送44个同步字的时间，NE超时为发送12个同步字时间，再加上发送5个字节的有效数据，因此等待最长时间为（44+12+5）×3.2552μs=198.5672μs。

由于4机之间或多或少存在偏差，不可能达到完全同步，因此完成1次信息交换的时间在16.276μs～198.5672μs之间。

实测数据表明，系统控制周期中的 A、B、C、D输入一致交换所花费的时间在16.2μs～200μs之间，通常仅在20μs左右，这是可以接受的。

5 结 论

本文根据拜占庭恢复理论，提出一种拜占庭容错星载计算机实现的原理性方案，然后对这种拜占庭容错方案进行了原型实现和验证，实验结果表明了方案的有效性和可行性。同时，理论分析和实现经验证明这种方案具备两个突出优点：一是通过独立的硬件实现并维持多机间的数据一致性，有效减轻了主处理器的容错开销；二是基于数据一致性机制，多机采用消息进行多机间的功能同步，与时钟紧密同步相比，新的方案使得异构处理器冗余应用成为可能；另外，层次化的容错策略也可以使应用软件尽可能少地耦合进容错策略实现的细节。

［1］ Lala J H，Harper R E.Architectural principles for safety-critical real-time applications［J］.Proceedings of the IEEE，1994，82（1）：25-40

［2］ Barborak M，Dahbura A，Malek M.The consensus problem in fault-tolerant computing ［J］.ACM Computing Surveys（CSUR），1993，25（2）：171-220

［3］ Pease M， Lamport L， Shostak S.The Byzantine generals problem ［J］.ACM Trans.Programming Languages and Systems，1982，4（3）：382-401

［4］ Pease M，Shostak R，Lamport L.Reaching agreement in the presence of faults［J］.Journal of ACM，1980，27（2）：228-234

［5］ Dolev D.The Byzantine generals strike again［J］.Journal of Algorithms，1982，14（3）：14-30

［6］ Fischer M，Lynch N A.A lower bound for the time to assure interactive consistency ［J］.Information Processing Letters，1982，14（4）：183-186

［7］ Dolev D，Dwrok C，Stockmeyer L.On the minimal synchronism needed for distributed consensus［R］.IBM Research Report，RJ4292（46990），IBM，May 1984

［8］ Harper R.Critical issues in ultra-reliable parallel processing ［D］.PhD Dissertation， Massachusetts Institute of Technology，Cambridge，MA，June 1987

Design and Validation of Byzantine Fault Tolerance for On-Board Computer

XIAO Aibin1，YANG Mengfei2，LIU Bo1
（1.Beijing Institute of Control Engineering，Beijing 100190，China；2.China Academy of Space Technology，Beijing 100094，China）

The on-board computer（OBC）that controls a manned spacecraft must be extremely reliable.Such a computer system generally has the ability of Byzantine fault resilience.Based on the theory of Byzantine resilience，a conceptual design of the Byzantine fault tolerant computer implementation is proposed.The feasibility of this scheme is validated in the real system through experiments.

on-board computer；Byzantine resilience；data consistency；synchronization

V446

A

1674-1579（2008）03-0017-06