論文地址:http://pmg.csail.mit.edu/papers/osdi99.pdf
PBFT是Practical Byzantine Fault Tolerance的縮寫尚骄，意為實用拜占庭容錯算法佑吝。該算法是Miguel Castro (卡斯特羅)和Barbara Liskov（利斯科夫）在1999年提出來的，解決了原始拜占庭容錯算法效率不高的問題，將算法復雜度由指數(shù)級降低到多項式級犬庇，使得拜占庭容錯算法在實際系統(tǒng)應用中變得可行。該論文發(fā)表在1999年的操作系統(tǒng)設計與實現(xiàn)國際會議上（OSDI99）焊切。沒錯祸轮，這個Loskov就是提出著名的里氏替換原則（LSP）的人，2008年圖靈獎得主哀峻。

摘要部分

OSDI99這篇論文描述了一種副本復制（replication）算法解決拜占庭容錯問題涡相。作者認為拜占庭容錯算法將會變得更加重要，因為惡意攻擊和軟件錯誤的發(fā)生將會越來越多剩蟀，并且導致失效的節(jié)點產(chǎn)生任意行為催蝗。（拜占庭節(jié)點的任意行為有可能誤導其他副本節(jié)點產(chǎn)生更大的危害，而不僅僅是宕機失去響應育特。）而早期的拜占庭容錯算法或者基于同步系統(tǒng)的假設丙号，或者由于性能太低而不能在實際系統(tǒng)中運作。這篇論文中描述的算法是實用的缰冤，因為該算法可以工作在異步環(huán)境中犬缨，并且通過優(yōu)化在早期算法的基礎上把響應性能提升了一個數(shù)量級以上。作者使用這個算法實現(xiàn)了拜占庭容錯的網(wǎng)絡文件系統(tǒng)（NFS）棉浸，性能測試證明了該系統(tǒng)僅比無副本復制的標準NFS慢了3%怀薛。

1.概要介紹

這篇論文提出解決拜占庭容錯的狀態(tài)機副本復制（state machine replication）算法。這個算法在保證活性和安全性（liveness & safety）的前提下提供了(n-1)/3的容錯性迷郑。從Lamport教授在1982年提出拜占庭問題開始枝恋，已經(jīng)有一大堆算法去解決拜占庭容錯了。PBFT在之上進行了優(yōu)化使得能夠應用在實際場景嗡害，在只讀操作中只使用1次消息往返（message round trip）鼓择，在只寫操作中只使用2次消息往返，并且在正常操作中使用了消息驗證編碼（Message Authentication Code,簡稱MAC）就漾，而造成妖艷賤貨性能低下的公鑰加密（public-key cryptography）只在發(fā)生失效的情況下使用（viewchange
and new-view messages）呐能。作者不僅提出算法，而且使用這個算法實現(xiàn)了一個拜占庭容錯的NFS服務抑堡。
作者列舉一下這邊論文的貢獻：

1）首次提出在異步網(wǎng)絡環(huán)境下使用狀態(tài)機副本復制協(xié)議
2）使用多種優(yōu)化使性能顯著提升
3）實現(xiàn)了一種拜占庭容錯的分布式文件系統(tǒng)
4）為副本復制的性能損耗提供試驗數(shù)據(jù)支持

2.系統(tǒng)模型

系統(tǒng)假設為異步分布式的摆出，通過網(wǎng)絡傳輸?shù)南⒖赡軄G失、延遲首妖、重復或者亂序偎漫。作者假設節(jié)點的失效必須是獨立發(fā)生的，也就是說代碼有缆、操作系統(tǒng)和管理員密碼這些東西在各個節(jié)點上是不一樣的象踊。

作者使用了加密技術來防止欺騙攻擊和重播攻擊温亲，以及檢測被破壞的消息。消息包含了公鑰簽名（其實就是RSA算法）杯矩、消息驗證編碼（MAC）和無碰撞哈希函數(shù)生成的消息摘要（message digest）栈虚。使用m表示消息，mi表示由節(jié)點i簽名的消息史隆，D(m)表示消息m的摘要魂务。按照慣例，只對消息的摘要簽名泌射，并且附在消息文本的后面粘姜。并且假設所有的節(jié)點都知道其他節(jié)點的公鑰以進行簽名驗證。

系統(tǒng)允許攻擊者可以操縱多個失效節(jié)點熔酷、延遲通訊孤紧、甚至延遲正確節(jié)點。但是不能無限期地延遲正確的節(jié)點拒秘，并且算力有限不能破解加密算法坛芽。例如，不能偽造正確節(jié)點的有效簽名翼抠，不能從摘要數(shù)據(jù)反向計算出消息內(nèi)容咙轩，或者找到兩個有同樣摘要的消息。
message digests:https://www.techopedia.com/definition/4024/message-digest

可以理解為checksum, 對文件內(nèi)容進行hash, 如果文件內(nèi)容被修改則hash改變, 用以驗證文件是否損壞/被修改. MD5, SHA等算法都可以用作生成message digest的算法)

Cryptographic hash function

密碼學中將輸入數(shù)據(jù)作為message, 輸出數(shù)據(jù), 即hash value, 記做message digest = 消息摘要.
僅對message digest進行簽名, 而不是對整個message進行簽名.
什么是簽名
非對稱加密中使用私鑰對消息+自己的身份進行加密, 外部節(jié)點使用公鑰進行解密, 可以看到加密方的身份, 即為簽名

3.服務屬性

這部分描述了副本復制服務的特性

論文算法實現(xiàn)的是一個具有確定性的副本復制服務阴颖，這個服務包括了一個狀態(tài)（state）和多個操作（operations）活喊。這些操作不僅能夠進行簡單讀寫，而且能夠基于狀態(tài)和操作參數(shù)進行任意確定性的計算量愧〖鼐眨客戶端向副本復制服務發(fā)起請求來執(zhí)行操作，并且阻塞以等待回復偎肃。副本復制服務由n個節(jié)點組成煞烫。

針對安全性

算法在失效節(jié)點數(shù)量不超過（n-1)/3的情況下同時保證安全性和活性（safety & liveness）。安全性是指副本復制服務滿足線性一致性（linearizability）,就像中心化系統(tǒng)一樣原子化執(zhí)行操作累颂。安全性要求失效副本的數(shù)量不超過上限滞详，但是對客戶端失效的數(shù)量和是否與副本串謀不做限制。系統(tǒng)通過訪問控制來限制失效客戶端可能造成的破壞紊馏，審核客戶端并阻止客戶端發(fā)起無權執(zhí)行的操作料饥。同時，服務可以提供操作來改變一個客戶端的訪問權限朱监。因為算法保證了權限撤銷操作可以被所有客戶端觀察到岸啡，這種方法可以提供強大的機制從失效的客戶端攻擊中恢復。

針對活性

算法不依賴同步提供安全性赫编，因此必須依靠同步提供活性巡蘸。否則奋隶，這個算法就可以被用來在異步系統(tǒng)中實現(xiàn)共識，而這是不可能的（由Fischer1985的論文證明）悦荒。本文的算法保證活性唯欣，即所有客戶端最終都會收到針對他們請求的回復，只要失效副本的數(shù)量不超過（n-1)/3逾冬，并且延遲delay(t)不會無限增長黍聂。這個delay(t)表示t時刻發(fā)出的消息到它被目標最終接收的時間間隔躺苦，假設發(fā)送者持續(xù)重傳直到消息被接收身腻。這時一個相當弱的同步假設，因為在真實系統(tǒng)中網(wǎng)絡失效最終都會被修復匹厘。但是這就規(guī)避了Fischer1985提出的異步系統(tǒng)無法達成共識的問題嘀趟。

下面這段話是關鍵

本文的算法是最優(yōu)的：當存在f個失效節(jié)點時必須保證存在至少3f+1
個副本數(shù)量，這樣才能保證在異步系統(tǒng)中提供安全性和活性愈诚。這么多數(shù)量的副本是需要的她按，因為在同n-f個節(jié)點通訊后系統(tǒng)必須做出正確判斷，由于f個副本有可能失效而不發(fā)回響應炕柔。但是酌泰，有可能f個失效的節(jié)點是好節(jié)點，f個壞節(jié)點依然發(fā)送請求匕累。盡管如此陵刹，系統(tǒng)仍舊需要好節(jié)點的返回數(shù)量大于壞節(jié)點的返回數(shù)量，即n-2f>f欢嘿，因此得到n>3f衰琐。

算法不能解決信息保密的問題，失效的副本有可能將信息泄露給攻擊者炼蹦。在一般情況下不可能提供信息保密羡宙，因為服務操作需要使用參數(shù)和服務狀態(tài)處理任意的計算，所有的副本都需要這些信息來有效執(zhí)行操作掐隐。當然狗热，還是有可能在存在惡意副本的情況下通過秘密分享模式（secret sharing scheme）來實現(xiàn)私密性，因為參數(shù)和部分狀態(tài)對服務操作來說是不可見的虑省。
推理
由于有f個壞節(jié)點, 它們可能完全不回復消息, 所以我們要確倍犯悖客戶端只要接收到n-f個消息就足以做出判斷. 不能依賴于更多的信息, 否則等待永不回復壞節(jié)點就意味著liveness被破壞.
考慮一個最差的情況: 那f個還未回復的節(jié)點是好節(jié)點, 收到的n-f個消息中有f個壞節(jié)點消息. 那么接到的好節(jié)點的消息實際上是 n-2f個, 壞節(jié)點消息是f個. 根據(jù)少數(shù)服從多數(shù), 需要n-2f>f, 即n>3f.
綜上, 全網(wǎng)總節(jié)點數(shù)n至少是3f+1才能確保安全性和Liveness.

4.算法

PBFT是一種狀態(tài)機副本復制算法，即服務作為狀態(tài)機進行建模慷妙，狀態(tài)機在分布式系統(tǒng)的不同節(jié)點進行副本復制僻焚。每個狀態(tài)機的副本都保存了服務的狀態(tài)，同時也實現(xiàn)了服務的操作膝擂。將所有的副本組成的集合使用大寫字母R表示虑啤，使用0到|R|-1的整數(shù)表示每一個副本隙弛。為了描述方便，假設|R|=3f+1，這里f是有可能失效的副本的最大個數(shù)纳账。盡管可以存在多于3f+1個副本蔼水，但是額外的副本除了降低性能之外不能提高可靠性。

所有的副本在一個被稱為視圖（View）的輪換過程（succession of configuration）中運作总珠。在某個視圖中，一個副本作為主節(jié)點（primary）勘纯，其他的副本作為備份（backups）局服。視圖是連續(xù)編號的整數(shù)。主節(jié)點由公式p = v mod |R|計算得到驳遵，這里v是視圖編號淫奔，p是副本編號，|R|是副本集合的個數(shù)堤结。當主節(jié)點失效的時候就需要啟動視圖更換（view change）過程唆迁。Viewstamped Replication算法和Paxos算法就是使用類似方法解決良性容錯的。
重要概念: View.
節(jié)點運行過程中, 全網(wǎng)絡的配置(configuration)是在不斷變化的. 比方說現(xiàn)在的配置是A節(jié)點是主節(jié)點, 其余節(jié)點都是從節(jié)點, 那么一段時間后, 這個配置可能改變?yōu)锽節(jié)點為主節(jié)點, 其余從節(jié)點.
我們將每一次的配置狀態(tài)稱為一個View. 整個網(wǎng)絡就是不斷在不同的View之間切換的.
記當前View的編號為v, 編號為p = v % n的節(jié)點就作為主節(jié)點, 其余作為從節(jié)點. 當主節(jié)點失效時, 進行View的切換.

PBFT算法如下：
1.客戶端向主節(jié)點發(fā)送請求調(diào)用服務操作
2.主節(jié)點通過廣播將請求發(fā)送給其他副本
3.所有副本都執(zhí)行請求并將結(jié)果發(fā)回客戶端
4.客戶端需要等待f+1個不同副本節(jié)點發(fā)回相同的結(jié)果竞穷，作為整個操作的最終結(jié)果唐责。

同所有的狀態(tài)機副本復制技術一樣，PBFT對每個副本節(jié)點提出了兩個限定條件：（1）所有節(jié)點必須是確定性的瘾带。也就是說鼠哥，在給定狀態(tài)和參數(shù)相同的情況下，操作執(zhí)行的結(jié)果必須相同月弛；（2）所有節(jié)點必須從相同的狀態(tài)開始執(zhí)行肴盏。在這兩個限定條件下，即使失效的副本節(jié)點存在帽衙，PBFT算法對所有非失效副本節(jié)點的請求執(zhí)行總順序達成一致菜皂，從而保證安全性。

接下去描述簡化版本的PBFT算法厉萝，忽略磁盤空間不足和消息重傳等細節(jié)內(nèi)容恍飘。并且，本文假設消息驗證過程是通過數(shù)字簽名方法實現(xiàn)的谴垫，而不是更加高效的基于消息驗證編碼（MAC）的方法章母。

4.1客戶端

客戶端c向主節(jié)點發(fā)送<REQUEST,o,t,c>請求執(zhí)行狀態(tài)機操作o，這里時間戳t用來保證客戶端請求只會執(zhí)行一次翩剪∪樵酰客戶端c發(fā)出請求的時間戳是全序排列的，后續(xù)發(fā)出的請求比早先發(fā)出的請求擁有更高的時間戳前弯。例如蚪缀，請求發(fā)起時的本地時鐘值可以作為時間戳秫逝。

每個由副本節(jié)點發(fā)給客戶端的消息都包含了當前的視圖編號，使得客戶端能夠跟蹤視圖編號询枚，從而進一步推算出當前主節(jié)點的編號违帆。客戶端通過點對點消息向它自己認為的主節(jié)點發(fā)送請求金蜀，然后主節(jié)點自動將該請求向所有備份節(jié)點進行廣播刷后。

副本發(fā)給客戶端的響應為<REPLY,v,t,c,i,r>，v是視圖編號渊抄，t是時間戳尝胆，i是副本的編號，r是請求執(zhí)行的結(jié)果抒线。

客戶端等待f+1個從不同副本得到的同樣響應班巩，同樣響應需要保證簽名正確渣慕，并且具有同樣的時間戳t和執(zhí)行結(jié)果r嘶炭。這樣客戶端才能把r作為正確的執(zhí)行結(jié)果，因為失效的副本節(jié)點不超過f個逊桦，所以f+1個副本的一致響應必定能夠保證結(jié)果是正確有效的眨猎。

如果客戶端沒有在有限時間內(nèi)收到回復，請求將向所有副本節(jié)點進行廣播强经。如果請求已經(jīng)在副本節(jié)點處理過了睡陪，副本就向客戶端重發(fā)一遍執(zhí)行結(jié)果。如果請求沒有在副本節(jié)點處理過匿情，該副本節(jié)點將把請求轉(zhuǎn)發(fā)給主節(jié)點兰迫。如果主節(jié)點沒有將該請求進行廣播，那么就有認為主節(jié)點失效炬称，如果有足夠多的副本節(jié)點認為主節(jié)點失效汁果，則會觸發(fā)一次視圖變更。

本文假設客戶端會等待上一個請求完成才會發(fā)起下一個請求玲躯，但是只要能夠保證請求順序据德，可以允許請求是異步的。

4.2 PBFT算法主線流程（正常情況）

每個副本節(jié)點的狀態(tài)都包含了:

• 服務的整體狀態(tài)
• 副本節(jié)點上的消息日志(message log)包含了該副本節(jié)點接受(accepted)的消息
• 當前視圖編號v跷车。

請求開始

當主節(jié)點p收到客戶端的請求m棘利，主節(jié)點將該請求向所有副本節(jié)點進行廣播，然后展開一個三階段協(xié)議（three-phase protocol）朽缴。在這里善玫，如果請求太多, 主節(jié)點會將請求buffer起來稍后再處理。

三階段協(xié)議

我們重點討論預準備（pre-prepare）密强、準備(prepare)和確認(commit)這三個階段茅郎。pre-prepare和prepare兩個階段用對同一個視圖中的requests進行排序（即使對請求進行排序的主節(jié)點失效了）裹唆，prepare和commit兩個階段用來確保在不同的view之間的requests是嚴格排序的。

預準備階段

在預準備階段只洒，主節(jié)點(primary)分配一個序列號n給request许帐，然后向所有backup node發(fā)送PRE-PREPARE消息，PRE-PREPARE消息的格式為<<PRE-PREPARE,v,n,d>,m>毕谴，這里v是視圖編號成畦，m是客戶端發(fā)送的請求消息，d是請求消息m的摘要涝开。

請求m本身是不包含在預準備的消息里面的循帐，這樣就能使預準備消息足夠小，因為預準備消息的目的是作為一種證明舀武，確定該請求是在視圖v中被賦予了序號n拄养，從而在視圖變更的過程中可以追索。另外一個層面银舱，將“將排序的協(xié)議”和“廣播請求的協(xié)議”進行解耦瘪匿，有利于對消息傳輸?shù)男蔬M行深度優(yōu)化。

只有滿足以下條件寻馏，各個backup node才會接受一個PRE-PREPARE 消息：

1. 請求和pre-prepare消息的簽名都正確, d是m的digest
2. 當前視圖編號是v棋弥。
3. 該備份節(jié)點從未在視圖v中接受過序號為n但是摘要d不同的消息m。
4. 編號n在下限h和上限H之間. (這是為了避免壞的主節(jié)點通過設置一個超大的n來窮盡編號)

進入準備階段

如果備份節(jié)點i接受了預準備消息<<PRE-PREPARE,v,n,d>,m>诚欠，則進入準備階段顽染。在準備階段的同時，該節(jié)點向所有backup node發(fā)送準備消息<PREPARE,v,n,d,i>轰绵，并且將PRE-PREPARE消息和PREPARE消息寫入自己的消息日志粉寞。backup node若不接受pre-prepare消息就什么都不做。

接受準備消息需要滿足的條件

包括主節(jié)點在內(nèi)的所有副本節(jié)點在收到準備消息之后左腔，1唧垦、對消息的簽名是否正確，2翔悠、視圖編號v是否一致业崖，3消息序號n是否滿限制這三個條件進行驗證，如果驗證通過則把這個準備消息寫入消息日志中蓄愁。

準備階段完成的標志

當且僅當節(jié)點i將如下消息插入到message log后, 我們才認為節(jié)點進入準備完畢狀態(tài), 記做prepared(m, v, n, i).

• 請求m
• 針對m, v, n的pre-prepare消息
• 2f個來自不同從節(jié)點(只有backup)的對應于pre-prepare的prepare消息(算上自己的那個prepare消息). 如何驗證對應關系? 通過視圖編號v双炕、消息序號n和摘要d。

為啥要2f個： 因為prepare消息主節(jié)點不參與發(fā)送, 這樣全網(wǎng)3f+1個節(jié)點刨去主節(jié)點和惡意節(jié)點(f+1)個, 剩下的是2f個好節(jié)點.

預準備階段和準備階段確保所有正常節(jié)點對同一個視圖中的請求排序達成一致撮抓。接下去是對這個結(jié)論的形式化證明：如果prepared(m,v,n,i)為真妇斤，則prepared(m',v,n,j)必不成立(i和j表示副本編號，i可以等于j)，這就意味著至少f+1個正常節(jié)點在視圖v的預準備或者準備階段發(fā)送了序號為n的消息m站超。
證明：
反證法：假如有prepared(m,v,n,i)為真且prepared(m',v,n,j)也為真荸恕，那么可以又接受prepared的條件可以看出，有f+1個好節(jié)點（包括他本身）發(fā)出了prepare消息接受m死相，另有f+1個好節(jié)點發(fā)出了prepare接受m',這樣好節(jié)點為2f+2 但是N=3f+1,好節(jié)點只有N-f=2f+1個融求，有矛盾。

進入確認階段

當prepared(m,v,n,i)條件為真的時候算撮，副本i將<COMMIT,v,n,D(m),i>向其他副本節(jié)點廣播生宛，于是就進入了確認階段。每個副本接受確認消息的條件是：1）簽名正確肮柜；2）消息的視圖編號與節(jié)點的當前視圖編號一致陷舅；3）消息的序號n滿足水線條件，在h和H之間审洞。一旦確認消息的接受條件滿足了莱睁，則該副本節(jié)點將確認消息寫入消息日志中。（補充：需要將針對某個請求的所有接受的消息寫入日志芒澜，這個日志可以是在內(nèi)存中的）仰剿。

committed && committed-local

我們定義committed(m,v,n)為真得條件為：任意f+1個好節(jié)點進入prepared(m,v,n,i)為真的時候；(不帶節(jié)點編號i表示是一個整體狀態(tài))
committed-local(m,v,n,i)為真的條件為：prepared(m,v,n,i)為真撰糠，并且i已經(jīng)接受了2f+1個commit消息（包括自身在內(nèi)）和與之對應一致的pre-prepare消息酥馍。commit與pre-prepare消息一致的條件是具有相同的視圖編號v辩昆、消息序號n和消息摘要d阅酪。

確認被接受的形式化描述

commit階段保證了以下這個不變式（invariant）：對某個好節(jié)點i來說，如果committed-local(m,v,n,i)為真則committed(m,v,n)也為真汁针。(也就是說只要有一個好節(jié)點到了committed-local狀態(tài)則整體就達到了committed狀態(tài))
證明：
某個好節(jié)點i達到committed-local說明其至少接收了2f+1個節(jié)點的commit消息术辐，所以至少有f+1個好節(jié)點的commit消息。好節(jié)點發(fā)送commit需要保證是已經(jīng)進入prepared狀態(tài)才行施无。這樣就至少有f+1個好節(jié)點進入了prepared狀態(tài)辉词，也意味著整體進入了committed狀態(tài)。

這個不變式和視圖變更協(xié)議保證了所有正常節(jié)點對本地確認的請求的序號達成一致猾骡，即使這些請求在每個節(jié)點的確認處于不同的視圖瑞躺。更進一步地講，只要有一個號節(jié)點到達committed狀態(tài)兴想，那么至少有f+1個好節(jié)點也會到達committed狀態(tài)幢哨。

故事的終結(jié)

每個副本節(jié)點i在committed-local(m,v,n,i)為真之后執(zhí)行m的請求，并且i的狀態(tài)反映了所有編號小于n的請求依次順序執(zhí)行嫂便。這就確保了所有正常節(jié)點以同樣的順序執(zhí)行所有請求捞镰，這樣就保證了算法的正確性（safety）。在完成請求的操作之后，每個副本節(jié)點都向客戶端發(fā)送回復岸售。副本節(jié)點會把時間戳比已回復時間戳更小的請求丟棄践樱，以保證請求只會被執(zhí)行一次。

我們不依賴于消息的順序傳遞凸丸，因此某個副本節(jié)點可能亂序確認請求拷邢。因為每個副本節(jié)點在請求執(zhí)行之前已經(jīng)將預準備、準備和確認這三個消息記錄到了日志中屎慢，這樣亂序就不成問題了解孙。

下圖展示了在沒有發(fā)生主節(jié)點失效的情況下算法的正常執(zhí)行流程，其中副本0是主節(jié)點抛人，副本3是失效節(jié)點弛姜，而C是客戶端。

PBFT算法流程

在這里插入圖片描述

4.3 垃圾回收
=
為了節(jié)省內(nèi)存妖枚，系統(tǒng)需要一種將日志中的無異議消息記錄刪除的機制廷臼。為了保證系統(tǒng)的安全性，副本節(jié)點在刪除自己的消息日志前绝页，需要確保至少f+1個正常副本節(jié)點執(zhí)行了消息對應的請求荠商，并且可以在視圖變更時向其他副本節(jié)點證明。另外续誉，如果一些副本節(jié)點錯過部分消息莱没，但是這些消息已經(jīng)被所有正常副本節(jié)點刪除了（例如故障恢復），這就需要通過傳輸部分或者全部服務狀態(tài)實現(xiàn)該副本節(jié)點的同步酷鸦。因此饰躲，副本節(jié)點同樣需要證明狀態(tài)的正確性。

在每一個操作執(zhí)行后都生成這樣的證明是非常消耗資源的臼隔。因此嘹裂，證明過程只有在請求序號可以被某個常數(shù)（比如100）整除的時候才會周期性地進行。我們將這些請求執(zhí)行后得到的狀態(tài)稱作檢查點（checkpoint）摔握，并且將具有證明的檢查點稱作穩(wěn)定檢查點（stable checkpoint）寄狼。

副本節(jié)點保存了服務狀態(tài)的多個邏輯拷貝，包括最新的穩(wěn)定檢查點氨淌，零個或者多個非穩(wěn)定的檢查點泊愧，以及一個當前狀態(tài)。寫時復制技術可以被用來減少存儲額外狀態(tài)拷貝的空間開銷盛正。

檢查點的正確性證明的生成過程如下：當副本節(jié)點i生成一個檢查點后删咱，向其他副本節(jié)點廣播檢查點消息<CHECKPOINT,n,d,i>，這里n是最近一個影響狀態(tài)的請求序號蛮艰，d是狀態(tài)的摘要腋腮。每個副本節(jié)點都默默地在各自的日志中收集并記錄其他節(jié)點發(fā)過來的檢查點消息雀彼，直到收到來自2f+1個不同副本節(jié)點的具有相同序號n和摘要d的檢查點消息。這2f+1個消息就是這個檢查點的正確性證明即寡。

具有證明的檢查點成為穩(wěn)定檢查點徊哑，然后副本節(jié)點就可以將所有序號小于等于n的預準備、準備和確認消息從日志中刪除聪富。同時也可以將之前的檢查點和檢查點消息一并刪除莺丑。

檢查點協(xié)議可以用來更新水線（watermark）的高低值（h和H），這兩個高低值限定了可以被接受的消息墩蔓。水線的低值h與最近穩(wěn)定檢查點的序列號相同梢莽，而水線的高值H=h+k，k需要足夠大才能使副本不至于為了等待穩(wěn)定檢查點而停頓奸披。加入檢查點每100個請求產(chǎn)生一次昏名，k的取值可以是200。

4.4 view-change視圖變更

view-change存在的意義: 主節(jié)點壞掉了, 更換view(即更換主節(jié)點primary), 以此來保證全網(wǎng)的liveness.使用計時器的超時機制觸發(fā)view-change阵面。

從節(jié)點觸發(fā)View Change

視圖變更可以由從節(jié)點timeout觸發(fā)轻局，以防止從節(jié)點無期限地等待請求的執(zhí)行。從節(jié)點等待一個請求样刷，就是該節(jié)點接收到一個有效請求仑扑，但是還沒有執(zhí)行它。當從節(jié)點接收到一個請求但是計時器還未運行置鼻，那么它就啟動計時器镇饮；當它不再等待請求的執(zhí)行就把計時器停止，但是當它等待其他請求執(zhí)行的時候再次情動計時器箕母。

從節(jié)點廣播View Change

當計時器超時的時候储藐，會觸發(fā)view-change，使v變?yōu)関+1司蔬，并停止服務（除了接收checkpoint, view-change, and new-view messages）并廣播< VIEW-CHANGE,v+1邑茄，n，C俊啼，P，i >消息到所有節(jié)點（n為最近的一個stable checkpoint對應的請求號左医，C表示2f+1個有效的checkpoint的證明授帕，P是一個包含若干個Pm的集合. 其中Pm的定義: 對于編號大于n且已經(jīng)在節(jié)點i prepared的消息m, Pm包含一個合法的pre-prepare消息(不包括對應的client message)和2f個對應的, 由不同節(jié)點簽名的prepare消息(v, n, D(m)要一樣)）。

新的主節(jié)點上位

View v+1的主節(jié)點p接收到2f個來自不同其他節(jié)點的view-change消息后, 就廣播<NEW-VIEW, v+1, V, O>_sigma_p到所有節(jié)點.
V :集合{p接收到的view-change消息, p發(fā)送(或者應該發(fā)送)的對于v+1的view-change消息}
O: 一個包含若干pre-prepare消息的集合(不順帶請求), 包含如下內(nèi)容:

• 主節(jié)點從V中找到
• min-s, 即最近一次stable checkpoint的編號.
• V中所有prepare消息的最大的編號max-s.
• 對min-s和max-s之間的每個編號n, 主節(jié)點創(chuàng)建一個新的pre-prepare消息, 用于View v+1. 兩種情況:
• V中的某個編號為n的view-change消息, 其P集合不為空. 這種情況下, 主節(jié)點創(chuàng)建一個新的pre-prepare消息<PRE-PREPARE, v+1, n, d>_sigma_p
• 其P集合為空. 主節(jié)點創(chuàng)建一個新的pre-prepare消息<PRE-PREPARE, v+1, n, d^null>_sigma_p, 其中d^null是一個特殊的null請求的digest. 該操作什么都不做.

然后, 主節(jié)點將O中的信息插入到log中. 如果min-s大于它最近一個checkpoint的編號, 主節(jié)點要計算編號為min-s的checkpoint的proof, 并將其插入到log中, 然后按照4.3中所講進行垃圾回收.
至此, 主節(jié)點正式進入View v+1, 可以接受關于v+1的消息.

從節(jié)點接受新的主節(jié)點

如果從節(jié)點接受的new-view消息滿足如下條件

• 簽名合法
• V中的view-change消息合法.
• O合法 (算法類似于主節(jié)點創(chuàng)建O的算法)

從節(jié)點會將這些消息加入到log中(跟上一段的主節(jié)點操作一樣), 然后對于O中的每一個pre-prepare消息, 廣播對應的prepare消息到所有節(jié)點并插入log, 正是進入View v+1.