目錄

0-前言

1-導(dǎo)引

2-不可能性

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

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

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

3-使用口頭消息的解

“口頭消息”的含義

OM(m)算法的步驟

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

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

“簽名消息”的含義

SM(m)算法的步驟

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

5-通信路徑缺失

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

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

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

7-小結(jié)

8-參考文獻(xiàn)

---

• 0-前言

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

• 1-導(dǎo)引

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

• 2-不可能性

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

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

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

    

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

    

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

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

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

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

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

• 3-使用口頭消息的解

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

• “口頭消息”的含義

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

• OM(m)算法的步驟

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

      

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

      

      • (1)指揮官發(fā)送值x,y,z給下屬1,2,3
      • (2)~(3)最終每一個(gè)下屬都得到majority(x,y,z)，并不能得到統(tǒng)一的解
    • 由以上過程，可知算法是遞歸運(yùn)行的，從OM(m)到OM(m-1)…OM(0)，OM(m)調(diào)用n-1個(gè)OM(m-1)，每個(gè)OM(m-1)調(diào)用n-2個(gè)OM(m-2)…一直到OM(0)
    • 節(jié)點(diǎn)數(shù)n，叛徒數(shù)m的情況下若叛徒節(jié)點(diǎn)參與通信(發(fā)送錯(cuò)誤信息)：
      • 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)算法的正確性推導(dǎo)

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

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

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

• “簽名消息”的含義

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

• SM(m)算法的步驟

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

    

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

    

  • 發(fā)令將軍發(fā)送"進(jìn)攻"命令給下屬 1，發(fā)送"撤退"命令給下屬 2
  • 在第 2 步中，他們又把各自命令發(fā)送給對(duì)方
  • 因此第 2 步之后 V1 = V2 = {"進(jìn)攻"，"撤退"}，下屬 1，2 都遵循命令 choice({"進(jìn)攻"，"撤退"})
  • 這里可以觀察到，不像之前圖 2 中的場(chǎng)景，下屬們可以知道發(fā)令將軍是叛徒，因?yàn)樗暮灻霈F(xiàn)在了兩個(gè)不同命令當(dāng)中，并且A4也能保證其結(jié)論的正確性
  • 事實(shí)上，第m個(gè)將軍并不需要繼續(xù)在命令的后邊附上自己的簽名，因?yàn)樗盏矫钪缶筒粫?huì)再轉(zhuǎn)發(fā)給別人了；因此SM(1)的簽名是不必要的

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

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

• 5-通信路徑缺失

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

  

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

• 對(duì)OM(m)的改進(jìn)OM(m,p)

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

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

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

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

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

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

• 7-小結(jié)

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

• 8-參考文獻(xiàn)

• My Writings --- Leslie Lamport