目錄

0-前言

1-導引

2-不可能性

3將軍(1叛徒)問題不存在解/不能達成共識

少于3m+1個將軍(有m個叛徒)不存在解/不能達成共識

精確一致性與近似一致性是同等困難的

3-使用口頭消息的解

“口頭消息”的含義

OM(m)算法的步驟

OM(m)算法的正確性推導

4-使用簽名消息情況下的解

“簽名消息”的含義

SM(m)算法的步驟

SM(m)算法的正確性推導

5-通信路徑缺失

6-可靠性系統(tǒng)

可靠性系統(tǒng)的要素

消息傳遞系統(tǒng)的約束

7-小結

8-參考文獻

---

• 0-前言

• 下面部分摘自Lamport的my writings，my writings是Lamport本人對自己以往發(fā)表的論文的一些總結，其中很多文字涉及到這些論文的創(chuàng)作來源
• 從下面的文字可以看出，該論文的內(nèi)容實際上已發(fā)表在1980年的<<Reaching Agreement in the Presence of Faults>>中，只是引入了拜占庭將軍這一說法，同時增加了一些新的內(nèi)容
  • 我一直覺得正是因為通過用一組圍坐在圓桌旁的哲學家來表述，Dijkstra 的哲學家就餐問題才變得如此讓人關注(比如在理論界，它可能比讀者/寫者問題都引人注目，盡管讀者/寫者問題可能更具實際意義)，我認為<<Reaching Agreement in the Presence of Faults>>所描述的問題十分重要，值得計算機科學家們?nèi)リP注
  • 哲學家就餐問題使我認識到，把問題以講故事的形式表達出來更能引起人們的關注
  • 在分布式計算領域有一個被稱作中國將軍問題的問題
  • 在這個問題中，兩個將軍必須在進攻還是撤退上達成一致，但是相互只能通過信使傳送消息，而且這個信使可能永遠都無法到達
  • 我借用了這里的將軍的叫法，并把它擴展成一組將軍，同時這些將軍中有的是叛徒，他們需要達成一致的決定
  • 同時我想給這些將軍賦予一個國家，同時不能得罪任何讀者
  • 那時候，阿爾巴尼亞還是一個完全封閉的國家，所以我覺得應該不會有阿爾巴尼亞人看到這篇文章，所以最初的時候這篇論文題目實際是The Albanian Generals Problem
  • 但是Jack Goldberg后來提醒我在這個世界上阿爾巴尼亞之外還有很多阿爾巴尼亞移民，所以建議我換個名字
  • 于是就想到了這個更合適的Byzantine generals的叫法
  • 寫這篇論文的主要目的是將Byzantine generals這個叫法用在這個問題上
  • 但是一篇新的論文需要有新的想法，于是提出了一種描述通用的3n+1處理單元的算法簡單方式(Shostak的4處理單元算法很精妙而且容易理解，但是Pease的通用化擴展算法卻不那么好懂)
  • 同時我們將網(wǎng)絡擴展到非全互聯(lián)網(wǎng)絡的情況，而且增加了一些實現(xiàn)相關的細節(jié)
• 一個可靠的計算機系統(tǒng)必須處理有故障的組件，這些組件可能引入與系統(tǒng)其它部分相沖突的信息
• 這樣的場景可以用一組指揮軍隊圍困敵國城市的拜占庭將軍來描述
• 將軍之間只能通過信使傳遞信息，他們必須在相同的作戰(zhàn)方案上達成一致
• 但是，他們之中可能存在叛徒，這些叛變的將軍會竭力的擾亂其它人
• 拜占庭將軍問題，就是指找到一種算法可以保證那些忠誠的將軍可以達成一致
• 結果表明，如果使用口頭信息，當且僅當超過三分之二的將軍是忠誠的時候該問題才可解，也就是說一個將軍可以擾亂兩個將軍
• 如果使用不可偽造的書面信息，對于任何數(shù)目的將軍和叛徒，該問題都是可解的
• 此外，本文還討論了如何將該問題的解應用于可靠的計算機系統(tǒng)實現(xiàn)中

• 1-導引

• 一個可靠的計算機系統(tǒng)必須能夠處理一個或多個的組件的失敗
• 一個失敗的組件可能會表現(xiàn)出一種經(jīng)常被忽略的行為：向系統(tǒng)的其他部分發(fā)送相矛盾的信息
• 可以將處理這種失敗的情況的問題抽象出來，就是這里的拜占庭將軍問題
• 在論文的絕大部分內(nèi)容都是討論這個抽象后的問題，只是在末尾會討論如何將該問題的解應用在可靠計算機系統(tǒng)的實現(xiàn)中
• 假設有幾股拜占庭軍隊現(xiàn)在正在一個敵城外扎營，每股軍隊由一個將軍指揮
• 將軍之間只能通過信使通信
• 觀察完敵情后，他們必須達成一個相同的行動計劃
• 然而，有些將軍可能是叛徒，他們會盡力阻止那些忠誠的將軍達成一致
• 將軍們必須有一個算法來保證如下條件：
  • A-所有忠誠的將軍必須達成相同的行動計劃
    • 忠誠的將軍將會做該算法要求他們做的事情，但是叛變的將軍可以做任何他們想做的事情
    • 無論叛變的將軍會做什么，算法必須要保證條件A
  • 誠實的將軍不能僅僅達成一致，他們還應該達成一個合理的行動計劃
  • 也就是說，實際上我們想保證：
  • B-當只有少數(shù)人是叛徒的時候，他們不能導致那些誠實的將軍們采納一個糟糕的計劃
  • 條件B很難去形式化，因為它需要精確的定義何謂糟糕的計劃，當然我們也并不嘗試去給出這樣的一個定義
  • 我們來考慮將軍們?nèi)绾巫龀鰶Q定，每個將軍都會觀察敵情，并將他的觀察結果告訴其他將軍
  • 假設v(i)代表第i個將軍發(fā)送的信息
  • 每個將軍使用某種方法來根據(jù)這些信息v(1),v(2)……v(n)來擬定作戰(zhàn)計劃(n代表將軍的總數(shù))
  • 通過讓所有的將軍使用同一種方法就可以滿足條件A，通過使用一種健壯的方法條件B也可以滿足
  • 比如，現(xiàn)在需要決定是進攻還是撤退，v(i)代表第i個將軍關于進攻還是撤退的意見，最終的決定可以通過在他們之間進行一個多數(shù)決的投票來決定
  • 在這種情況下，只有當持兩種意見的忠誠將軍數(shù)目幾乎相同時，少數(shù)的叛變將軍才能影響最終的結果
  • 但是這種情況下，無論是進攻還是撤退都算不上是糟糕的方案(這就說明滿足條件B)
  • 雖然這種策略可能不是滿足條件A和B的唯一一種方式，但是目前我們僅想到這一個
  • 該方法假設存在一種方法，將軍們可以相互傳遞各自的v(i)值
  • 很明顯的一種方法是，將軍i，讓他的信使將v(i)送給所有的將軍
  • 但是，這樣行不通，因為如果要滿足條件A，需要每個忠誠的將軍收到相同的v(1),v(2)……v(n)，但是一個叛變的將軍可能會給不同的將軍發(fā)送不同的值
  • 對于條件A來說，如果要滿足，下面的條件必須成立：
    • 1-每個忠誠的將軍必須收到相同的v(1),v(2)……v(n)
      • 條件1暗示一個將軍并沒有必要使用一個直接從第i個將軍那收到的v(i)值，因為一個叛變的第i將軍可能給不同的將軍發(fā)送不同的v(i)值
      • 但是這樣意味著，滿足條件1的同時，很可能一不小心就使用了一個與第i將軍發(fā)送的v(i)不同的值，即使第i個將軍是誠實的(因為我們可能采用了從其他將軍處得來的關于v(i)的值，但是這個將軍可能是叛變者，它可能自己已經(jīng)改變了v(i)的值，這樣即使第i將軍是誠實的，但是經(jīng)過叛變者之后它的值也已不再受控了)
      • 但是為了滿足條件B，我們絕不允許這種情況發(fā)生
      • 比如我們，我們不能允許少數(shù)的叛變者就使得忠誠的將軍們在一個個"retreat", "retreat"…… "retreat",中做決定，而每個忠誠的將軍發(fā)送的明明是"attack"
      • 因此，我們還要為每個i增加如下的需求
    • 2-如果第i個將軍是忠誠的，那么其他的忠誠的將軍必須使用他發(fā)送的值作為v(i)的值
    • 我們可以改寫條件1，使得它是針對任意i的條件(無論第i個將軍是否是忠誠的)：
    • 1’-任意兩個忠誠的將軍使用相同的v(i)值
    • 條件1’和2現(xiàn)在都是針對第i個將軍的值v(i)的了
    • 因此，我們可以只考慮一個將軍如何發(fā)送他的值給其他人
    • 現(xiàn)在我們用一個發(fā)令將軍向它的下屬發(fā)送命令的形式來重新描述這個問題，就得到如下問題：
    • 拜占庭將軍問題
    • 一個發(fā)令將軍向他的n-1個下屬將軍發(fā)送命令，使得：
      • IC1-所有忠誠的下屬都遵守相同的命令
      • IC2-如果發(fā)令將軍是忠誠的，那么每個忠誠的下屬必須遵守他發(fā)出的命令
    • 條件IC1和IC2被稱為交互一致性(interactive consistency)條件
    • 可以看到，當發(fā)令將軍是忠誠的時候，IC1可以由IC2導出
    • 然而，發(fā)令將軍不一定是忠誠的
    • 為了解決最初的問題，第i個將軍只需要利用拜占庭將軍問題的解法發(fā)送命令"使用v(i)作為我的值"，就可以將他的值v(i)發(fā)送給其他的將軍
    • 此時其他的將軍就扮演拜占庭將軍問題中的下屬的角色

• 2-不可能性

• 拜占庭將軍問題看似很簡單
• 它的難解之處是通過一個令人驚訝的事實而體現(xiàn)出來的：
• 如果將軍們只能發(fā)送口頭消息，除非有超過三分之二的將軍是忠誠的，否則該問題無解
• 尤其是，如果只有三個將軍，其中一個是叛變者，那么此時無解
• 口頭消息是指信息的內(nèi)容完全在發(fā)送者控制之下，這樣一個叛變了的發(fā)送者可能會傳送任何可能的消息
• 正常情況下計算機之間傳輸?shù)南⒕蛯儆谶@種類型
• 在第4節(jié)，會考慮帶簽名的書面消息類型，對于這種類型該結論不成立

• 3將軍(1叛徒)問題不存在解/不能達成共識

  • 現(xiàn)在來說明為什么使用口頭消息，當三個將軍中有一個叛變時是無解的
  • 為了簡單起見，我們只考慮是”進攻”還是”撤退”這一簡單的決定的情況

    

  • 首先看圖1里的情形，發(fā)令者是忠誠的并且給下屬 1，2 發(fā)送了一個”進攻”命令
  • 但是下屬2是個叛變者，他對下屬1說，他收到了一個”撤退”命令
  • 如果要保證IC2滿足，下屬1必須遵守命令去進攻
  • 現(xiàn)在考慮圖2所展示的另一種情形，發(fā)令者是一個叛變的將軍，發(fā)送了一個“進攻”命令給下屬1，但是給2發(fā)送的是“撤退”命令

    

  • 下屬 2 轉告下屬 1 說他收到的是“撤退”命令
  • 下屬1，不知道誰是叛變者，同時他也無法判斷發(fā)令者發(fā)送給下屬2的真實的命令到底是什么
  • 因此，這兩幅圖中的情形，對于1來說是完全相同的(他不知道誰是叛變者，兩種情況下他都是只知道發(fā)令者告訴他要進攻，但是2說發(fā)令者說要撤退；所以他無法區(qū)分出這兩種情形，但是如果是情形1，他必須進攻，如果是情形2他如果也進攻，那就是說無論如何他都聽發(fā)令者的命令，如果選定了這1算法，因為1,2本質上是等價的角色，那么2也需要采納該算法(即使下屬 1 告訴他發(fā)令將軍說的是“進攻”，他也必須服從自己收到的命令)，這樣2就會選擇撤退，這就違發(fā)了IC1；如果他要選擇是否撤退，那么意味著他要區(qū)分這兩種情況，但是實際它是無法區(qū)分的，因此無解)
  • 如果叛變者總是在說謊的話，對于1來說就無法區(qū)分這兩種情況，因此他就必須選擇遵守進攻命令，因此無論何時，下屬1從發(fā)令者那收到進攻命令，他都必須遵守它
  • 然而，類似的結論也指出(進攻與撤退不過是兩個稱謂，將2者互換一下就可以得出結論)，如果下屬2從發(fā)令者那收到了撤退命令，他都必須要遵守，即使1告訴他發(fā)令者的命令是進攻
  • 因此對于圖2的情形來說，2必須遵守撤退命令，而1必須遵守進攻命令，因此違法了條件IC1
  • 因此三個將軍中有一個是叛變者時，該問題無解

• 少于3m+1個將軍(有m個叛徒)不存在解/不能達成共識

  • 精確一致性的證明：
  • 利用這個結論，我們可以說明當有m個叛徒，而將軍數(shù)小于3m+1時，該問題無解
  • 證明(反證法)：
    • 將3m將軍m叛徒問題中的將軍稱為阿爾巴尼亞將軍，3將軍1叛徒中的將軍稱為拜占庭將軍，以示區(qū)分
    • 注意此處的拜占庭將軍并不單指叛徒，而是指所有的將軍
    • 拜占庭指揮官代表一個阿爾巴尼亞指揮官和m-1個阿爾巴尼亞中尉，兩個拜占庭中尉分別代表m個阿爾巴尼亞中尉
    • 因此對于拜占庭叛徒將軍(代表m個阿爾巴尼亞將軍)，最多對應m個阿爾巴尼亞叛徒將軍
    • 由IC1可知，m個阿爾巴尼亞中尉(由單個誠實拜占庭中尉所代表)遵循相同的命令，這一命令也是該誠實拜占庭節(jié)點所需要遵守的命令
    • 對于阿爾巴尼亞將軍，可知是滿足IC1和IC2的，又由以上對應關系，可知3將軍問題是滿足IC1和IC2的，也即3將軍問題存在解
    • 這與已知(3將軍(1叛徒)問題不存在解)矛盾，故3m將軍問題不存在解

• 精確一致性與近似一致性是同等困難的

  • 可能有人認為解決拜占庭將軍問題的難點在于它要求達到精確的一致
  • 下面我們通過證明近似一致實際與精確一致一樣困難來說明情況并不是這樣
  • 近似一致性的證明：
  • 我們現(xiàn)在假設不是要達到一個精確的戰(zhàn)斗計劃，將軍們只需要達成近似的進攻時間
  • 詳細來說，我們假設發(fā)令者需要確定進攻時間，同時需要滿足如下兩個條件：
    • IC1’-所有的忠誠的下屬相互之間在10分鐘內(nèi)發(fā)起進攻
    • IC2’-如果發(fā)令將軍是忠誠的，所有的忠誠的下屬在發(fā)令者給定的命令時間點的10分鐘之內(nèi)發(fā)起進攻
  • (我們假設命令是在進攻的前一天下達并被處理的，而且與命令的接收時間無關，只需要關注命令中給定的進攻時間)
  • 類似于拜占庭將軍問題，這個問題只有在超過三分之二的將軍是忠誠的時候才有解
  • 我們通過表明這樣的一個事實來證明它：如果存在這個問題的一個三將軍解，我們可以通過這個解構造出拜占庭將軍問題的一個三將軍解
  • 證明(依舊反證法)：
  • 假設發(fā)令者希望發(fā)送一個進攻或者撤退命令
  • 他會使用假設的那個算法，通過發(fā)送一個在1:00進行攻擊的命令來作為進攻命令，通過發(fā)送在2:00進行攻擊的命令作為撤退命令
  • 每個下屬使用下面的過程來獲取命令：
    • (1)每個下屬根據(jù)收到的攻擊時間而遵循的命令：
      • 時間是1:10以前，則攻擊
      • 時間是1:50之后，則撤退
      • 否則轉向(2)
    • (2)查詢其他下屬做出的“進攻”或“撤退”的命令：
      • 如果其他中尉做出了決定，則該中尉遵循與其他中尉相同的命令
      • 否則，撤退
  • 根據(jù)IC2’如果發(fā)令者是忠誠的，那么一個忠誠的下屬會在第一步里獲取正確的命令，這樣IC2就滿足了
  • 如果發(fā)令者是忠誠的，IC1可以由IC2導出
  • 因此只需要證明當發(fā)令者是叛徒時的IC1成立即可
  • 因為最多有一個叛徒，意味著兩個下屬都是忠誠的
  • 根據(jù)IC1’，如果一個下屬在步驟(1)里決定進攻，那么另一個就不能在步驟(1)決定撤退，因此要么他們在步驟(1)里都達到了相同的決定，要么至少其中一個將其決定推遲到了步驟(2)
  • 為什么會進入步驟2呢？
  • 因為當發(fā)令者是叛徒時，兩個忠誠的下屬達成的時間雖然相差在10分鐘內(nèi)但可能是隨意的，比如可能在1:10-1:50之間，所以最后有可能兩個都沒有在第(1)階段得出決定，而最后都選擇撤退
  • 在這種情況下，很容易看出他們都達到了相同的決定，因此IC1滿足
  • 這樣我們就構造出了對于存在一個叛徒的拜占庭將軍問題的三將軍解，而這是不可能的
  • 同理，拜占庭的3將軍問題不存在解，因此本問題也不存在解
  • 同理對于該近似一致性的3m將軍問題的解與上文所述一致

• 3-使用口頭消息的解

• 前面我們指出，使用口頭消息時對于一個含有m個叛徒的拜占庭將軍問題，至少有3m+1個將軍才可解
• 現(xiàn)在我們給出一個針對3m+1或更多將軍的情況下的解
• 但是，首先我們需要明確“口頭消息”的含義

• “口頭消息”的含義

  • 每個將軍都會執(zhí)行某個算法來把消息傳送給其他將軍，同時我們假設忠誠的將軍會正確地執(zhí)行該算法
  • “口頭消息”可以通過如下我們?yōu)閷④娤⑾到y(tǒng)所做的假設來具體定義：
    • A1-每個發(fā)送的消息都會被正確的傳輸
    • A2-消息的接收者知道發(fā)送者是誰
    • A3-消息如果丟失可以被檢測到
  • 假設A1和A2是防止叛徒介入其他兩個將軍的通信中
  • 根據(jù)A1，他無法妨礙其他兩位將軍發(fā)送的消息
  • 根據(jù)A2，他不能偽造消息來攪亂其他兩位將軍的交流
  • 假設A3是為了防止一個叛徒通過簡單的不發(fā)送消息來阻止一次決定
  • 這些假設在實際中的實現(xiàn)將會在第6節(jié)進行討論

• OM(m)算法的步驟

  • 本節(jié)以及下一節(jié)的算法，要求每個將軍都能夠直接向其他將軍發(fā)送消息
  • 在第5節(jié)我們會描述沒有該條件限制下的算法
  • 一個叛變的發(fā)令者可能會決定不發(fā)送任何命令
  • 由于下屬們必須遵守相同的命令，因此這種情況下他們必須有一個默認的命令
  • 我們使用RETREAT(retreat，撤退)作為該默認命令
  • 我們歸納性的定義該口頭消息(Oral Message簡稱OM)算法OM(m)，m是非負整數(shù)，m為叛徒個數(shù)，通過這個算法，一個發(fā)令者向n-1個下屬發(fā)送命令
  • 可以證明對于3m+1或者更多個將軍時，OM(m)解決了拜占庭將軍問題
  • 用”獲取一個值”來取代”遵守一個命令”這樣的說法在描述該算法時顯得更方便一些
  • 算法中還假設了一個函數(shù) majority(取收到的消息(v1,v2……vn-1)的大多數(shù)(大多數(shù)的確定：眾數(shù)或者中位數(shù)))，當一系列元素(v1,v2…vn-1)中出現(xiàn)次數(shù)占半數(shù)以上的元素為v時，則 majority(v1,v2…vn-1) = v，否則 majority(v1,v2…vn-1) = RETREAT
  • 用發(fā)送/接收某個值來代替發(fā)送/接收命令
  • 算法OM(0)
    • (1)發(fā)令者發(fā)送他的值給每個下屬
    • (2)每個下屬使用他從發(fā)令者那收到的值，如果沒有收到則使用值RETREAT
  • 算法OM(m)m>0
    • (1)發(fā)令者發(fā)送他的值給每個下屬
    • (2)對于任意i，vi代表下屬i從發(fā)令者處收到的值，如果沒有收到則采用RETREAT；下屬i扮演算法OM(m-1)中的發(fā)令者，并采用該算法將值vi發(fā)送給其余的n-2個下屬
    • (3)對于任意i以及任意的j!=i，讓vj代表下屬i在步驟2中(使用算法OM(m-1))從下屬j處收到的值，如果他沒有收到這樣的值，就采用RETREAT；下屬i采用函數(shù)majority(v1,v2…vn-1)的值
  • 算法OM(m)中的 m 指代算法最多可以容許有多少個叛徒
  • 不是要求有 m 個叛徒，或者已知 m 個叛徒
  • OM(0)即為不提防任何叛徒的情況
  • 在 m > 0 的情況下，每個下屬都無法信任任何人，因此對于每個接收到的值，他們都需要使用 majority(v1,v2…vn-1) 確定
  • 在第 m 輪中，發(fā)令將軍給每個下屬都發(fā)送了一個值，但誰都不敢相信這個值
  • 因此每個下屬都給其他 n-2（除消息上游和自己）個下屬發(fā)送自己接收到的信息以幫助他人做決定（叛徒可以發(fā)送任何值，但規(guī)定了遵守此規(guī)則），這就是 m-1 輪
  • 而 m-1 輪收到的值大家又需要其他人的信息做決定，因此又給其他 n-3（除消息上游上上游和自己）個下屬發(fā)送自己的信息幫助他人做決定
  • 以此類推，一直到 OM(0) 為止
  • 上面整個過程是一個遞歸的過程，每個下屬都會給其他下屬發(fā)送很多信息，為了使這些不同信息得以區(qū)分，每個下屬可以在發(fā)送消息時加上自己所屬序號的前綴
  • 示例：
    • 如圖示例：m=1，n=4

      

    • 當一個下屬為叛徒的情況
      • (1)在OM(1)的第一階段，指揮官發(fā)送值v給其余三個下屬
      • (2)第二階段：下屬1用算法OM(0)發(fā)送值v給下屬2，下屬3發(fā)送給下屬2值x
      • (3)在第三步，下屬2此時獲得了兩個v和一個x，因此最終下屬2獲得正確的值為v=majority(v,v,x)，下屬1同理
    • 當指揮官為叛徒的情況

      

      • (1)指揮官發(fā)送值x,y,z給下屬1,2,3
      • (2)~(3)最終每一個下屬都得到majority(x,y,z)，并不能得到統(tǒng)一的解
    • 由以上過程，可知算法是遞歸運行的，從OM(m)到OM(m-1)…OM(0)，OM(m)調(diào)用n-1個OM(m-1)，每個OM(m-1)調(diào)用n-2個OM(m-2)…一直到OM(0)
    • 節(jié)點數(shù)n，叛徒數(shù)m的情況下若叛徒節(jié)點參與通信(發(fā)送錯誤信息)：
      • OM(m-1)被調(diào)用的次數(shù)n-1
      • OM(m-2)被調(diào)用的次數(shù)(n-1)(n-2)
      • OM(m-3)被調(diào)用的次數(shù)(n-1)(n-2)(n-3)
      • OM(m-k)被調(diào)用的次數(shù)(n-1)(n-2)(n-3)..(n-k)
      • 總的次數(shù)：n-1+(n-1)(n-2)+(n-1)(n-2)(n-3)+(n-1)(n-2)(n-3)..(n-k)

• OM(m)算法的正確性推導

  • 為了證明算法OM(m)對于任意m的正確性，我們首先證明如下的輔助定理：
  • 引理1：對任意m,k，若系統(tǒng)中將軍總數(shù)超過2k+m，叛徒最多有k個，算法OM(m)滿足IC2，即如果指揮官誠實，那么每一個誠實的下屬都遵從指揮官的命令
  • 引理1證明：
    • 當m=0時，由A1可知，IC2滿足
    • 當m>0時，在OM(m)算法的step(1)，指揮官把值傳給n-1個下屬，在step(2)中，每一個誠實的下屬調(diào)用OM(m-1)，前文已知n>2k+m，因此n-1>2k+(m-1)，所以每一個誠實的下屬i都會得到城實下屬的vj=v
    • 又因為n-1>2k+(m-1)>=2k，即這n-1個下屬的半數(shù)以上都是誠實的，所以step(3)中獲得的majority(v1,v2……vn-1)必等于v，即滿足IC2
  • 定理1：對任意m，如果將軍數(shù)量大于3m且叛徒數(shù)最多是m，算法OM(m)滿足IC1和IC2
  • 定理1證明：
    • 當不存在叛徒(m=0)的時候，顯然OM(0)滿足IC1&IC2的約束，因此假定OM(m-1)成立，證明OM(m)，m>0成立
    • 假設指揮官誠實，由引理1可知，若k與m相等，則OM(m)滿足IC2，又因為在指揮官誠實的情況下IC1可以由IC2推出，所以只需要證明在指揮官是叛徒的情況下檢驗是否滿足IC1
    • 已知指揮官是叛徒，最多有m個叛徒
    • 所以下屬中最多有m-1個叛徒
    • 下屬的數(shù)量是3m-1，且3m-1>3(m-1)，因此OM(m-1)滿足IC1&IC2
    • 對于每一個j，任意兩個誠實的下屬得到的都是相同的vj的值(這任意兩個下屬有一個是j的話就由IC2可以推出；若不包括j的話，由IC1可以推出)
    • 因此，任意兩個誠實的下屬最終會得到相同的v1,v2……vn-1，也即算法step(3)的majority(v1,v2……vn-1)相同，OM(m)的IC1得以證明
    • 對于證明的思路分析：
    • 采用了歸納演繹法
    • 顯然OM(0)恒成立
    • 假設OM(m-1)成立
      • 若指揮官誠實，那么由引理1可推OM(m)的IC2成立，進而OM(m)IC1成立
      • 若指揮官為叛徒，
        • 通過歸納法證明過程中對任意j由OM(m-1)的IC2推出任意兩個誠實下屬有相同vj的值，
        • 這是因為如果j為兩個誠實下屬之一，那么就符合OM(m-1)的IC2條件；
        • 如果j不是這兩個誠實下屬之一，那么j是誠實將軍自不必多說，
        • 如果j是叛徒的話，因為該任意兩個下屬是誠實的，
        • 由IC1也可推知二者Vj的值也相同，
        • 雖然不是正確值，但達成了共識
        • 因此滿足IC1，即OM(m)滿足IC1&IC2
    • 綜上，定理1成立

• 4-使用簽名消息情況下的解

• 正是叛徒能夠“撒謊”導致拜占庭將軍問題變的難以解決
• 如果可以限制他們的這種能力，那么問題就會變得容易解決了

• “簽名消息”的含義

  • 一種方法是允許將軍發(fā)送不可偽造的簽名消息
  • 更準確的說，是我們給 A1-A3 加上如下的假設：
    • A4
      • (a)一個忠誠的將軍的簽名不可以被偽造，且他簽署的消息的內(nèi)容的任何改動都可以被檢測到
      • (b)任何人都可以驗證某個將軍簽名的真實性
  • 我們不對叛變將軍的簽名做限制
  • 也即我們允許他的簽名被另一個叛徒偽造，從而允許叛徒之間勾結
  • 引入簽名消息后，之前所說的限制就不存在了，對于任意叛徒的任意將軍數(shù)都有可行解

• SM(m)算法的步驟

  • 算法大致流程：
    • 指揮官發(fā)送帶有自己簽名的信息給所有下屬
    • 下屬在指揮官簽名的基礎上附上自己的簽名并發(fā)給其他下屬
    • 其他下屬重復操作
  • 定義choice函數(shù)將一組命令轉變成單個命令：
    • 1-如果集合V由單個元素v組成，choice(V)=v
    • 2-choice(None)=RETREAT
  • choice函數(shù)的定義也可以是中位數(shù)
  • x:i表示被將軍i簽名的信息x，v:j:i表示先被j簽名的信息v，然后又被i簽名的v:j
  • General 0代表指揮官
  • 每一個下屬 i 都維持一個集合Vi，Vi是當前收到的被正確簽名的命令的集合(如果指揮官誠實，那么此集合只有一個元素)
  • 算法SM(m)步驟：
    • 首先將 Vi 集合初始化為空集
    • (1)發(fā)令將軍簽署并發(fā)送他的值給每個下屬
    • (2)對于第 i 個下屬：
      • (A)如果他從發(fā)令將軍處收到了 v:0 形式的消息，且他尚未接收過任何命令，則他將：
        • 1. 設置 Vi 為 {v}
        • 2. 發(fā)送 v:0:i 消息給所有其他下屬
      • (B)如果他收到形如 v:0:j1:…:jk 的消息，并且值 v 不在集合 Vi 中，則他將：
        • 1. 將值 v 添加至 Vi
        • 2. 如果 k < m，將消息 v:0:j1:…:jk:i 發(fā)送至所有序號不是 j1,…,jk 的其他下屬
    • (3)對于第 i 個副將：當他不會再收到任何消息時，通過 choice(Vi) 選擇出命令
  • 在步驟(2)，下屬i會忽略任何已經(jīng)包含在集合 Vi 中的命令v的信息
  • 在步驟(3)如果一個下屬不接受到信息該如何決斷呢？
  • 通過對k進行歸納法，容易得到對于任意的下屬序列 j1,…,jk(k<=m)
  • 一個下屬在步驟(2)能夠最多接收到一次 v:0:j1:…:jk:i 信息，若約束下屬jk，要么發(fā)送該信息(指v:0:j1:…:jk:i)，要么發(fā)送一條消息告訴其他人他不會再發(fā)送此類的消息，這樣我們就可以判斷是否所有消息都已經(jīng)接收（由于 A3 限定，如果一個 jk 叛徒選擇兩種消息都不發(fā)送那也是可以檢測到的）
  • 除此以外，當無信息到達時超時機制也可用于進行決斷(Section 6給出)
  • 步驟(2)中收到簽名的下屬會丟棄具有不正確簽名格式的信息，這是為了節(jié)省存儲空間
  • 因為如果不這么辦的話，當一個命令 v 被 k 個下屬簽名并以消息形式傳遞給其他下屬的時候，系統(tǒng)中就會存在(n?k?2)(n?k?3)...(n?m?2)個拷貝
  • 以n=7,m=2為例：(本文應該是默認叛徒不參與通信(也可能是無法進行通信)或且發(fā)出的信息并不留存)

    

  • 之后所有節(jié)點發(fā)現(xiàn)k=m，轉步驟(3)
  • 下圖 5 展示了算法 SM(1) 在總共 3 個將軍且發(fā)令將軍是叛徒情況下的消息處理流程：

    

  • 發(fā)令將軍發(fā)送"進攻"命令給下屬 1，發(fā)送"撤退"命令給下屬 2
  • 在第 2 步中，他們又把各自命令發(fā)送給對方
  • 因此第 2 步之后 V1 = V2 = {"進攻"，"撤退"}，下屬 1，2 都遵循命令 choice({"進攻"，"撤退"})
  • 這里可以觀察到，不像之前圖 2 中的場景，下屬們可以知道發(fā)令將軍是叛徒，因為他的簽名出現(xiàn)在了兩個不同命令當中，并且A4也能保證其結論的正確性
  • 事實上，第m個將軍并不需要繼續(xù)在命令的后邊附上自己的簽名，因為他收到命令之后就不會再轉發(fā)給別人了；因此SM(1)的簽名是不必要的

• SM(m)算法的正確性推導

  • 定理2：對于任意的m，如果最多有m個叛徒，那么算法SM(m)解決了拜占庭將軍問題
  • 證明：
  • 先證IC2，當指揮官是誠實的情況下，在步驟(1)他會發(fā)送v : 0給他的下屬們，每一個誠實的下屬在步驟(2)(A)都會收到命令v，因為叛徒下屬并不能偽造指揮官簽名，因此在步驟(2)(B)并不能對消息進行篡改，所以誠實的下屬在步驟(2)(B)并不能收到除了v以外的其他命令
  • 這就保證了集合Vi只會有一個命令v，再經(jīng)由步驟(3)的choice函數(shù)，最后每一個下屬的命令都是一樣的，也即滿足IC2
  • 因為在指揮官是誠實的情況下IC1可以由IC2推導出，因此只需要證明指揮官是叛徒的情況下是否符合IC1即可
  • 若兩個下屬i,j最后在步驟3服從相同的命令，那么他們倆在步驟(2)的 Vi , Vj 也是一樣的
  • 因此，證明IC1就是證明
  • 如果i在步驟(2)將v加入到集合Vi，那么j也一定在步驟(2)把v加入到Vj中
  • 如果i在步驟(2)(A)收到了命令v，那么他就會將其在步驟(2)(A)(ii)發(fā)送給j，所以j就會收到這一信息(因為消息的A1約束)
  • 如果i在步驟(2)(B)將命令添加到自身的Vi中，那他一定收到了信息v : 0 : j1 : ... : jk
  • 如果j是其中一個jr那么通過A4約束，他一定已經(jīng)收到了消息v，如果j不在該簽名隊列(j1 : ... : jk)中，分兩種情況：
    • 1. k < m的話，i就會將信息v : 0 : j1 : ... : jk : i發(fā)給j，j同樣會收到命令v
    • 2. k = m的話，除叛徒指揮官之外，n-1個下屬中最多還有m-1個叛徒下屬，因此至少在j1，j2 ... : jm中，至少有一個下屬是誠實的；那么這個誠實的下屬也在他收到消息的第一時間將v發(fā)給j
  • 所以無論如何j還是會收到v
  • 綜上所述，SM(m)算法滿足IC1&IC2，定理2成立

• 5-通信路徑缺失

• 前文所述都是將軍之間可以兩兩直接發(fā)送消息的情況，以下討論移除這一假設，對算法OM(m)和SM(m)進行擴展
• 3-正則圖(3-regular graph)：每一個節(jié)點的度都是3；如下圖所示：

  

• 如果兩個將軍有邊相連，那么稱這兩個將軍為鄰居
• 定義1：
  • (a)節(jié)點i的鄰居正則集合(regular set of neighbors)是滿足以下條件的點集i1 , ..., ip
    • (i)每個元素都是節(jié)點i的鄰居
    • (ii)對于每一個不同于i的將軍k，存在至少兩條從ij到k的不經(jīng)過i且只有終點k重合的路徑
  • (b)如果圖G的每一個點都有一個由p個點構成的regular set of neighbors，那么圖G被稱為p-正則圖(p-regular)
• 圖6就是一個3?regular，圖7就不是，因為中心點沒有有3個點的regular set of neighbors

• 對OM(m)的改進OM(m,p)

• 前提：需要將軍(包括叛徒將軍)之間的能夠發(fā)送消息的圖是一個3m?regular
• 對所有的正數(shù)m,p，如果圖G是一個p?regular，定義算法OM(m,p)如下所示：
  • (0)選擇指揮官的由p個下屬組成的正則鄰居集合N
  • (1)指揮官將其值發(fā)給N中的每一個下屬
  • (2)對N中的每一個下屬i，以Vi代表i收到的值，或RETREAT代表未收到任何值；下屬i按照如下方式將Vi發(fā)給其他下屬k：
    • (A)如果m=1，那么沿著路徑Pi,k發(fā)送，該路徑的存在是由定義1的條件(ii)保證的
    • (B)如果m>1，那么他就作為算法OM(m-1,p-1)中的發(fā)令者，同時此時的將軍圖是通過將原始的發(fā)令者從圖G中刪除得到的
  • (3)對于任意的k，及N(N={i1,…,ip})中的任意不等于k的i，讓vi代表下屬k在步驟(2)中從下屬i處收到的值，如果沒有收到值令其等于RETREAT；下屬k使用值majority(vi1,…,vip)
• 注意：從p-regular圖中刪除一個節(jié)點后可以得到一個(p-1)-regular圖；因此，可以在步驟(2)中應用算法OM(m-1,p-1)
• 現(xiàn)在我們證明如果最多有m個叛徒，那么OM(m,3m)解決了拜占庭將軍問題
• 該證明類似于算法OM(m)的證明，因此我們只是簡單的描述下
• 首先從引理1的一個擴展開始：
• 引理2：對于任意的m>0及任意的p>=2k+m，如果最多有k個叛徒，算法OM(m,p)滿足條件IC2
  • 證明：對于m=1，可以看出每個下屬會得到majority(v1,…,vp)的值，其中的每個值vi是發(fā)令者通過一條與發(fā)送給他的其他值的發(fā)送路徑不相交的一條路徑發(fā)送的(此處的發(fā)令者是指步驟(2)中的N中的某個將軍，并不是特指(1)中的那個原始的發(fā)令者)
  • 由于最多有k個叛徒而且p>=2k+1，因此超過一半的路徑都是完全由忠誠的下屬組成的(總共有p條路徑，只有k個叛徒，p>=2k+1，即使一條路徑上只有一個叛徒，那么最多有k條路徑上有叛徒)
  • 因此，如果發(fā)令者是誠實的，那么有一半以上的vi值都是他發(fā)送的那個值，這樣就保證滿足了IC2
  • 現(xiàn)在假設對于m-1，m>1 引理2成立
  • 如果發(fā)令者是忠誠的，那么N中的P個下屬都會得到正確的值
  • 因為p>2k，因此他們中大多數(shù)都是忠誠的，根據(jù)歸納假設，他們中的每個人都會給每個誠實的下屬發(fā)送正確的值
  • 因此，每個忠誠的下屬，會收到半數(shù)以上的正確值，因此在步驟(3)他們會得到正確的值
• 定理3：對于任意的m>0及任意的p>=3m，如果最多有m個叛徒，那么算法OM(m,p)解決了拜占庭將軍問題
  • 證明：根據(jù)引理2令k=m，我們可以得到OM(m,p)滿足IC2
  • 如果發(fā)令者是誠實的，那么IC1可以由IC2導出，因此我們只需要證明發(fā)令者是叛徒的情況下的IC1即可
  • 為此，我們需要證明在步驟(3)，每個忠誠的下屬得到相同的vi值的集合
  • 如果m=1，很明顯成立(此時只有一個叛徒，而且他是發(fā)令者)
  • 因為所有的下屬包括N中的那些，都是誠實的，并且路徑Pi,k不經(jīng)過發(fā)令者
  • 如果m>1，可以使用一個歸納法證明，因為p>=3m，得出p-1>=3(m-1)
  • 我們關于算法OM(m)的擴展要求圖G是一個3m-regular圖，是一個相對比較強的聯(lián)通性假設
  • 實際上，如果僅有3m+1個將軍，3m-regularity實際上就是全互聯(lián)，而算法OM(m,3m)實際上也變成了OM(m)算法
  • 與此相比，算法SM(m)很容易擴展到可能的最弱的連通性假設
  • 首先，我們來看保證拜占庭將軍可解需要何種程度的連通性
  • IC2要求一個忠誠的下屬遵從忠誠的發(fā)令者，很明顯如果發(fā)令者無法與該下屬通信是不可能達到的
  • 尤其是如果發(fā)令者發(fā)到該下屬的消息都要經(jīng)過一些叛徒轉發(fā)，那么就沒有方法保證該下屬可以得到發(fā)令者的命令
  • 類似的，如果兩個下屬之間只能通過一些叛變的中間者進行通信，他們條件IC1也無法滿足
  • 因此對于拜占庭將軍問題可解的最弱的連通性假設就是：由忠誠的將軍們組成的子圖是連通的
  • 可以證明，在該假設下，算法SM(n-2)是一個可行解，此處n代表將軍的個數(shù)-無論有多少個叛徒
  • 當然，我們必須要修改該算法，使得他只能向那些可以通信的對象發(fā)送消息
  • 詳細來說，就是在步驟(1)，發(fā)令者只能向他的鄰居下屬發(fā)送消息，在步驟(2)(B)，只能向那些不在jr中的鄰居下屬發(fā)送信息
  • 下面我們來證明一個更一般的結論，首先需要知道圖的直徑是指圖中任意兩節(jié)點間的最短路徑的長度的最大值
• 定理4：對于任意的m和d，如果最多有m個叛徒及忠誠的將軍組成的子圖的直徑為d，那么算法SM(m+d-1)(加入了上面的改動后的算法)可以解決拜占庭將軍問題
  • 證明：證明過程很類似于定理2
  • 首先證明IC2，根據(jù)假設，從忠誠的發(fā)令者與一個下屬i之間存在一條路徑，該路徑只是經(jīng)過d-1個或者更少的忠誠下屬
  • 這些下屬在命令到達i之前，可以正確的轉發(fā)它，如前面所述，假設A4可以防止一個叛徒偽造一個不同的命令
  • 為了證明IC1，我們假設發(fā)令者是個叛徒，接下來需要說明，一個忠誠下屬收到的任何命令，另一個忠誠的下屬j也都能收到
  • 假設i收到了一個未被j簽名的消息v:0:j1:…:jk
  • 如果k<m，那么i會在接下來的d-1步內(nèi)把該消息轉發(fā)給j
  • 如果k>=m，那么之前的m個簽名者中至少有一個是忠誠的，而且他一定已經(jīng)將給命令發(fā)送給了他所有的鄰居，這樣它會被忠誠的下屬們繼續(xù)轉發(fā)，也會在接下來的d-1步內(nèi)j就會收到該消息
• 推論：如果忠誠的將軍的圖是連通的，那么SM(n-2)(同時是改寫后的算法)解決了n個將軍情況下的拜占庭將軍問題
  • 證明：讓d代表忠誠的將軍的圖的直徑；由于一個連通圖的直徑肯定小于節(jié)點總數(shù)，同時忠誠將軍的個數(shù)肯定大于d，反過來叛徒的個數(shù)肯定小于n-d；令m=n-d-1代入定理4，得到SM(n-d-1+d-1)即SM(n-2)
  • 定理4假設忠誠的將軍組成的圖是連通的；即使該條件不成立，上面的證明可以很容易擴展而得到如下的結論：
  • 當最多有m個叛徒的時候，算法SM(m+d-1)有如下屬性：
  • 1-圖中由最多d個忠誠下屬連接的任意兩個忠誠下屬會遵守相同的命令
  • 2-如果發(fā)令者是忠誠的，那么與發(fā)令者之間存在一條由最多m+d個忠誠下屬組成的路徑的忠誠下屬將會遵守發(fā)令者的命令

• 6-可靠性系統(tǒng)

• 可靠性系統(tǒng)的要素

  • 除了在內(nèi)部使用可靠性電路組件外，我們所知的實現(xiàn)可靠計算機系統(tǒng)的唯一方式就是使用幾個不同的處理器來計算相同的結果，然后在它們的輸出結果上執(zhí)行多數(shù)決的投票來確定一個值(投票可能是在系統(tǒng)內(nèi)部進行的，也可能是該輸出的用戶在外部進行的)
  • 無論是在實現(xiàn)可靠計算機中通過冗余電路來避免獨立芯片的失敗，還是在彈道導彈防御系統(tǒng)中使用冗余計算站點來避免核攻擊中的網(wǎng)點破壞，都是如此
  • 唯一的區(qū)別就是被備份的處理單元的大小規(guī)模
  • 多數(shù)決的投票的使用基于這樣的一個假設：所有的正常的處理單元應該產(chǎn)生相同的輸出結果
  • 當它們都使用相同的輸入時，這是正確的
  • 然而，一個輸入數(shù)據(jù)來自一個獨立的物理單元，比如來自可靠計算機系統(tǒng)的其他電路單元，或者來自于導彈防御系統(tǒng)中的一個雷達站，一個故障組件也可能會為不同的處理單元提供不同的值
  • 更進一步的，從同一個輸入單元獲取輸入的不同的處理單元也可能獲得不同的輸入，因為在他們讀取時輸入值可能是不斷變化的
  • 比如，兩個處理器去讀取一個在運行的時鐘，一個可能讀取到老的時間，一個可能讀到新的，只能通過對該時鐘的讀取進行同步才能防止這種情況
  • 為了讓基于多數(shù)決的投票可以構建可靠性的系統(tǒng)，需要滿足如下兩個條件：
  • 一致性(Safety)、可用性(Liveness)(分別對應下列1,2)
  • 1-所有的正常處理單元必須使用相同的輸入值(這樣他們才會產(chǎn)生相同的輸出)
  • 2-如果輸入單元是正常的，那么每個正常的進程都應該使用它提供的值作為輸入(這樣他們才能產(chǎn)生正確的結果)
  • 這正是我們的交互一致性條件IC1和IC2，至少發(fā)令者變成了輸入產(chǎn)生單元，下屬變成了處理單元，忠誠意味著正常(nonfaulty)
  • 為這樣的問題提供一個硬件級的解決方案看起來是很吸引人的
  • 比如，有人認為可以通過讓所有的處理單元從同一條線路上讀取輸入來保證它們可以獲取相同的值
  • 但是，一個出錯的處理單元可能會在線路上發(fā)送邊緣信號—這種信號某些處理器可能作為0處理，但是其他的可能作為1處理
  • 因此不存在一種方法可以保證不同的處理器會從可能出錯的輸入單元上獲取相同的值，除非讓處理器相互之間可以通信來解決拜占庭將軍問題
  • 當然一個出錯的輸入單元可能會提供無意義的輸入值
  • 拜占庭將軍解決方案可以做的就是保證所有的處理單元可以使用相同的輸入值
  • 如果輸入是一個很重要的部分，那么應該有多個獨立的輸入單元提供冗余值
  • 比如在一個導彈防御體系中，除了有冗余的處理站點外，還應該具有冗余的雷達
  • 然而，輸入的冗余無法達到可靠性
  • 仍然有必要保證正常的處理單元可以通過使用冗余數(shù)據(jù)產(chǎn)生相同的輸出
  • 對于輸入設備是正常的但是由于讀取時它的值仍在變化的情況，我們?nèi)匀幌Ｍ切┱５奶幚韱卧梢垣@取合理的輸入值
  • 可以看到，如果函數(shù)majority和choice被設定為中位數(shù)函數(shù)，那么我們的算法會具有如下的屬性：
  • 正常的處理單元得到的值將落在輸入單元提供的值的邊界之內(nèi)
  • 因此只要輸入單元提供一個合理的值的邊界，那么正常的處理單元將會得到一個合理的值

• 消息傳遞系統(tǒng)的約束

• 前面我們已經(jīng)給出了幾個解(指之前的幾個OM，SM算法)，但是他們都是從拜占庭將軍問題的角度來描述，而不是采用計算機系統(tǒng)的用語
• 現(xiàn)在我們來看，這些解如何應用到可靠的計算機系統(tǒng)
• 毫無疑問，一個將軍的算法可以在一個處理單元上實現(xiàn)
• 問題取決于實現(xiàn)一個滿足假設A1-A3的消息傳遞系統(tǒng)(對于算法SM(m)來說，就是假設A1-A4)
• 下面，我們逐個分析這些假設：
• A1-每一個正常節(jié)點發(fā)出的信息都被正確的送達
  • 在現(xiàn)實系統(tǒng)中，通信線路可能出錯
  • 對于算法OM(m)和OM(m,p)，連接兩個處理單元間的通信線路出錯無法與其中的一個處理單元出錯區(qū)分出來
  • 因此，我們僅能保證這些算法在出現(xiàn)m個失敗時可以工作，可能是處理器也可能是通信線路出錯了(當然，連接到相同處理器上的通信線路錯誤等價于那個處理器的失敗)
  • 如果我們假設通信線路錯誤不會導致簽名信息的偽造(下面可以發(fā)現(xiàn)該假設十分合理)，那么我們的簽名信息算法SM(m)就不會受到通信線路錯誤的影響
  • 更準確的說，即使出現(xiàn)通信線路錯誤，定理4依然合法
  • 這樣一個通信線路錯誤與簡單的移除該通信線路具有相同的影響---只是降低了圖的連通性
• A2-信息接收者知道信息的發(fā)送者
  • 這條實際上主要是要求一個出錯的處理單元不能偽裝成一個正常的
  • 在實際中，這意味著進程間的通信必須是通過固定線路而不是通過某些消息傳遞交換網(wǎng)絡(如果使用的是交換網(wǎng)絡，那么必須考慮網(wǎng)絡節(jié)點的失效，拜占庭將軍問題再次出現(xiàn))
  • 注意如果條件A4滿足，同時所有的消息都是簽名的，那么A2就不是必要的
  • 因為進程的不可模仿性通過消息的簽名就可以達到
• A3-信息缺失能夠被檢測到
  • 消息的缺席只能通過在固定時長內(nèi)沒有到達來檢測，換句話說，需要通過使用某些超時約定
  • 使用超時機制來達到條件A3，需要如下2個假設：
  • 1-消息的產(chǎn)生和傳輸所需的時間有一個固定的最大時長
  • 2-發(fā)送者與接收者有一個固定誤差的同步時鐘(類似于時間相差±20ms)
  • 第一個假設的必要性是很明顯的，因為接收者必須知道他需要花多長時間等待消息的到達
  • 第二個假設的必要性很不明顯；然而可以證明，如果要解決拜占庭將軍問題，需要該假設或者是等價于它的某個假設；更準確的說，假設有一個算法，在該算法中，將軍們只能在如下的情形下采取行動：
    • 1-在某個固定的初始時間(對于所有的將軍來說該值相同)
    • 2-收到消息的時候
    • 3-當一個隨機選擇的時長過后(比如一個將軍可以將計時器設定為一個隨機值，在時間到時才能繼續(xù)行動)
  • (上面代表了我們能想象出來的不需要構建同步時鐘的最通常的一類算法)
  • 可以證明，如果消息可能以任意快的速率傳輸即使存在一個上界，那么不存在解決拜占庭將軍問題的此類算法
  • 甚至即使我們限制叛徒的錯誤行為只是無法發(fā)送消息，這種情況下依然是無解的
  • 該結論的證明超過了本篇文章的內(nèi)容
  • 需要注意的是，如果對傳輸延時上除了上界限制之外，再添加一個下界限制就允許處理單元通過來回的傳遞消息來實現(xiàn)時鐘
  • 上面的兩個假設，使得檢測未發(fā)送的消息變得很簡單
  • 令u代表最大的消息生成和傳輸延時，假設正常處理單元在任何時刻的時鐘誤差最大為t
  • 這樣如果一個正常處理單元在他的時鐘時間T生成的任何消息，消息會在接收者的時鐘時間T+u+t內(nèi)到達
  • 因此，如果接收者在那時還未收到該消息，那么它就認為發(fā)送者沒有發(fā)送該消息(如果它在之后到達，那么發(fā)送者一定出錯了，因此算法的正確性不能依賴于正在發(fā)送的消息)
  • 通過固定輸入處理單元發(fā)送值的時間，處理單元就可以確定等待應該等待消息到何時
  • 比如，在算法SM(m)中，一個處理單元對于任何具有k個簽名的消息必須等待到時間T0+k(u+t)，T0代表該處理單元在發(fā)令者開始執(zhí)行算法時的它自己的時鐘時間
  • 沒有任何兩個時鐘具有相同的速率，因此無論處理單元間的時鐘一開始無論同步的多么精確，最后他們都會相差很大，除非會周期性的進行重新的同步
  • 因此現(xiàn)在我們需要解決讓處理單元時鐘同步在一定偏差之內(nèi)，即使有的處理單元是出錯的
  • 該問題本身是一個與拜占庭將軍問題難度相當?shù)膯栴}
  • 時鐘同步問題的解與拜占庭將軍問題的解聯(lián)系緊密，我們會在未來的文章中進行描述
• A4-簽名不可篡改及可驗證性
  • 假設進程i從數(shù)據(jù)M生成的簽名為Si(M)
  • 那么一個經(jīng)簽名的信息就由一個(M,Si(M))對組成
  • 為了滿足A4的(a)(b)兩個要求，函數(shù)Si必須具有如下兩個屬性：
  • (a)如果處理單元i是正常的，那么任何出錯單元都不能生成Si(M)
  • (b)給定M和X，任何進程都可以確定X是否等于Si(M)
  • 屬性(a)不可能絕對滿足，因為Si(M)僅僅是一個數(shù)據(jù)項，一個出錯的處理單元可能生成任意的數(shù)據(jù)項(這意味著它也可能剛好生成Si(M))
  • 但是我們可以讓這種出錯情況的概率盡可能的小，從而也可以讓系統(tǒng)盡可能的穩(wěn)定
  • 如何做到這點依賴于我們期望碰到的出錯類型；比如如下兩種情況：
  • 1-隨機故障
    • 令Si為一個合適的隨機化函數(shù)，我們可以讓一個出現(xiàn)隨機故障的處理單元生成一個正確的簽名的概率等價于通過隨機選擇函數(shù)來完成這件事的概率，即可能的簽名的數(shù)目的倒數(shù)
    • 下面介紹可以達到該目的的一種方法
    • 假設消息被編碼成小于P的正整數(shù)，P是2的冪(實際上消息本質上也是二進制01碼，因此只需要保證其長度小于P的長度即可)
    • 令Si(M)=(M*Ki)mod Pi，Ki是一個隨機選擇的小于P的奇數(shù)
    • 令Ki^-1為滿足Ki* Ki^-1=1 mod P的唯一一個數(shù)，一個處理單元可以通過測試M是否等于(X* Ki^-1)mod P來測試X是否等于Si(M)
    • 如果一個處理單元的內(nèi)存中沒有值Ki，那么它為一個消息M生成正確的簽名M*Ki的概率是1/P：這也是通過隨機選擇來生成的概率(如果處理單元能通過某種過程獲得Ki，那么出錯的處理器j在計算Sj(M)的時候就有更大的概率可能將Sj替換為Si來偽造i的簽名)(所以這樣看來其實該機制也類似于公鑰簽名機制，(Ki,P)可以看做私鑰，而(Ki^-1,P)則可以看做公鑰
    • 可能還有一個問題是Ki可以很容易通過(Ki^-1,P)求出來，當然這也是與公鑰機制的區(qū)別
    • 但是這不影響對問題的解決，因為該假設是假設錯誤是隨機的，如果利用(Ki^-1,P)計算Ki再去偽造應該算是惡意攻擊了，就是下面這個假設的范疇了
  • 2-惡意攻擊
    • 如果出錯的處理單元是由惡意攻擊導致---比如一個正常的處理單元可能正被一個企圖破壞整個系統(tǒng)的人操縱
    • 那么簽名函數(shù)Si的構建就變成了一個密碼學問題
    • 需要注意的是如果處理單元已經(jīng)看到過消息M的簽名，那么下次它就很容易生成Si(M)
    • 因此需要保證不能重復對相同的消息簽名
    • 這就意味著，使用SM(m)算法重復的發(fā)送一系列值的時候，需要給這些值增加一個序列號來保證它們的唯一性(之所以要加入序列號，是因為如果不加下屬們就很容易偽造簽名，比如他收到了一個(M,S1(M),S2(M)…Sk(M))消息，同時之前也收到過值為M’的消息，同時由于不斷的發(fā)送，他可能已經(jīng)收到過針對M’的所有簽名，這樣他就可以把(M,S1(M),S2(M)…Sk(M))修改成(M’,S1(M’),S2(M’)…Sk(M’))，這樣就達到了偽造的目的：他修改了M的值，但是將軍們的簽名還都正確；所以需要加入序列號以提供保證，使得將軍們不會再次發(fā)出相同的消息值，也就沒法利用之前收到的消息進行偽造)
    • 最后看下如何通過上面的方法來保證A4假設呢？
    • 首先假設A4如何保證消息不被偽造，先看下屬在偽造一個消息時需要做哪些事情：
    • 根據(jù)前面，我們知道每個下屬收到的是形如(M,S1(M),S2(M)…Sk(M))的消息，他如果要修改該消息，首先要修改M的內(nèi)容，然后再修改簽名1到k
    • 但是根據(jù)假設它實際上無法修改經(jīng)過忠誠者簽名的那些消息，根據(jù)上面的方法，每個下屬接受到消息后只需要去驗證M是否等于(Si(M)* (Ki^-1))mod P，即可驗證簽名的真?zhèn)?#xff0c;所以只要保證忠誠的將軍的Ki不被泄露即可
    • 另一方面對于叛變的將軍，并沒有任何的限制，比如叛變的將軍可能會告訴另一個將軍自己的私鑰(Ki,P)這樣他的簽名就可以被偽造了，但是忠誠的將軍不會這么做，所以他的簽名就能保證不可偽造，但該假設并沒有對叛變的將軍做出這種保證，也就是說這種簽名存在的情況下，叛變的將軍們依然可以相互勾結去偽造出發(fā)令者的命令

• 7-小結

• 我們已經(jīng)提出了拜占庭將軍問題在不同假設下的幾個解，也說明了如何將它們用于實現(xiàn)可靠的計算機系統(tǒng)
• 這些解，都需要昂貴的時間和消息傳遞開銷
• 算法OM(m)和SM(m)的消息的傳遞路徑長度都達到了m+1
• 換句話說，每個下屬都可能要等著消息從發(fā)令者處發(fā)出后經(jīng)過m個其他個下屬后才能到達它這
• 對于一個不是全互聯(lián)的圖來說，在算法中，消息傳遞路徑的長度還會達到m+d，d代表忠誠的將軍組成的子圖的直徑
• 算法OM(m)和SM(m)會發(fā)送多達(n-1)(n-2)…(n-m-1)個消息
• 可以通過將消息合并來減少需要傳輸?shù)南?shù)
• 同時減少需要傳輸?shù)男畔?shù)量也是有可能的，但是消息數(shù)量的壓縮雖有可能但是有待進一步研究
• 不管怎樣仍然有大量的消息需要傳輸
• 隨機故障下的可靠性是一個難題且其解決方法是很昂貴的
• 降低這種開銷的唯一方法就是限定可能出現(xiàn)的錯誤類型
• 比如，經(jīng)常假設計算機可能會沒有響應，但是不會返回錯誤的響應；然而當需要高度的可靠性時，是不應該做出這樣的假設的，此時拜占庭將軍問題的所有開銷就是不可避免的(比如說人們經(jīng)常假定計算機無法響應但是永遠無法返回錯誤的響應，而這種假設在拜占庭將軍問題中并不能行)

• 8-參考文獻

• My Writings --- Leslie Lamport