網(wǎng)絡(luò)異常情況下的拜占庭容錯(cuò)算法研究

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

關(guān)鍵詞：復(fù)制品；網(wǎng)絡(luò)異常；拜占庭容錯(cuò)算法

中圖分類號：TP393.08

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

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

1 算法描述

1.1 基本概念

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

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

1.2 出錯(cuò)情況下的拜占庭容錯(cuò)算法

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

引起服務(wù)請求端的復(fù)制品計(jì)時(shí)器超時(shí)的原因可能有：（1）服務(wù)響應(yīng)端的主復(fù)制品 發(fā)生錯(cuò)誤，未能將服務(wù)請求端發(fā)生來的請求轉(zhuǎn)發(fā)給其他服務(wù)響應(yīng)端的復(fù)制品。（2）服務(wù)響應(yīng)端的主復(fù)制品 被黑客控制，故意不將服務(wù)響應(yīng)端的復(fù)制品經(jīng)過算法認(rèn)可后的結(jié)果發(fā)送給服務(wù)請求端的復(fù)制品。（3）服務(wù)請求端的復(fù)制品計(jì)時(shí)器時(shí)間設(shè)置過短，不適用于當(dāng)前的網(wǎng)絡(luò)狀況。

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

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

Step2：C中的復(fù)制品ci發(fā)送請求后，等待應(yīng)答的過程中，計(jì)時(shí)器超時(shí)，ci將請求 發(fā)送給T中的每一個(gè)復(fù)制品。

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

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

Step5：T中的復(fù)制品經(jīng)過View-change算法后，選舉了一個(gè)新的主復(fù)制品（如中的t2），開始拜占庭一致算法。

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

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

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

2 結(jié)束語

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

參考文獻(xiàn)：

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

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

[3]孫周軍.基于拜占庭算法構(gòu)建具有入侵容忍能力的Web服務(wù)研究[J].微電子學(xué)與計(jì)算機(jī)，2008，25（3）：35-37.

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

[5]余發(fā)江，張煥國.可信安全計(jì)算平臺(tái)的一種實(shí)現(xiàn)[J].武漢大學(xué)學(xué)報(bào)（理學(xué)版），2004（1）：69-73.

[6]張煥國.可信計(jì)算研究進(jìn)展[J].武漢大學(xué)學(xué)報(bào)（理學(xué)版），2006（5）：513-518.

[7]Merideth，M.G.，etal.Thema：Byzantine-fault-tolerantmiddlewareforweb-serviceapplications.in24thIEEESymposiumonReliableDistributedSystems.2005.Orlando，F(xiàn)lorida.

作者單位：貴州師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，貴陽 550018