第7章分布式系統(tǒng)中容錯技術(shù)1一臺計(jì)算機(jī)由各種各樣的硬件和軟件組成，這些部件時不時地會出現(xiàn)故障或錯誤，導(dǎo)致死機(jī)或運(yùn)行失敗。

這些故障或錯誤往往是隨機(jī)出現(xiàn)的，計(jì)算機(jī)用戶無法預(yù)料這些情況的出現(xiàn)，有時甚至察覺不到錯誤的出現(xiàn)。如果一個計(jì)算機(jī)系統(tǒng)能夠?qū)Ψ穷A(yù)期的軟件/硬件故障有適當(dāng)?shù)膶Σ吆蛻?yīng)變措施，則我們說這個系統(tǒng)具備一定的容錯(Faulttolerance)

能力。分布式系統(tǒng)的特殊之處在于故障的局部化，即系統(tǒng)的某個(些)

局部成份出現(xiàn)故障，這種故障可能會影響到系統(tǒng)的局部功能，而對系統(tǒng)的其它部分毫無影響。本章討論內(nèi)容包括容錯處理的基本概念、要求和模型，如何實(shí)現(xiàn)可靠的通信，以及當(dāng)發(fā)現(xiàn)故障時如何排除并恢復(fù)運(yùn)行。27.1分布式系統(tǒng)中的故障模型

7.1.1基本概念

屬性：

可用性

可靠性

安全性可維護(hù)性

保密性完整性

后果：

失效

錯誤

故障策略：

防止故障

故障容錯

故障恢復(fù)

故障預(yù)報(bào)什么是“可信賴的系統(tǒng)”？如何區(qū)分各種故障？如何處理故障？3可用性：可用性反映的是系統(tǒng)隨時可被用戶使用的特性?？煽啃裕阂粋€系統(tǒng)可以無故障持續(xù)運(yùn)行的程度。與可用性相反，可靠性以時間周期為基準(zhǔn)，而不是以某個時刻為基準(zhǔn)。也就是說，一個高度可靠的系統(tǒng)在相當(dāng)長的時間周期里可以無間斷地為用戶提供服務(wù)安全性：安全性指的是在系統(tǒng)出現(xiàn)暫時錯誤的情況下，不出現(xiàn)災(zāi)難性后果的能力?？删S護(hù)性：可維護(hù)性指的是系統(tǒng)一旦出現(xiàn)故障，系統(tǒng)易于修復(fù)的能力。保密性：保密性要求系統(tǒng)資源不被非法用戶訪問?？尚刨囅到y(tǒng)的性質(zhì)4當(dāng)系統(tǒng)不能提供所承諾的服務(wù)時就認(rèn)為系統(tǒng)失效一個系統(tǒng)在正常工作時會在若干種運(yùn)行狀態(tài)之間變遷，一旦出現(xiàn)異常，則該系統(tǒng)進(jìn)入錯誤(Error)

狀態(tài)。一個系統(tǒng)的錯誤狀態(tài)可能是導(dǎo)致系統(tǒng)失效的原因造成錯誤的原因稱為故障。歸于導(dǎo)致故障錯誤失效故障的種類繁多，軟件和硬件都有可能產(chǎn)生故障，而且在某些場合下，與系統(tǒng)無關(guān)的外部環(huán)境也可能引發(fā)故障。通常分為：暫時性的(transient)、間歇性的(intermittent)和永久性的(permanent)57.1.2基本的故障模型

拜占庭故障故障類故障子類故障語義崩潰故障

服務(wù)器崩潰(停機(jī))

，但停機(jī)前工作正常失憶型崩潰服務(wù)器只能從初始狀態(tài)啟動，遺忘了崩潰前的狀態(tài)中頓型崩潰服務(wù)器可以從崩潰前的狀態(tài)啟動停機(jī)型崩潰服務(wù)器完全停機(jī)失職故障（遺漏故障）

服務(wù)器對輸入的請求沒有響應(yīng)接收型失職服務(wù)器無法接收信件發(fā)送型失職服務(wù)器無法發(fā)送信件應(yīng)答故障

服務(wù)器對服務(wù)請求做出錯誤反應(yīng)返回值故障返回值出現(xiàn)錯誤狀態(tài)變遷故障服務(wù)器偏離正確的運(yùn)行軌跡時序故障

服務(wù)器反應(yīng)遲緩，超出規(guī)定的時間間隔隨意故障

服務(wù)器在任意時間產(chǎn)生的隨意錯誤故障分類

(與語義有關(guān))6要建立可靠系統(tǒng)就必須控制故障。對用戶來講最重要的是容錯，即系統(tǒng)發(fā)生故障時也能提供服務(wù)（對其他進(jìn)程隱藏故障的發(fā)生）。容錯是建立在冗余的基礎(chǔ)上的,冗余類型有四種：哺乳動物的兩只眼睛、兩個耳朵、兩個腎，747飛機(jī)的四個引擎只用了三個，多個體育裁判硬件冗余使用多個硬件軟件冗余使用多個軟件信息冗余

海明(Hamming)

校驗(yàn)檢查和奇偶位時間冗余

超時重發(fā)技術(shù)：如原子操作和原子事務(wù)處理重復(fù)計(jì)算物理冗余77.1.3故障的基本處理方法(進(jìn)程容錯機(jī)制)：(1)主動復(fù)制。所有的復(fù)制模塊協(xié)同進(jìn)行，并且它們的狀態(tài)緊密同步。用到了錯誤屏蔽的概念——隱藏出現(xiàn)的故障或防止故障造成錯誤。把相同進(jìn)程的集合組織到一個平等組中。在分布式系統(tǒng)中使用主動復(fù)制相對比較昂貴。編組故障屏蔽(2)被動復(fù)制。以等級方式組織進(jìn)程組，其中只有一個模塊（主進(jìn)程）處于動態(tài)，其他模塊的交互狀態(tài)由這一模塊的檢查點(diǎn)定期更新。如果主進(jìn)程崩潰，后備進(jìn)程執(zhí)行選舉算法選擇一個新的主進(jìn)程。動態(tài)方法層次故障屏蔽(3)半主動復(fù)制。是主動復(fù)制和被動復(fù)制的混合方法。此種方法所需的恢復(fù)開銷相對較低。失效的檢測可分為外部檢測和內(nèi)部檢測兩類：外部檢測是指將檢測節(jié)點(diǎn)失效的職責(zé)賦予被檢測節(jié)點(diǎn)的外部附件。內(nèi)部檢測將節(jié)點(diǎn)的失效檢測機(jī)制置于該節(jié)點(diǎn)內(nèi)部，通常檢測部件被假定為一個可以完全信賴的“硬核”。

8Passive(Primary-Backup)Replication

RequestCommunication:

therequestisissuedtotheprimaryRMandcarriesauniquerequestid.Coordination:

Primarytakesrequestsatomically,inorder,checksid(resendsresponseifnotnewid.)Execution:

Primaryexecutes&storestheresponseAgreement:Ifupdate,primarysendsupdatedstate/result,req-idandresponsetoallbackupRMs.Response:

primarysendstothefrontendClientFrontEndRMRMRMClientFrontEndRMprimaryBackupBackupBackup….9FaultToleranceinPassiveReplicationThesystemimplementslinearizability,sincetheprimarysequencesoperationsinorder.Iftheprimaryfails,abackupbecomesprimarybyleaderelection,andthereplicamanagersthatsurviveagreeonwhichoperationshadbeenperformedatthepointwhenthenewprimarytakesover.Theaboverequirementismetifthereplicamanagers(primaryandbackups)areorganizedasagroupandiftheprimaryusesview-synchronousgroupcommunicationtosendupdatestobackups.Thesystemremainslinearizableaftertheprimarycrashes10ActiveReplication

RequestCommunication:

Therequestcontainsauniqueidentifierandismulticasttoallbyareliabletotallyorderedmulticast.Coordination:

Groupcomm.ensuresthatrequestsaredeliveredtoeachRMinthesameorder(butmaybeatdifferenttimes!).Execution:

Eachreplicaexecutestherequest.(Correctreplicasreturnsameresultsincetheyarerunningthesameprogram,i.e.,theyarereplicatedprotocolsorreplicatedstatemachines)Agreement:Noagreementphaseisneeded,becauseofmulticastdeliverysemanticsofrequestsResponse:

EachreplicasendsresponsedirectlytoFE,FEusestheseasbeforeClientFrontEndRMRMClientFrontEndRM….11FaultToleranceinActiveReplicationRMsworkasreplicatedstatemachines,playingequivalentroles.Thatis,eachrespondstoagivenseriesofrequestsinthesameway.ThisisachievedbyrunningthesameprogramcodeatallRMs.IfanyRMcrashes,stateismaintainedbyothercorrectRMs.ThissystemimplementssequentialconsistencyThetotalorderensuresthatallcorrectreplicamanagersprocessthesamesetofrequestsinthesameorder.Eachfrontend’srequestsareservedinFIFOorder(becausethefrontendawaitsaresponsebeforemakingthenextrequest).So,requestsareFIFO-totalordered.Butifclientsaremulti-threadedandcommunicatewithoneanotherwhilewaitingforresponsesfromtheservice,wemayneedtoincorporatecausal-totalordering127.2容錯系統(tǒng)的基本構(gòu)件7.2.1堅(jiān)固存儲器（穩(wěn)定存儲器，Lampson提出）

堅(jiān)固存儲器是對一個可以經(jīng)受系統(tǒng)失效的特定存儲器的邏輯抽象，也就是說，堅(jiān)固存儲器里的內(nèi)容不會被一個失效所毀壞。堅(jiān)固存儲器的實(shí)現(xiàn)技術(shù)：磁盤鏡像：堅(jiān)固存儲器可以用一對普通磁盤來實(shí)現(xiàn)。堅(jiān)固存儲器中的每一個塊由兩個獨(dú)立的磁盤塊組成，分別位于不同的驅(qū)動器上，使得它們同時由于硬件故障受到損壞的機(jī)會最小。RAID：另一種實(shí)現(xiàn)堅(jiān)固存儲器的方法是使用廉價磁盤冗余陣列(RAID)。RAID是通過運(yùn)用位交錯技術(shù)將數(shù)據(jù)分布到多個磁盤中，從而提供高I/O性能?？梢杂靡粋€或幾個磁盤來檢測或屏蔽錯誤，RAID與傳統(tǒng)磁盤相比有顯著的優(yōu)點(diǎn)，并可承受多個失效。13RecoveryStableStorageStableStorageCrashafterdrive1isupdatedBadspot147.2.2故障—停止處理器當(dāng)一個處理器失效，最可能的是它不進(jìn)行任何不正確的操作，并且簡單地停止運(yùn)行，這樣的處理器被稱為故障—停止處理器，一個故障—停止處理器由多個處理器組成。失效的效果：當(dāng)出現(xiàn)一個故障時，故障—停止處理器會有以下效果：(a)處理器停止運(yùn)行；(b)易失性存儲器的內(nèi)容丟失，而堅(jiān)固存儲器不受影響；(c)任何其他處理器均可以檢測到故障—停止處理器的失效狀態(tài)。故障—停止處理器的實(shí)現(xiàn)：現(xiàn)有一個可靠的堅(jiān)固存儲器、一個可靠的存儲處理器(控制存儲媒介的處理器)以及k+1個處理器，將它們轉(zhuǎn)變成故障—停止處理器的方法如下：k+1個處理器中的每一個都運(yùn)行同樣的程序并通過存儲處理器訪問同一個堅(jiān)固存儲器。如果任何一個請求是不同的，或者任何一個請求沒有在指定的期間到達(dá)，則意味著檢測到一個失效事件，因而應(yīng)該丟棄所有請求。因?yàn)橄到y(tǒng)表現(xiàn)為一個故障—停止處理器，這一方法產(chǎn)生一個k—故障—停止處理器，除非系統(tǒng)中k+1個或更多的部件失效。157.2.3原子操作一個原子操作就是由硬件獨(dú)立執(zhí)行的一系列動作。也就是說，每一個動作或者被完全徹底地執(zhí)行，或者所有的動作根本沒有執(zhí)行，系統(tǒng)的狀態(tài)保持不變。原子操作中的每一個動作都是孤立的，當(dāng)執(zhí)行這一動作時，在進(jìn)程中感覺不到外界活動的存在，也意識不到外界狀態(tài)的變化。與此相似，任何外界的進(jìn)程均感覺不到一個孤立的原子操作的內(nèi)在狀態(tài)的變化。這就是所謂的原子操作的“全有或全無”的性質(zhì)，即一個原子操作要么全部完成，要么在執(zhí)行過程中出現(xiàn)錯誤的時候相當(dāng)于根本沒有執(zhí)行。原子操作失效時，可以通過簡單地重做來恢復(fù)。16如果由于某個故障，系統(tǒng)進(jìn)入錯誤狀態(tài)，容錯處理的目的是采取適當(dāng)?shù)氖侄?，把系統(tǒng)恢復(fù)(Recovery)到無錯誤狀態(tài)。大致上我們可以把系統(tǒng)恢復(fù)技術(shù)歸納為兩類：前向恢復(fù)(ForwardRecovery)和逆向恢復(fù)(BackwardRecovery)。前向恢復(fù)技術(shù)，采用一種樂觀的態(tài)度，當(dāng)系統(tǒng)發(fā)現(xiàn)錯誤后，我們試圖把系統(tǒng)帶入一個新狀態(tài)，從新狀態(tài)開始繼續(xù)運(yùn)行。關(guān)鍵在于必須預(yù)先知道會發(fā)生什么錯誤。逆向恢復(fù)技術(shù)，向后式恢復(fù)（回退恢復(fù)），采用保守的態(tài)度，事先不知道會發(fā)生什么故障，在系統(tǒng)正常運(yùn)行時記錄一些狀態(tài)歷史。一旦當(dāng)失效導(dǎo)致系統(tǒng)處于不一致的狀態(tài)時，可恢復(fù)到從前沒有發(fā)生故障的狀態(tài)，重新執(zhí)行。是一種通用方法。開銷較大。不能提供完全的故障透明性。需要設(shè)置檢查點(diǎn)?；謴?fù)技術(shù)

7.3節(jié)點(diǎn)故障的處理177.3.1向前式恢復(fù)：例外處理技術(shù)過程：一個進(jìn)程或任務(wù)的初始拷貝由不同的處理器來運(yùn)行。這些版本的結(jié)果在檢查點(diǎn)進(jìn)行表決或比較，如果表決結(jié)果是成功的，則可以獲得一個儲存在堅(jiān)固存儲器中的正確結(jié)果。在此結(jié)果的基礎(chǔ)上，再執(zhí)行下一項(xiàng)任務(wù)的拷貝。如果表決結(jié)果是失敗的，對以前的任務(wù)進(jìn)行一次回退執(zhí)行。也就是說，在后備處理器上再運(yùn)行以前的任務(wù)，目的是獲得正確的結(jié)果。盡管在所有版本都失效(所有結(jié)果都不正確)或者表決也不能獲得正確結(jié)果的情況下，回退運(yùn)行是不可避免的，但由于利用了現(xiàn)存的正確結(jié)果而不必從頭重新開始，還是節(jié)省了回退時間。前向恢復(fù)技術(shù)的關(guān)鍵是要事先掌握可能出現(xiàn)的故障，并且為每一種故障定義了相應(yīng)的恢復(fù)操作，于是才能在故障出現(xiàn)時把系統(tǒng)切換到一個新的狀態(tài)。前向恢復(fù)技術(shù)的要求過于苛刻，我們無法預(yù)先估計(jì)到所有可能發(fā)生的故障。18向前式恢復(fù)方案的實(shí)例：其中Ii，Ii+1和Ii+2是檢查點(diǎn)間隔。兩個進(jìn)程X和Y均運(yùn)行一個進(jìn)程的同一個版本。在每一個檢查點(diǎn)之前，需要對它們的結(jié)果進(jìn)行比較并確認(rèn)是否正確。S是一個后備處理器，對兩個間隔Ii和Ii+1進(jìn)行驗(yàn)證。有以下四種可能的情況：(1)沒有并發(fā)重試。如果X和Y都在間隔Ii正確運(yùn)行，那么X和Y在間隔Ii所得的結(jié)果是相同的，S不進(jìn)行并發(fā)重試。Pradhan、Vaidya提出19(2)有非回退的并發(fā)重試。在Ii中出現(xiàn)了錯誤，但在兩個合法的檢查點(diǎn)間隔Ii+1和Ii+2中間沒有錯誤。如果我們用(Xi,Yi,Si)代表在間隔Ii之中X、Y和S的狀態(tài)，并且用0代表錯誤，1代表正確，d代表沒有關(guān)系(或者錯誤或者正常)。(Xi,Yi,Si)就有兩種情況：(1,0,1)和(0,1,1)，無論哪種情況，系統(tǒng)都可以判斷哪個進(jìn)程是正確的，所以不用回退。(3)在一次并發(fā)重試的間隔后進(jìn)行回退。對應(yīng)于在Ii中有兩個進(jìn)程(X、Y和S中的兩個)有錯誤的情況。若用(Xi,Yi,Si)代表在間隔Ii之中X、Y和S的狀態(tài)，可得到三種情況：(1,0,0)，(0,1,0)，(0,0,d)。這三種情況是在一次并發(fā)重試的間隔后進(jìn)行回退。系統(tǒng)回退到Ii的開始處。20(4)在并發(fā)重試的兩次間隔之后回退。該情況下在檢查點(diǎn)間隔Ii+1處出現(xiàn)了一個額外的錯誤，如果我們用(Xi,Yi,Si,Xi+1,Yi+1,Si+1)代表在間隔Ii和Ii+1中X、Y和S的狀態(tài)，這種情況對應(yīng)于以下描述的四種情形：(1,0,1,d,d,0)，(1,0,1,0,d,d)，(0,1,1,d,d,0)，(0,1,1,d,0,d)?？梢源_定間隔Ii中哪個進(jìn)程是正確的，但是不能確定間隔Ii+1中哪個進(jìn)程是正確的。系統(tǒng)回退到間隔Ii+1的起始處。217.3.2向后式恢復(fù)：檢查點(diǎn)技術(shù)檢查點(diǎn)：在向后式恢復(fù)中進(jìn)程被恢復(fù)到一個先前的正確的狀態(tài)。進(jìn)程執(zhí)行中的一些點(diǎn)被稱為“檢查點(diǎn)”(checkpoint)，在以后發(fā)生錯誤的情況下，進(jìn)程可以被恢復(fù)到這些點(diǎn)。在檢查點(diǎn)的實(shí)現(xiàn)過程中，需要考慮兩個主要問題：檢查點(diǎn)的存儲和檢查點(diǎn)的更新。局部快照合法恢復(fù)線非法恢復(fù)線22有兩種方法來保存檢查點(diǎn)：(1)每個檢查點(diǎn)被組播到每一個備份模塊；(2)每個檢查點(diǎn)被存儲在其本地堅(jiān)固存儲器中。當(dāng)進(jìn)程正確地從一個舊的檢查點(diǎn)運(yùn)行到一個新的檢查點(diǎn)時，舊的檢查點(diǎn)就要被新的檢查點(diǎn)替換。當(dāng)進(jìn)程執(zhí)行到兩個檢查點(diǎn)之間時發(fā)生錯誤，那么進(jìn)程應(yīng)該卷回到舊的檢查點(diǎn)處重新執(zhí)行。檢查點(diǎn)的原子更新：當(dāng)使用新的檢查點(diǎn)替換舊的檢查點(diǎn)的過程中，系統(tǒng)也會發(fā)生失效。這可以通過檢查點(diǎn)的原子更新過程來解決，也就是說，在檢查點(diǎn)的更新中，要么舊的檢查點(diǎn)被新的檢查點(diǎn)替換，要么舊的檢查點(diǎn)被完整地保留。檢查點(diǎn)原子更新的實(shí)現(xiàn)：假設(shè)庫A和庫B現(xiàn)在保存的檢查點(diǎn)是C1，現(xiàn)在要用檢查點(diǎn)C2取代庫A和庫B的內(nèi)容。在取代前，假設(shè)Ta1=Ta2=Tb1=Tb2=1，檢查點(diǎn)的更新過程如下：(1)為了更新庫A，先置Ta1=2；(2)將庫A的內(nèi)容用檢查點(diǎn)C2取代；(3)庫A更新完畢，置Ta2=2；(4)為了更新庫B，先置Tb1=2；(5)將庫B的內(nèi)容用檢查點(diǎn)C2取代；(6)庫B更新完畢，置Tb2=2；23識別在檢查點(diǎn)更新過程中發(fā)生的失效：基于影像頁面技術(shù)的恢復(fù)方案：在基于影像頁面技術(shù)的方案中，當(dāng)進(jìn)程需要修改一個頁面時，系統(tǒng)復(fù)制該頁并保留在堅(jiān)固存儲器中。系統(tǒng)中每個頁面都有兩個拷貝，當(dāng)進(jìn)程在執(zhí)行的過程中，只有其中的一個拷貝被進(jìn)程修改，另一個拷貝就作為影像頁面。如果進(jìn)程失效，則丟棄被修改的拷貝，系統(tǒng)根據(jù)影像頁面進(jìn)行恢復(fù)。如果進(jìn)程成功運(yùn)行，則每一份影像頁面被相應(yīng)的修改后的頁面替換。247.4分布式檢查點(diǎn)算法7.4.1一致性檢查點(diǎn)全局狀態(tài)：一種全局狀態(tài)的定義是一系列局部狀態(tài)的集合，代表系統(tǒng)曾經(jīng)歷過的某個狀態(tài)。這里的局部狀態(tài)就是一個進(jìn)程的檢查點(diǎn)，每個局部進(jìn)程有一個局部狀態(tài)。可利用分布式快照算法保證系統(tǒng)的全局一致性。即系統(tǒng)中每一個進(jìn)程周期地“快照”自身的狀態(tài)，并把狀態(tài)數(shù)據(jù)存放在局部堅(jiān)固存儲器中。當(dāng)某個進(jìn)程或系統(tǒng)發(fā)生故障需要恢復(fù)以前的狀態(tài)時，就利用這些局部快照構(gòu)造出一個全局一致的狀態(tài)，令整個系統(tǒng)根據(jù)這個全局狀態(tài)恢復(fù)運(yùn)行。25恢復(fù)線和切割線：一個分布式快照對應(yīng)一個全局一致的狀態(tài)，該全局狀態(tài)是離故障點(diǎn)最近的系統(tǒng)快照。這個分布式快照可以作為一個恢復(fù)線(recoveryline)用于恢復(fù)?；謴?fù)線在每一進(jìn)程的快照上必須選擇一致的切入點(diǎn)。即，一個恢復(fù)線對應(yīng)于最近的一個一致性切割線262）局部檢查點(diǎn)可能組成如下兩種不一致的全局狀態(tài)：丟失報(bào)文。進(jìn)程Pi的檢查點(diǎn)狀態(tài)顯示它給進(jìn)程Pj發(fā)送了報(bào)文m，但是進(jìn)程Pj并沒有關(guān)于該報(bào)文的紀(jì)錄。孤兒報(bào)文。進(jìn)程Pj的檢查點(diǎn)狀態(tài)顯示它收到了一個來自進(jìn)程Pi的報(bào)文m，但是進(jìn)程Pi的狀態(tài)顯示它沒有向進(jìn)程Pj發(fā)送過報(bào)文m。不一致全局狀態(tài)實(shí)例：27一個強(qiáng)一致(stronglyconsistent)的檢查點(diǎn)集合是由一系列的沒有孤兒報(bào)文和沒有丟失報(bào)文局部檢查點(diǎn)組成。一個一致的檢查點(diǎn)集合是由一系列沒有孤兒報(bào)文的局部檢查點(diǎn)組成。顯然一個強(qiáng)一致的檢查點(diǎn)集合包括一系列局部檢查點(diǎn)，在這些檢查點(diǎn)之間，進(jìn)程之間沒有報(bào)文傳送。如果每個進(jìn)程都在發(fā)送一個報(bào)文之后生成一個檢查點(diǎn)，那么最近的檢查點(diǎn)集合將永遠(yuǎn)是一致的。3）檢查點(diǎn)的設(shè)置可以是同步的，或異步的，也可以是兩者的混合。287.4.2異步檢查點(diǎn)異步檢查點(diǎn)算法中，程序中各進(jìn)程周期性地相互獨(dú)立地保存自己的運(yùn)行狀態(tài)，程序各進(jìn)程之間不需要相互協(xié)商。在恢復(fù)過程中，各進(jìn)程之間則需要相互協(xié)商通過復(fù)雜的回退算法各自回退到合適的檢查點(diǎn)時刻以使整個程序的各個進(jìn)程恢復(fù)到最近的一個一致的全局狀態(tài)。一致檢查點(diǎn)的檢測方法：比較發(fā)送的和接收的報(bào)文數(shù)量來檢測孤兒報(bào)文的存在。如果接收到的報(bào)文數(shù)目和任何發(fā)送報(bào)文的進(jìn)程發(fā)送的報(bào)文的數(shù)目是一致的，那么就可以認(rèn)為找到了一個局部檢查點(diǎn)的一致集合。使用間隔依賴圖來進(jìn)行檢測。如果每個進(jìn)程i的向量時鐘是LCi，一個檢查點(diǎn)集合是一致的，當(dāng)且僅當(dāng)不存在i和j滿足LCi＜LCj，即不存在孤兒報(bào)文。

4）算法的優(yōu)缺點(diǎn)：允許分布式程序的各個進(jìn)程擁有最大程度的自治性，算法的延遲較小。但由于每個進(jìn)程需要保存若干時刻的檢查點(diǎn)信息，空間開銷較大；其次，在恢復(fù)過程中可能會重復(fù)回退，甚至出現(xiàn)多米諾效應(yīng)，使程序一直回退到初始狀態(tài)。29多米諾效應(yīng)(dominoeffect)由于進(jìn)程的分布式特性，要找到一個恢復(fù)線較困難。需要每個進(jìn)程都回退到它最近保存的狀態(tài)。每個進(jìn)程都定期地對狀態(tài)設(shè)置檢查點(diǎn)，各進(jìn)程之間設(shè)置檢查點(diǎn)的過程是獨(dú)立的，與系統(tǒng)中其他進(jìn)程毫無協(xié)調(diào)。一旦需要形成一條恢復(fù)線，每個進(jìn)程只能回溯到它最近保存的那個局部快照，然后通過一個檢驗(yàn)算法來核對一致性。如果檢驗(yàn)成功，則皆大歡喜；反之，就必須令所有進(jìn)程進(jìn)一步回退，一直到形成一條合法恢復(fù)線為止。這種折疊回退的過程可能會導(dǎo)致多米諾效應(yīng)。例如，為解決孤兒報(bào)文的問題，由于一個進(jìn)程的回退導(dǎo)致另外一個或多個進(jìn)程的回退的效應(yīng)，即多米諾效應(yīng)。

Thedominoeffect307.4.3同步檢查點(diǎn)（協(xié)調(diào)檢查點(diǎn)）在同步檢查點(diǎn)算法中，各相關(guān)進(jìn)程協(xié)調(diào)它們的局部檢查點(diǎn)的建立行為，以保證所有的最近的檢查點(diǎn)都是一致的。在同步檢查點(diǎn)中，只有最近的一致的檢查點(diǎn)集合才需要被維護(hù)和保存。即所有進(jìn)程都同步地把它們的狀態(tài)寫到本地穩(wěn)定存儲器中。算法的優(yōu)缺點(diǎn)：由于使用同步檢查點(diǎn)算法，各進(jìn)程的局部檢查點(diǎn)組成的集合是一個全局一致的狀態(tài)，所以在恢復(fù)時各個進(jìn)程只需要簡單地從檢查點(diǎn)處重新開始執(zhí)行。優(yōu)點(diǎn)是每個進(jìn)程只需保存最近時刻的檢查點(diǎn)信息，空間開銷較小，且在恢復(fù)的時候沒有多米諾效應(yīng)。其缺點(diǎn)是，在建立檢查點(diǎn)時，各進(jìn)程間的同步使程序運(yùn)行中止時間較長，且中央?yún)f(xié)調(diào)者是系統(tǒng)瓶頸。Sync-and-Stop(SNS)算法中有一個進(jìn)程pc負(fù)責(zé)管理全局檢查點(diǎn)建立過程。各進(jìn)程的檢查點(diǎn)建立過程如下：pc向所有進(jìn)程廣播檢查點(diǎn)開始報(bào)文Mb(第一次同步開始)；任一個進(jìn)程接收到報(bào)文Mb后停止運(yùn)行，并在自己所發(fā)送的報(bào)文全部到達(dá)接收者后向pc進(jìn)程發(fā)送報(bào)文Ms1；31pc接收到所有進(jìn)程發(fā)送的報(bào)文Ms2后，意味著第二次同步結(jié)束。pc向所有進(jìn)程廣播報(bào)文Me；各進(jìn)程接收到報(bào)文Me后，刪除舊的檢查點(diǎn)，僅保留新的檢查點(diǎn)，然后繼續(xù)執(zhí)行。SNS算法的恢復(fù)過程十分簡單，只需回退到檢查點(diǎn)處繼續(xù)執(zhí)行。

經(jīng)過第一次同步之后，任何進(jìn)程所發(fā)送的報(bào)文都已經(jīng)被對應(yīng)的接收進(jìn)程接收到，任何進(jìn)程之間不會存在孤兒報(bào)文，滿足一致性的要求。pc接收到所有進(jìn)程發(fā)送的報(bào)文Ms1后，即意味著第一次同步結(jié)束。pc向各進(jìn)程廣播報(bào)文Mchk，第二次同步開始；任一個進(jìn)程接收到報(bào)文Mchk后，立即作局部檢查點(diǎn)，檢查點(diǎn)建立完成之后向pc發(fā)送報(bào)文Ms2；32Chandy-Lamport(CL)算法：機(jī)器mc與m1之間有通道直接相連，可直接相互發(fā)送報(bào)文，機(jī)器mc與m1稱為直接相連；機(jī)器mc與m2之間沒有直接通道相連，它們間相互發(fā)送的報(bào)文要通過m1轉(zhuǎn)發(fā)，機(jī)器mc與m2稱為間接相連。建立檢查點(diǎn)的過程可由任一個進(jìn)程pc發(fā)起，pc進(jìn)程停止運(yùn)行，并向與其所在機(jī)器直接相連的機(jī)器上的進(jìn)程廣播報(bào)文Mb，然后進(jìn)程pc建立局部檢查點(diǎn)；進(jìn)程p接收到報(bào)文Mb后，若進(jìn)程p還未開始建立檢查點(diǎn)，則進(jìn)程p停止運(yùn)行并立即向與其所在機(jī)器直接相連的機(jī)器上的進(jìn)程廣播報(bào)文Mb，然后進(jìn)程p建立局部檢查點(diǎn)；進(jìn)程p開始建立檢查點(diǎn)后，若接收到其他進(jìn)程發(fā)送的非檢查點(diǎn)控制報(bào)文m，則保存報(bào)文m；33當(dāng)進(jìn)程p完成局部檢查點(diǎn)的建立，并且接收到與其所在機(jī)器直接相連的機(jī)器上的所有進(jìn)程發(fā)送的報(bào)文Mb后，進(jìn)程p向pc進(jìn)程發(fā)送報(bào)文Ms；當(dāng)進(jìn)程pc接收到所有進(jìn)程發(fā)送的報(bào)文Ms后，pc進(jìn)程向所有進(jìn)程發(fā)送報(bào)文Me，并刪除本進(jìn)程舊的檢查點(diǎn)，進(jìn)程pc繼續(xù)執(zhí)行；其他進(jìn)程p接收到報(bào)文Me后，刪除本進(jìn)程舊的檢查點(diǎn)，繼續(xù)執(zhí)行。在恢復(fù)過程中，CL算法在回退到當(dāng)前檢查點(diǎn)重新執(zhí)行的同時還必須重發(fā)過程(c)中保存的報(bào)文m。與SNS算法相比，CL算法減少了兩次全局同步的開銷。CL算法的缺點(diǎn)是其控制報(bào)文的數(shù)目與機(jī)器間的拓?fù)浣Y(jié)構(gòu)有關(guān)。347.4.4混合檢查點(diǎn)其基本思想是在一個較長的時間段中使用同步檢查點(diǎn)，而在較短的時間段內(nèi)使用異步檢查點(diǎn)。也就是說，在一個同步時間段里，會有若干個異步時間段。因此，我們可以有一個可以控制的回退，從而保證不會在建立檢查點(diǎn)的過程中引入過多的開銷。

例如：準(zhǔn)同步檢查點(diǎn)。這個方法允許每個進(jìn)程異步地設(shè)置檢查點(diǎn)，從而保證了進(jìn)程的獨(dú)立性。同時，對恢復(fù)線的擴(kuò)展采用發(fā)起通信的檢查點(diǎn)協(xié)調(diào)方法，從而可以限制恢復(fù)過程中回退的傳播。7.4.5報(bào)文日志：日志技術(shù)日志技術(shù)不僅用于故障恢復(fù)，也常常用于故障收集、故障報(bào)告、以及故障診斷等方面。與保存系統(tǒng)狀態(tài)相比，記錄日志不但節(jié)省時間，也節(jié)省存儲空間，因?yàn)楸４嫦到y(tǒng)快照要求面面俱到，而保存日志只需要少許的關(guān)鍵信息。不同層次、不同應(yīng)用領(lǐng)域中的故障恢復(fù)系統(tǒng)對日志的觀點(diǎn)亦不相同。例如，在分布式數(shù)據(jù)庫系統(tǒng)中，日志記錄以事務(wù)為單位，記載各事務(wù)對數(shù)據(jù)的更新操作和狀態(tài)。其典型格式為〈事務(wù)標(biāo)識，數(shù)據(jù)項(xiàng)，老值，新值〉，以及執(zhí)行2PC的有關(guān)信息。35報(bào)文日志：為了減少回退時撤銷的計(jì)算工作量，所有接收的和發(fā)送的報(bào)文都可以記錄下來。前者叫做接收者日志，后者叫做發(fā)送者日志。它使用一個檢查點(diǎn)狀態(tài)作為開始點(diǎn)，然后簡單地把從該點(diǎn)以后發(fā)送的所有消息都重發(fā)并進(jìn)行處理。當(dāng)Pj的檢查點(diǎn)被恢復(fù)到一個沒有孤兒報(bào)文，而且所有要發(fā)送的報(bào)文都已經(jīng)發(fā)送的一致狀態(tài)的時候，可以用Pj的接收者日志減少回退工作量，即只需要將Pj所收到的報(bào)文重新向Pj發(fā)送一遍即可。

如果進(jìn)程Pj記錄了報(bào)文m的接收者日志，那么Pi和Pj的當(dāng)前檢查點(diǎn)集合就可以看作是一致的。一旦Pj由于失效回退到當(dāng)前檢查點(diǎn)重新執(zhí)行的時候，報(bào)文m就可以通過Pj的接收者日志重新發(fā)送給進(jìn)程Pj，不會引起進(jìn)程Pi的任何回退。36如果Pi在發(fā)送完報(bào)文m后失效，那么當(dāng)進(jìn)程Pi恢復(fù)到當(dāng)前檢查點(diǎn)后，它會根據(jù)發(fā)送者日志的紀(jì)錄知道曾經(jīng)發(fā)送過報(bào)文m，這樣就沒有必要再發(fā)送一次了。如果接收者Pj失效，而且沒有接收者日志，它仍然可以根據(jù)從發(fā)送者日志中得到的報(bào)文正確恢復(fù)。37Alvisi和Marzullo的報(bào)文日志方案報(bào)文格式：每個報(bào)文m包含有一個報(bào)文頭用于存放重發(fā)這個報(bào)文和正確處理這個報(bào)文所必需的一些信息，例如，該報(bào)文的發(fā)送者和接收者，用于識別報(bào)文重復(fù)的序列號，另外還有一個傳輸號用于決定何時該報(bào)文需要傳遞給接收進(jìn)程。

堅(jiān)固的報(bào)文：如果一個報(bào)文不再會丟失，則稱這個報(bào)文是堅(jiān)固的，例如當(dāng)一個報(bào)文已經(jīng)被寫入到堅(jiān)固存儲器中，就可以說這個報(bào)文是堅(jiān)固的。堅(jiān)固的報(bào)文可以重新發(fā)送給失效后重新恢復(fù)的進(jìn)程。進(jìn)程集合DEP(m)的組成：一個報(bào)文m對應(yīng)于一個進(jìn)程集合DEP(m)，該集合包含了與報(bào)文m傳輸有關(guān)的所有進(jìn)程。DEP(m)包含了所有接收該報(bào)文m的進(jìn)程；

如果另外一個報(bào)文m’和報(bào)文m有因果依賴性關(guān)系，并且m’是傳遞給進(jìn)程Q的，那么DEP(m)集合中應(yīng)該包含進(jìn)程Q。因果依賴性關(guān)系：如果m’和m是由同一個進(jìn)程發(fā)送的，并且m的發(fā)送先于m’的發(fā)送，則說m’和報(bào)文m的傳輸有因果依賴性關(guān)系。同樣地，如果m”和m’有因果依賴性關(guān)系，m’和m有因果依賴性關(guān)系，則說m”和m有因果依賴性關(guān)系。38進(jìn)程集合COPY(m)的組成：如果一個進(jìn)程有報(bào)文m的一個拷貝，但是這個拷貝還沒有寫入到它的局部堅(jiān)固存儲器中的話，該進(jìn)程就屬于集合COPY(m)。當(dāng)一個進(jìn)程發(fā)送了報(bào)文m，它也屬于集合COPY(m)。值得注意的是COPY(m)集合中所包含的進(jìn)程是那些擁有報(bào)文m的拷貝，并且在出現(xiàn)失效的時候，能夠重新傳輸報(bào)文m的進(jìn)程。當(dāng)COPY(m)中的所有進(jìn)程都失效時，顯然報(bào)文m就不能被重新傳輸。

孤兒進(jìn)程：假設(shè)在一個分布式系統(tǒng)中，某個或某些進(jìn)程失效了，Q是一個存活下來的進(jìn)程。有一個報(bào)文m，如果進(jìn)程Q是集合DEP(m)中的一個元素，而集合COPY(m)中的所有進(jìn)程都失效了，那么Q就是一個孤兒進(jìn)程。也就是說，當(dāng)一個進(jìn)程依賴于報(bào)文m，但是無法向該進(jìn)程重發(fā)報(bào)文m，該進(jìn)程就是一個孤兒進(jìn)程。

避免孤兒進(jìn)程的出現(xiàn)：需要確保當(dāng)集合COPY(m)中的進(jìn)程都失效的時候，DEP(m)中沒有存活的進(jìn)程。也就是說，DEP(m)中的進(jìn)程也必須全部失效。這可以通過如下的強(qiáng)制方式得以實(shí)現(xiàn)，當(dāng)一個進(jìn)程成為DEP(m)中的一個成員的時候，我們強(qiáng)制它也成為COPY(m)的一個成員。也就是說，當(dāng)一個進(jìn)程依賴于報(bào)文m的傳輸?shù)臅r候，它將保持報(bào)文m的一個副本。39悲觀的日志協(xié)議：每一個非堅(jiān)固的報(bào)文m，確保最多只有一個進(jìn)程依賴于報(bào)文m。也就是說，對于每一個非堅(jiān)定的報(bào)文m，悲觀的日志協(xié)議確保該報(bào)文最多只傳給了一個進(jìn)程。值得注意的是，一旦一個非堅(jiān)定的報(bào)文m傳遞給了進(jìn)程P，P就成為集合COPY(m)的一個成員。最壞的情況是在報(bào)文m寫入到堅(jiān)固存儲器之前，進(jìn)程P失效了。因?yàn)樵诒^的日志協(xié)議下，在報(bào)文m寫入到堅(jiān)固存儲器之前，不允許P發(fā)送任何報(bào)文，所以不會有其他進(jìn)程依賴于報(bào)文m，也就不會有重發(fā)報(bào)文m的可能性。所以，使用悲觀的日志協(xié)議避免了孤兒進(jìn)程的問題。樂觀的日志協(xié)議：在樂觀的日志協(xié)議下，實(shí)際的工作是在失效發(fā)生之后進(jìn)行的。假定對某個報(bào)文m來說，如果集合COPY(m)中的每個進(jìn)程都失效了，DEP(m)中的每個孤兒進(jìn)程一直要回退到以前的某個狀態(tài)，在這個狀態(tài)下，該進(jìn)程不再是集合DEP(m)中的一個成員。很明顯，樂觀的日志協(xié)議需要保持追蹤依賴性關(guān)系，從而使得它的實(shí)現(xiàn)變得復(fù)雜。407.5拜占庭故障的恢復(fù)故障-停止型故障與拜占庭式故障：在故障-停止模型中，我們假定一個處理器將停止工作并且不再恢復(fù)運(yùn)轉(zhuǎn)。在其他情況下，一個故障可能做出破壞性的行為。例如，一個有故障的處理器可能會向不同的處理器發(fā)送不同的令它們費(fèi)解的報(bào)文，這種故障叫做隨意性故障(arbitraryfault)，或拜占庭式故障(Byzantinefault)。由Pease(1980)和Lamport(1982)進(jìn)行了分析。

處理這類故障的一個主要方案是將多個完全相同的進(jìn)程設(shè)置成為一個進(jìn)程組，當(dāng)消息發(fā)送到組本身時，組中所有成員都接收它，從而達(dá)到容錯的目的。7.1.3進(jìn)程容錯機(jī)制－主動復(fù)制（層次故障屏蔽）、被動復(fù)制（編組故障屏蔽）417.5.1恢復(fù)中的設(shè)計(jì)問題進(jìn)程組的內(nèi)部結(jié)構(gòu)：編組目的是把若干等同的進(jìn)程抽象成一個具備容錯能力的虛進(jìn)程。組內(nèi)成員具備彼此通信的能力平面結(jié)構(gòu)(Flatgroup)

：在這種結(jié)構(gòu)中，所有的進(jìn)程都是等價的，要通過彼此協(xié)商才能做出決定。層次結(jié)構(gòu)(Hierarchicalgroup)

：在最簡單的層次結(jié)構(gòu)的進(jìn)程組中，一個進(jìn)程是協(xié)調(diào)者，其他所有的進(jìn)程為工作者。無論是進(jìn)程組外的一個顧客，還是進(jìn)程組中的一個工作者向進(jìn)程組發(fā)出一個工作請求，由協(xié)調(diào)者決定哪一個工作者最適合這項(xiàng)工作，并且將此工作請求轉(zhuǎn)交給它42進(jìn)程組管理：對于進(jìn)程組通信來說，需要一定的辦法進(jìn)行進(jìn)程組的管理，如組播通信、組創(chuàng)建及刪除，同時還要允許進(jìn)程能加入到一個進(jìn)程組中去以及允許一個進(jìn)程離開一個進(jìn)程組。實(shí)現(xiàn)方式：

集中式管理：設(shè)置一個進(jìn)程組服務(wù)員(GroupServer)

，所有的服務(wù)請求都發(fā)送給進(jìn)程組服務(wù)員。進(jìn)程組服務(wù)員使用一個數(shù)據(jù)庫來保存所有進(jìn)程組的信息和一個進(jìn)程組中所有成員的有關(guān)信息

分布式管理：另一種辦法是采用分布方式管理進(jìn)程組。借助于一種可靠的組播通信協(xié)議，各編組自行管理，同時成員的進(jìn)入與退出也通過組播通信進(jìn)行。例如當(dāng)一個組外的進(jìn)程要加入到這個進(jìn)程組時，它向這個進(jìn)程組中的所有成員發(fā)送一個報(bào)文，申明自己要加入到這個進(jìn)程組。存在的問題…437.5.2故障屏蔽和進(jìn)程復(fù)制

利用進(jìn)程組屏蔽故障：進(jìn)程組是構(gòu)造容錯系統(tǒng)問題的一部分。特別是，如果用相同的進(jìn)程來構(gòu)成一個進(jìn)程組，那么就能夠屏蔽進(jìn)程組中一個或多個出錯的進(jìn)程。或者說，我們可以用多個相同的進(jìn)程構(gòu)造一個進(jìn)程組，用這個容錯的進(jìn)程組取代相對脆弱的單個進(jìn)程。利用進(jìn)程組進(jìn)行容錯需要多少個進(jìn)程副本：

令G為一個進(jìn)程編組，如果在G的成員中，只要不多于K個成員同時發(fā)生故障，G可以一直正常運(yùn)行，則G被稱為K容錯故障—停止型故障：如果進(jìn)程組中有k+1個進(jìn)程，那么就足以提供k故障容錯。拜占庭式故障：此時，每個編組至少需要2k+1個進(jìn)程，才能屏蔽K個成員同時發(fā)生的故障，即達(dá)到K容錯能力。447.5.3容錯系統(tǒng)中的一致性算法（分布式協(xié)定算法）分布式協(xié)定算法的目標(biāo)：使得所有無故障進(jìn)程在有限步驟里對某個問題達(dá)成一致性結(jié)論。如下：進(jìn)程組中的每個參加者都將自己的局部決策（布爾值）發(fā)給進(jìn)程組中所有的其他參加者每個參加者根據(jù)自己的局部決策值和收到的其他參加者的局部決策值做出決策（如少數(shù)服從多數(shù)）故障—停止型故障拜占庭式故障45分布式一致算法的正確性條件：(1)一致性。所有正確的進(jìn)程取得一致的結(jié)果，而且是最后的結(jié)果；(2)合法性。所有進(jìn)程同意的結(jié)果必須來自某個正確的進(jìn)程的輸入；(3)有限性。每個進(jìn)程在有限的步驟內(nèi)取得一致的結(jié)果。交互一致性算法交互一致性：系統(tǒng)中的每個非出錯進(jìn)程都使用來自進(jìn)程Pi的同樣的值來進(jìn)行決策。這樣，一般的一致性問題就變?yōu)橄到y(tǒng)中的進(jìn)程都同意一個特殊的進(jìn)程(比如P0)的值。確切地說：所有非出錯進(jìn)程都使用進(jìn)程P0的同樣的值v0若發(fā)送進(jìn)程P0是非出錯的，那么所有非出錯進(jìn)程都使用P0發(fā)送的值。結(jié)論：在有k個出錯節(jié)點(diǎn)的情況下，只有進(jìn)程的總數(shù)至少為3k+1時才能獲得一致。因?yàn)橹挥写嬖?k+1個正確工作的進(jìn)程才能達(dá)成協(xié)議，即只有當(dāng)三分之二以上的進(jìn)程正常工作時才能達(dá)成一致，所以總共有3k+1個進(jìn)程46拜占庭將軍問題

假設(shè)有N支拜占庭部隊(duì)包圍了敵軍，每支部隊(duì)都由一位將軍統(tǒng)領(lǐng)，將軍與將軍之間由信使傳遞信息。將軍之中可能有通敵者，這個(些)通敵者試圖用矛盾的信件來混淆視線，破壞將軍們之間可能達(dá)成的協(xié)定。

假定發(fā)布命令（廣播通信）的將軍是司令，而其他將軍都是軍長，要想達(dá)成一致協(xié)定，所有的軍長都必須“同意”司令發(fā)出的命令。

當(dāng)然，要解決拜占庭將軍問題，每一位將軍都要扮演一次司令的角色，向其他將軍廣播消息。更確切地說，每一位將軍pi都必須把自己的初始值Vi發(fā)送給其他將軍，并滿足下述兩個條件（稱為相互一致性）：

(1)如果發(fā)送者ps是忠誠的，則所有忠誠的將軍都要同意Vs； (2)如果發(fā)送者ps是通敵的，則所有忠誠的將軍都對Vs有一致的看法。

47三位拜占庭將軍問題

（1）首先，我們假定司令通敵。于是他向軍長A發(fā)出“進(jìn)攻”而向軍長B發(fā)出“撤退”的相互矛盾的命令。當(dāng)兩位軍長互相驗(yàn)證所得到的命令時，發(fā)現(xiàn)無法得到一致的結(jié)論?？瓷先ナ撬玖畛隽藛栴}，但問題并非如此簡單。在(2)中，假定司令發(fā)出正確的命令，而軍長B通敵。當(dāng)兩位軍長驗(yàn)證來自司令的命令時，軍長B把“進(jìn)攻”篡改為“撤退”。對軍長A來說，(1)和(2)并無區(qū)別，他在這兩種情況下都收到相互矛盾的消息（一封“進(jìn)攻”，一封“撤退”）。顯然，軍長A不能服從來自司令的命令，因?yàn)槿绻玖钔〝车脑?，兩位忠誠的將軍就不可能一致行動，而是背道而馳；可是，如果司令是忠誠的，軍長A又不能違抗來自司令的命令，如果違抗，將受到軍法從事。于是，軍長A陷入兩難境地，無法做出決定。撤退進(jìn)攻司令進(jìn)攻(1)司令通敵(2)軍長B通敵軍長A軍長B撤退司令進(jìn)攻軍長A軍長B進(jìn)攻撤退進(jìn)攻48（1）我們?nèi)匀患僭O(shè)司令通敵，也就是說，司令向軍長們發(fā)出兩種不同的命令。然而，三位忠誠的軍長在隨后的通信中，都得到一組相同的命令，即（進(jìn)攻，進(jìn)攻，撤退），根據(jù)多數(shù)原則，三位軍長便采取一致的行動，同時發(fā)起進(jìn)攻。而(2)中，軍長C通敵，盡管他篡改了來自司令的命令，軍長A和軍長B還是能夠通過多數(shù)原則做出決定，即執(zhí)行來自司令的正確命令。Lamport等人文章把這個原則推廣到一般情況：在一可能具有拜占庭故障的系統(tǒng)中，我們需要至少3K+1個服務(wù)器才能具備K-容錯的能力

四位拜占庭將軍問題

司令進(jìn)攻軍長C軍長A進(jìn)攻撤退進(jìn)攻進(jìn)攻進(jìn)攻撤退進(jìn)攻軍長B司令軍長A軍長B軍長C進(jìn)攻進(jìn)攻撤退進(jìn)攻進(jìn)攻進(jìn)攻進(jìn)攻1）司令通敵(2)軍長C通敵撤退撤退進(jìn)攻49TheByzantinegeneralsproblemfor3loyalgeneralsand1traitor.Thegeneralsannouncetheirtroopstrengths(inunitsof1kilosoldiers).Thevectorsthateachgeneralassemblesbasedon(a)Thevectorsthateachgeneralreceivesinstep3.AgreementinFaultySystems50AgreementinFaultySystemsThesameasinpreviousslide,exceptnowwith2loyalgeneralsandonetraitor.51

LAMPORT交互一致性算法IC：IC(m)，m<k，開始時m=0，S={}。發(fā)送者將其值和發(fā)送者列表S發(fā)送給其他進(jìn)程，共(n-1-m)個；設(shè)vi是進(jìn)程Pi從發(fā)送者接收到的值或者是如果沒有收到值時使用的缺省值。在IC(m+1≠k)時進(jìn)程Pi作為發(fā)送者，將結(jié)果vi和發(fā)送者列表S∪{Pi}發(fā)送給其他不在發(fā)送者列表中的n-2-m個進(jìn)程。如果m+1=k，則調(diào)用IC(k)；對每個進(jìn)程Pi，設(shè)vj是進(jìn)程Pj接收到的值(但是由Pj轉(zhuǎn)發(fā)給Pi)。節(jié)點(diǎn)使用值majority(vj)，jS；其中，IC(k)：a.發(fā)送者將它的值發(fā)送給其他n-k-1個進(jìn)程；b.每個進(jìn)程使用從接收者收到的值，或者，如果它沒有收到任何值，就使用缺省值。結(jié)論：上述算法中，被交換的報(bào)文總數(shù)為(n-1)(n-2)…(n-k-1)，其復(fù)雜度為O(nk)，k可以是(n-1)/3。52實(shí)例：具有7個進(jìn)程的例子，Pi，0≤i≤6。假定k=2，即最多有2個故障，n=7。設(shè)P0是初始發(fā)送者，發(fā)送值為1。不妨設(shè)P5和P6是出錯進(jìn)程，它向其他進(jìn)程發(fā)送不確定的值。在這個例子中共需要k+1=3輪信息交換：P0將{V0,S}={1,{P0}}發(fā)送給進(jìn)程P1，P2，…，P6。P1至P6中每個進(jìn)程都接收到報(bào)文{1,{P0}}，它們將所收到的報(bào)文轉(zhuǎn)發(fā)給除了開始的發(fā)送者和它本身之外的所有其他的進(jìn)程。例如P1向P2至P6發(fā)送報(bào)文{1,{P0,P1}}。它分別從P2至P6處接收到報(bào)文{1,{P0,P2}}、{1,{P0,P3}}、{1,{P0,P4}}、{d,{P0,P5}}、{d,{P0,P6}}。53在第三輪中，P1將報(bào)文{1,{P0,P2}}以{1,{P0,P2,P1}}的形式分別發(fā)送給進(jìn)程P3、P4、P5、P6，將報(bào)文{1,{P0,P3}}以{1,{P0,P3,P1}}的形式分別發(fā)送給進(jìn)程P2、P4、P5、P6，將報(bào)文{1,{P0,P4}}以{1,{P0,P4,P1}}的形式分別發(fā)送給進(jìn)程P2、P3、P5、P6，將報(bào)文{d,{P0,P5}}以{d,{P0,P5,P1}}的形式分別發(fā)送給進(jìn)程P2、P3、P4、P6，將報(bào)文{d,{P0,P6}}以{d,{P0,P6,P1}}的形式分別發(fā)送給進(jìn)程P2、P3、P4、P5。第三輪遞歸結(jié)束，返回第二輪。進(jìn)程P1收到報(bào)文{1,{P0,P2,P3}}、{1,{P0,P2,P4}}、{d,{P0,P2,P5}}、{d,{P0,P2,P6}}，連同在第二輪中收到的報(bào)文{1,{P0,P2}}，將這5個報(bào)文中的值執(zhí)行majority(1,1,d,d,1)=1，得到的這個新值1作為報(bào)文{1,{P0,P2}}的新值，記為新報(bào)文{1,{P0,P2}}’。同樣的道理，得到新報(bào)文{1,{P0,P3}}’、{1,{P0,P4}}’、{1,{P0,P5}}’、{1,{P0,P6}}’。第二輪遞歸結(jié)束，返回第1輪。P1對6個報(bào)文{1,{P0}}、{1,{P0,P2}}’、{1,{P0,P3}}’、{1,{P0,P4}}’、{1,{P0,P5}}’、{1,{P0,P6}}’中的值執(zhí)行majority(1,1,1,1,1,1)=1，這個新值是P1所確信的最終值。54交互一致性算法的擴(kuò)展

：可以通過對每個發(fā)送者都重復(fù)同樣的協(xié)議將交互一致性擴(kuò)展到多個發(fā)送者的情況。擴(kuò)展的方法：在第k輪收到的值將被發(fā)送到所有的其他節(jié)點(diǎn)，而不僅僅是那些沒有被發(fā)送過的節(jié)點(diǎn)。一致性協(xié)議對系統(tǒng)的要求：同步系統(tǒng)與異步系統(tǒng)：如果所有的處理器都是在可以預(yù)料的速度下運(yùn)行，那么這個系統(tǒng)就是同步的。確切地說，處理器是同步的當(dāng)且僅當(dāng)存在一個常量s≥1，每當(dāng)任何一個處理器運(yùn)行了s+1步，其他的所有處理器都至少運(yùn)行了1步；否則這個系統(tǒng)就是異步的。

55可以得到一致性對系統(tǒng)的要求為：AB+AC+CD=True即在下面三種情況下，系統(tǒng)滿足一致性協(xié)議的要求：(1)(AB=1)，處理器是同步的，通信延遲是有限的；(2)(AC=1)，處理器是同步的，報(bào)文是有序的；(3)(CD=1)，報(bào)文是有序的，傳輸機(jī)制是廣播。用卡諾圖描述一致性對系統(tǒng)的要求：定義布爾變量(1)系統(tǒng)是同步的(A=1)還是異步的(A=0)。(2)通信延遲是有限的(B=1)還是無限的(B=0)。(3)報(bào)文是有序的(C=1)還是無序的(C=0)。(4)傳輸機(jī)制是廣播的(D=1)還是點(diǎn)到點(diǎn)的(D=0)。CD00011110AB000010010010111111100011一致性協(xié)議對系統(tǒng)的要求：567.6可靠的組通信

7.6.1基本的可靠組播方案

所謂可靠的組播通信，就是要求發(fā)送給某個進(jìn)程組的報(bào)文必須確保傳送到進(jìn)程組中的每一個成員。577.6.2可靠組播通信中的可擴(kuò)充性

簡單方案：接收者收到組播報(bào)文后不向發(fā)送者發(fā)送應(yīng)答報(bào)文，只有在接收者發(fā)現(xiàn)丟失一個報(bào)文后，才向發(fā)送者發(fā)送一個反饋報(bào)文，指出某個報(bào)文丟失了。問題1：多個接收者丟失報(bào)文時，仍然會出現(xiàn)反饋報(bào)文擁塞的情況；問題2：在理論上講，發(fā)送者必須在其歷史緩沖區(qū)中長時間保存它發(fā)送的每一個廣播報(bào)文。無等級的反饋控制，F(xiàn)loyd1997成功接收到組播報(bào)文的接收者不向發(fā)送者發(fā)送反饋報(bào)文，只有在接收者