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

許多應用與人身安全或設備安全有密切聯(lián)系，隨著(zhù)安全性要求的提高，希望設備或系統在其構成的部件與控制裝置發(fā)生故障時(shí)仍能保證安全，即故障-安全（failsafe）的特性。系統是由子系統組成的，子系統有故障時(shí)有控制地停止工作（failsilent，故障-靜默模式），對系統而言仍是故障，因為它不再提供原定的服務(wù)了，這有可能引起全系統功能的失效。所以，安全是要從最高層的全局來(lái)分析的。例如對一輛汽車(chē)，剎車(chē)系統整體不能用故障-靜默來(lái)達到安全，而應該是故障后仍能工作（failoperatiONal，故障-仍工作模式），或至少是性能下降一點(diǎn)仍能工作（faildegraded，故障-降格工作模式）。

　　單一部件的架構（包括硬件與軟件）有故障而失效時(shí)就無(wú)法繼續提供服務(wù)了，它不能滿(mǎn)足故障-仍工作模式或故障-降格工作模式的要求。這就必須采用有備份的冗余架構，每一個(gè)備份都能完成出故障的原來(lái)部件的大部分或全部服務(wù)工作，維持系統正常運行。備份工作的交替就要求它們對工作狀態(tài)（系統的輸入、應該的輸出和誰(shuí)不該輸出）有相同的看法。這種相同的看法要通過(guò)信息交換并通過(guò)協(xié)議才能建立，并稱(chēng)為交互一致性（interactive consiSTency）。

　　有一部分控制對象存在功能上互為冗余的可能性，例如汽車(chē)的4個(gè)輪子的剎車(chē)，當一個(gè)輪子的子剎車(chē)系統（設備或控制裝置）有故障時(shí)，修正其他輪子的剎車(chē)力便可以實(shí)現總體剎車(chē)系統的故障-仍工作模式或故障-降格工作模式。此時(shí)對單個(gè)輪子而言，它只要能實(shí)現故障-靜默即可。顯然，單個(gè)輪子的可信賴(lài)性要求被降低，會(huì )造成成本的大大降低。在這種情況下，輪子的控制器之間就存在交互一致性問(wèn)題。

　　來(lái)自汽車(chē)電子大佬Infineon和Delphi的研究報告[1]比較了基于這種互為冗余的分布式冗余剎車(chē)系統與集中式僅控制器冗余的硬件成本，指出成本可大為下降，并稱(chēng)集中式有控制器冗余的剎車(chē)系統將會(huì )廢止，這對我國汽車(chē)電子業(yè)者有警示意義。不過(guò)，該文并未提到用硬件集中方案也可實(shí)現對象互為冗余的剎車(chē)系統（這二種方案成本差別將不會(huì )太大）。此時(shí)由于通信有較大不同，交互一致性問(wèn)題會(huì )不一樣，加上其他因素，它們的優(yōu)劣有待研究。但至少分布式互為冗余剎車(chē)系統是一個(gè)備選方案。參考文獻[1]非常概述地提及了控制方案，并未談及技術(shù)細節以及采用的協(xié)議。本文將根據交互一致性的理論，對實(shí)施這類(lèi)應用中可能遇到的問(wèn)題進(jìn)行分析。

　　1 SM算法

　　對交互一致性的研究已經(jīng)有30年了，它被稱(chēng)為拜占庭將軍問(wèn)題算法（Byzentine Generals Problem）。原始文獻有2個(gè)版本[23]，1980年的文章引用很多，但是公認很難讀懂[4]。原來(lái)的討論是針對點(diǎn)對點(diǎn)通信進(jìn)行的，本文根據對參考文獻[3]的理解，針對總線(xiàn)方式通信加以展開(kāi)，這會(huì )引入作者的看法。參考文獻[3]提出：一個(gè)冗余系統的“所有無(wú)錯節點(diǎn)應該采用同樣的輸入（這樣才能產(chǎn)生同樣的輸出）；如果輸入系統沒(méi)錯，就應該采用輸入的值（這樣才能產(chǎn)生正確的輸出）”。參考文獻[3]提供了二種解決算法：一是口傳消息算法OM（Oral Message Algorithm），二是簽名消息算法SM（Signed Message Algorithm）。對容許m個(gè)錯而言，OM算法需要3m+1個(gè)節點(diǎn)以及m+1輪消息傳送，SM需要m+2個(gè)節點(diǎn)和m+1輪消息傳送。這是2種原理與性能有很大差別的算法。OM算法依靠消息轉述與表決來(lái)確定從節點(diǎn)的輸入，當無(wú)法進(jìn)行表決時(shí)要采取預定義的缺省輸入。當主節點(diǎn)有拜占庭錯且錯值占多數時(shí)，無(wú)錯的從節點(diǎn)間看法雖是一致的，但是是不正確的。SM算法依靠逐級檢驗與重復轉發(fā)，可以發(fā)現各節點(diǎn)（包括主節點(diǎn)）的錯，而且只要有一次正確收到就可以了。由于性能好且需要的從節點(diǎn)數較少，SM值得進(jìn)一步探究。下面以總線(xiàn)通信時(shí)的情況來(lái)介紹SM的做法。

　?、?對需要交換數據并保證一致的n=m+2個(gè)節點(diǎn)而言，可將問(wèn)題作分解，每個(gè)節點(diǎn)可輪流作為主節點(diǎn)對其他節點(diǎn)傳送消息，實(shí)施SM算法。

　?、?每個(gè)通信幀含有兩部分內容：數據d和與d有關(guān)的簽名a。根據參考文獻[3]，簽名要不被有錯節點(diǎn)作偽，應該各節點(diǎn)各不相同且每次都不同。筆者認為根據工業(yè)應用可以不這樣要求，詳見(jiàn)后文。

　?、?通信各輪的幀內容如下：

　　第1輪，主節點(diǎn)發(fā)自己的數據與簽名(d:a0);

　　第2輪，各從節點(diǎn)轉發(fā)由第1輪收到的幀再加自己的簽名((d:a0):aj)，其中 (j=1，…，n-1);

　　以后各輪，各從節點(diǎn)轉發(fā)由上一輪收到的幀再加自己的簽名((…((d:a0):aj)…):ar)，其中 (j,…,r∈{1,…,n-1}; j≠…≠r)，也就是說(shuō)已經(jīng)經(jīng)過(guò)本從節點(diǎn)轉發(fā)的內容不再轉發(fā)。

　　由于是通過(guò)總線(xiàn)廣播而不是點(diǎn)到點(diǎn)通信，通信量只要計算不同的幀的個(gè)數就可以:N=1+(n-1)+(n-1)2+…?？偟耐ㄐ泡啍禐閙+1。

　?、?每個(gè)從節點(diǎn)保存一個(gè)供選擇的集choice，初始化時(shí)為空：choice{Φ}。choice的更新可在m+1輪通信結束之后進(jìn)行。更新時(shí)先檢驗簽名的有效性，只有全為有效的才可把該幀的d添加到choice中，如果choice中已有，就不重復添加。點(diǎn)對點(diǎn)通信按參考文獻[3]的做法，出現主節點(diǎn)錯時(shí)choice會(huì )有多個(gè)元素，總線(xiàn)通信時(shí)主節點(diǎn)的簽名計算只有一次，按本文做法（見(jiàn)下文）choice只會(huì )有一個(gè)元素（真值或空）。

　?、?參考文獻[3]證明了在下列假設得到保證的條件下所有無(wú)故障從節點(diǎn)會(huì )得到相同的choice：

　　A1發(fā)送的消息總能正確送達；

　　A2每個(gè)節點(diǎn)知道誰(shuí)在發(fā)送；

　　A3消息的缺失可以檢測出來(lái)；

　　A4簽名不能被作偽，作偽時(shí)可檢測出來(lái)；

　　任何從節點(diǎn)能檢測出簽名是否有錯。

　　SM算法的有效性與此有關(guān)，通信時(shí)發(fā)生錯幀漏檢的情況相當于發(fā)生一次錯，要在容錯的次數設計上加以考慮。