摘 要：隨著電子商務網站等分布式應用的高速發(fā)展，系統(tǒng)的可用性已經受到了越來越多的重視。關鍵的服務不僅需要能夠容忍良性錯誤，還需要能夠容忍拜占庭錯誤。針對當前大部分的拜占庭容錯算法主要針對算法正常執(zhí)行的問題，提出了考慮出錯情況下的拜占庭容錯算法。該算法主要考慮實際過程中服務請求端和服務提供端的主復制品可能發(fā)生錯誤而沒有響應，或者因網絡擁塞而使響應沒有及時送達等網絡異常的情況。該算法解決了其他拜占庭容錯算法在網絡發(fā)生異常的情況下不能正常工作的問題，具有更強的適應性。

關鍵詞：復制品；網絡異常；拜占庭容錯算法

中圖分類號：TP393.08

容錯算法，一直是分布式應用程序框架的組成部分。在分布式系統(tǒng)中，研究者們對高可用系統(tǒng)的研究。一般集中在良性錯誤，如服務器宕機、拒絕服務攻擊、在網絡上竊聽消息或修改與破壞數據等，這些錯誤可能使服務器中斷，破壞數據的完整性和保密性。但缺乏對更為嚴重的惡意攻擊的研究，譬如軟件錯誤、錯誤操作、密鑰丟失、服務器被黑客控制等。這種由惡意攻擊引起的錯誤，被稱為拜占庭錯誤。如果任其發(fā)展，由于拜占庭故障造成的分布式應用偏離指定的行為，可能導致財產損失甚至人類生命喪失。

當前主流拜占庭容錯算法主要針對算法正常執(zhí)行的問題，提出了考慮出錯情況下的拜占庭容錯算法。該算法主要考慮實際過程中服務請求端和服務提供端的主復制品可能發(fā)生錯誤而沒有響應，或者因網絡擁塞而使響應沒有及時送達的情況。

1 算法描述

1.1 基本概念

拜占庭容錯中，為了容忍f個錯誤的復制品，復制品集合的大小 。一旦錯誤復制品的數量超過了錯誤容忍的門限值 ，該服務就不能再正常工作。一些符號說明如下：

Fc是服務請求端中發(fā)生拜占庭錯誤上限值；每個replica用ci表示，主副制品用cp表示；服務響應端T由tn=3ft+1個replicas組成，ft是服務響應端中發(fā)生拜占庭錯誤replicas個數的上限值，每個replica用ti表示，主副制品用tp表示。

1.2 出錯情況下的拜占庭容錯算法

當前主流的拜占庭容忍算法針對的是服務請求端和服務提供端的主復制品都未發(fā)生錯誤且網絡暢通的情況，這是一種理想狀況。在實際過程中服務請求端和服務提供端的主復制品可能發(fā)生錯誤而沒有響應，或者因網絡擁塞而使響應沒有及時送達。本節(jié)就服務請求端未能及時收到消息，引起計時器超，服務提供端發(fā)生錯誤的情形，對算法進行討論。

引起服務請求端的復制品計時器超時的原因可能有：（1）服務響應端的主復制品 發(fā)生錯誤，未能將服務請求端發(fā)生來的請求轉發(fā)給其他服務響應端的復制品。（2）服務響應端的主復制品 被黑客控制，故意不將服務響應端的復制品經過算法認可后的結果發(fā)送給服務請求端的復制品。（3）服務請求端的復制品計時器時間設置過短，不適用于當前的網絡狀況。

對于情況（3）應該使用使用神經網絡等建模工具對計時器的時間進行建模，對計時器的時間進行動態(tài)調整，這不在本文討論的范圍內，本文主要考慮情況（1）和情況（2）。解決這一問題的算法描述如下：

Step1：當服務請求端C需要調用外部服務響應端T服務時，C中的每一個復制品向T中的主服務復制品tp發(fā)送消息 。其中o是要ci請求的操作，x是該操作的序號， 是該請求o的時間戳。發(fā)送請求后，服務請求者ci啟動計時器，等待來自T的應答，如圖1所示。

Step2：C中的復制品ci發(fā)送請求后，等待應答的過程中，計時器超時，ci將請求 發(fā)送給T中的每一個復制品。

Step3：T中的復制品 收到 條匹配的DirectRequest消息后， 向T的主復制品 發(fā)送消息 ，并啟動計時器。

Step4： 向T的主復制品 發(fā)送消息 后，在計時器時間收到了 發(fā)送的消息，則說明 未發(fā)生錯誤，T的復制品開始PRE-PREPARE、PREPARE和COMMIT三個階段的通信過程；如果 在計時器時間內未收到 發(fā)送的消息， 開始懷疑 發(fā)生了錯誤，向其他復制品發(fā)送更改視圖的消息 。

Step5：T中的復制品經過View-change算法后，選舉了一個新的主復制品（如中的t2），開始拜占庭一致算法。

Step6： 收到其他復制品 發(fā)送的消息 ， 是當前T中復制品所在的視圖，r是執(zhí)行的結果，x是請求操作的序號。 比較這些結果，如果其中包含相同數量的 的消息數量>2ft+1，則接受此結果，并將結果 發(fā)送給服務請求端中的每一個復制品。

Step7：C中的復制品 收到 發(fā)送來的結果 后，對結果進行驗證，確定消息來自 后，發(fā)送應答消息 給服務請求端中的主復制品（簡稱 ），其中 是當前T中復制品所在的視圖。

Step8： 收到各 發(fā)送的應答消息 后，驗證 來自于 后查看其中是否有 個 具有相同 ，如果是，則 將接受該應答，并開始PRE-PREPARE、PREPARE和COMMIT三個階段的表決，一旦達成一致，就將結果放入接收隊列中，返回給上層應用程序，如圖1所示。

2 結束語

針對現有拜占庭容錯算法均假設算法可以順利執(zhí)行的問題，本文提出了一種出錯情況下的拜占庭容錯算法，適用于在實際過程中服務請求端和服務提供端的主復制品可能發(fā)生錯誤而沒有響應，或者因網絡擁塞而使響應沒有及時送達等情況。

參考文獻：

[1]CastroM，LiskovB.PracticalByzantinefaulttoleranceandproactiverecovery[J].ACMTransactionsonComputerSystems（TOCS），2002，20（4）：398-461.

[2]MalkhiD，ReiterM.Byzantinequorumsystems[J].DistributedComputing，1998，11（4）：203-213.

[3]孫周軍.基于拜占庭算法構建具有入侵容忍能力的Web服務研究[J].微電子學與計算機，2008，25（3）：35-37.

[4]王天鍔，張大方，楊金民.基于代理的Byzantine一致性算法的研究[J].計算機工程與科學，2005（4）：57-59.

[5]余發(fā)江，張煥國.可信安全計算平臺的一種實現[J].武漢大學學報（理學版），2004（1）：69-73.

[6]張煥國.可信計算研究進展[J].武漢大學學報（理學版），2006（5）：513-518.

[7]Merideth，M.G.，etal.Thema：Byzantine-fault-tolerantmiddlewareforweb-serviceapplications.in24thIEEESymposiumonReliableDistributedSystems.2005.Orlando，Florida.

作者單位：貴州師范學院數學與計算機科學學院，貴陽 550018