分布式嵌入系统中的交互一致性

许多应用与人身安全或设备安全有密切联系，随着安全性要求的提高，希望设备或系统在其构成的部件与控制装置发生故障时仍能保证安全，即故障-安全（failsafe）的特性。系统是由子系统组成的，子系统有故障时有控制地停止工作（failsilent，故障-静默模式），对系统而言仍是故障，因为它不再提供原定的服务了，这有可能引起全系统功能的失效。所以，安全是要从最高层的全局来分析的。例如对一辆汽车，刹车系统整体不能用故障-静默来达到安全，而应该是故障后仍能工作（failoperatiONal，故障-仍工作模式），或至少是性能下降一点仍能工作（faildegraded，故障-降格工作模式）。

单一部件的架构（包括硬件与软件）有故障而失效时就无法继续提供服务了，它不能满足故障-仍工作模式或故障-降格工作模式的要求。这就必须采用有备份的冗余架构，每一个备份都能完成出故障的原来部件的大部分或全部服务工作，维持系统正常运行。备份工作的交替就要求它们对工作状态（系统的输入、应该的输出和谁不该输出）有相同的看法。这种相同的看法要通过信息交换并通过协议才能建立，并称为交互一致性（interactive consiSTency）。

有一部分控制对象存在功能上互为冗余的可能性，例如汽车的4个轮子的刹车，当一个轮子的子刹车系统（设备或控制装置）有故障时，修正其他轮子的刹车力便可以实现总体刹车系统的故障-仍工作模式或故障-降格工作模式。此时对单个轮子而言，它只要能实现故障-静默即可。显然，单个轮子的可信赖性要求被降低，会造成成本的大大降低。在这种情况下，轮子的控制器之间就存在交互一致性问题。

来自汽车电子大佬Infineon和Delphi的研究报告[1]比较了基于这种互为冗余的分布式冗余刹车系统与集中式仅控制器冗余的硬件成本，指出成本可大为下降，并称集中式有控制器冗余的刹车系统将会废止，这对我国汽车电子业者有警示意义。不过，该文并未提到用硬件集中方案也可实现对象互为冗余的刹车系统（这二种方案成本差别将不会太大）。此时由于通信有较大不同，交互一致性问题会不一样，加上其他因素，它们的优劣有待研究。但至少分布式互为冗余刹车系统是一个备选方案。参考文献[1]非常概述地提及了控制方案，并未谈及技术细节以及采用的协议。本文将根据交互一致性的理论，对实施这类应用中可能遇到的问题进行分析。

1 SM算法

对交互一致性的研究已经有30年了，它被称为拜占庭将军问题算法（Byzentine Generals Problem）。原始文献有2个版本[23]，1980年的文章引用很多，但是公认很难读懂[4]。原来的讨论是针对点对点通信进行的，本文根据对参考文献[3]的理解，针对总线方式通信加以展开，这会引入作者的看法。参考文献[3]提出：一个冗余系统的“所有无错节点应该采用同样的输入（这样才能产生同样的输出）；如果输入系统没错，就应该采用输入的值（这样才能产生正确的输出）”。参考文献[3]提供了二种解决算法：一是口传消息算法OM（Oral Message Algorithm），二是签名消息算法SM（Signed Message Algorithm）。对容许m个错而言，OM算法需要3m+1个节点以及m+1轮消息传送，SM需要m+2个节点和m+1轮消息传送。这是2种原理与性能有很大差别的算法。OM算法依靠消息转述与表决来确定从节点的输入，当无法进行表决时要采取预定义的缺省输入。当主节点有拜占庭错且错值占多数时，无错的从节点间看法虽是一致的，但是是不正确的。SM算法依靠逐级检验与重复转发，可以发现各节点（包括主节点）的错，而且只要有一次正确收到就可以了。由于性能好且需要的从节点数较少，SM值得进一步探究。下面以总线通信时的情况来介绍SM的做法。

① 对需要交换数据并保证一致的n=m+2个节点而言，可将问题作分解，每个节点可轮流作为主节点对其他节点传送消息，实施SM算法。

② 每个通信帧含有两部分内容：数据d和与d有关的签名a。根据参考文献[3]，签名要不被有错节点作伪，应该各节点各不相同且每次都不同。笔者认为根据工业应用可以不这样要求，详见后文。

③ 通信各轮的帧内容如下：

第1轮，主节点发自己的数据与签名(d:a0);

第2轮，各从节点转发由第1轮收到的帧再加自己的签名((d:a0):aj)，其中 (j=1，…，n-1);

以后各轮，各从节点转发由上一轮收到的帧再加自己的签名((…((d:a0):aj)…):ar)，其中 (j,…,r∈{1,…,n-1}; j≠…≠r)，也就是说已经经过本从节点转发的内容不再转发。

由于是通过总线广播而不是点到点通信，通信量只要计算不同