?

　　許多應用與人身安全或設備安全有密切聯系，隨著安全性要求的提高，希望設備或系統在其構成的部件與控制裝置發生故障時仍能保證安全，即故障-安全(failsafe)的特性。系統是由子系統組成的，子系統有故障時有控制地停止工作(failsilent，故障-靜默模式)，對系統而言仍是故障，因為它不再提供原定的服務了，這有可能引起全系統功能的失效。所以，安全是要從最高層的全局來分析的。

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

　　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)，也就是說已經經過本從節點轉發的內容不再轉發。

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