?

　　許多應(yīng)用與人身安全或設(shè)備安全有密切聯(lián)系，隨著安全性要求的提高，希望設(shè)備或系統(tǒng)在其構(gòu)成的部件與控制裝置發(fā)生故障時(shí)仍能保證安全，即故障-安全(failsafe)的特性。系統(tǒng)是由子系統(tǒng)組成的，子系統(tǒng)有故障時(shí)有控制地停止工作(failsilent，故障-靜默模式)，對(duì)系統(tǒng)而言仍是故障，因?yàn)樗辉偬峁┰ǖ姆?wù)了，這有可能引起全系統(tǒng)功能的失效。所以，安全是要從最高層的全局來分析的。

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

　　1 SM算法

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

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

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

　　③ 通信各輪的幀內(nèi)容如下：

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

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

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

　　由于是通過總線廣播而不是點(diǎn)到點(diǎn)通信，通信量只要計(jì)算不同的幀的個(gè)數(shù)就可以:N=1+(n-1)+(n-1)2+…。總的通信輪數(shù)為m+1。