評論(0

拜占庭將軍問題

標籤: 暫無標籤

拜占庭將軍問題(Byzantine failures)又稱兩軍問題,是由萊斯利·蘭伯特提出的點對點通信中的基本問題。

1 拜占庭將軍問題 -起源

  拜占庭位於現在土耳其的伊斯坦布爾,是東羅馬帝國的首都。由於當時拜占庭羅馬帝國國土遼闊,為了防禦目的,因此每個軍隊都分隔很遠,將軍與將軍之間只能靠信差傳消息。 在戰爭的時候,拜占庭軍隊內所有將軍和副官必需達成一致的共識,決定是否有贏的機會才去攻打敵人的陣營。但是,在軍隊內有可能存有叛徒和敵軍的間諜,左右將軍們的決定又擾亂整體軍隊的秩序。在進行共識時,結果並不代表大多數人的意見。這時候,在已知有成員謀反的情況下,其餘忠誠的將軍在不受叛徒的影響下如何達成一致的協議,拜占庭問題就此形成。

2 拜占庭將軍問題 -拜占庭將軍問題

  拜占庭將軍問題是一個協議問題,拜占庭帝國軍隊的將軍們必須全體一致的決定是否攻擊某一支敵軍。問題是這些將軍在地理上是分隔開來的,並且將軍中存在叛徒。叛徒可以任意行動以達到以下目標:欺騙某些將軍採取進攻行動;促成一個不是所有將軍都同意的決定,如當將軍們不希望進攻時促成進攻行動;或者迷惑某些將軍,使他們無法做出決定。如果叛徒達到了這些目的之一,則任何攻擊行動的結果都是註定要失敗的,只有完全達成一致的努力才能獲得勝利。
  拜占庭假設是對現實世界的模型化,由於硬體錯誤、網路擁塞或斷開以及遭到惡意攻擊,計算機和網路可能出現不可預料的行為。拜占庭容錯協議必須處理這些失效,並且這些協議還要滿足所要解決的問題要求的規範。這些演算法通常以其彈性t作為特徵,t表示演算法可以應付的錯誤進程數。
  很多經典演算法問題只有在t

3 拜占庭將軍問題 -拜占庭失效

  所謂拜占庭失效指一方向另一方發送消息,另一方沒有收到,發送方也無法確認消息確實丟失的情形。
  在容錯的分散式計算中,拜占庭失效可以是分散式系統中演算法執行過程中的任意一個錯誤。這些錯誤被統稱為「崩潰失效」和「發送與遺漏是失效」。當拜占庭失效發生時,系統可能會做出任何不可預料的反應。
  這些任意的失效可以粗略地分成以下幾類:
  進行演算法的另一步時失效,即崩潰失效;
  無法正確執行演算法的一個步驟;
  執行了任意一個非演算法指定的步驟
  各個步驟由各進程執行,演算法就是由這些進程執行的。一個錯誤的進程是在某個點出現了上述情況的進程。沒有出現錯誤的進程是正確的進程。

4 拜占庭將軍問題 -拜占庭將軍問題的兩種解決演算法

  拜占庭問題的最初描述是:n 個將軍被分隔在不同的地方,忠誠的將軍希望通過某種協議達成某個命令的一致(比如一起進攻或者一起後退)。但其中一些背叛的將軍會通過發送錯誤的消息阻撓忠誠的將軍達成命令上的一致。Lamport 證明了在將軍總數大於3m ,背叛者為m 或者更少時,忠誠的將軍可以達成命令上的一致。
  為了保證上面的需求,必須滿足下面兩個條件:
  1. 每兩個忠誠的將軍必須收到相同的值 v(i)(v(i)是第i 個將軍的命令)
  2. 如果第i 個將軍是忠誠的,那麼他發送的命令和每個忠誠將軍收到的v(i)相同
  為了簡化以上模型,我們使用一個將軍發送命令給多個副官的形式來證明,發送命令的將軍稱為發令者,接收命令的將軍為副官,那麼上面的兩個條件可以表述為:
  IC1. 所有忠誠的副官遵守相同的命令
  IC2. 如果發出命令的將軍是忠誠的,那麼所有忠誠的副官遵守司令(發出命令的將軍)的命令
  特別提示:發送命令的每次只有一個將軍,將其命令發送給n-1 個副官。m 代表叛國者的個數,因為將軍總數為n,所以副官總數為n-1 個。IC2 中副官遵守實際上是指忠誠的將軍能夠正確收到忠誠將軍的命令消息。 通過口頭消息

  通過口頭消息傳遞達到一致,如果有m 個叛國將軍,則將軍們的總數必須為3m+1 個以上。下面是口頭消息傳遞過程中默認的一些條件:
  A1. 每個被發送的消息都能夠被正確的投遞
  A2. 信息接收者知道是誰發送的消息
  A3. 能夠知道缺少的消息
  A1 和A2 假設了兩個將軍之間通信沒有干擾,既不會有背叛者阻礙消息的發送(截斷)也不會有背叛者偽造消息的情況(偽造)。即是每個將軍都可以無誤地將自己的消息發送給其他每個將軍。(下一節中可以不需要這個必要條件)
  我們定義口頭消息演算法OM(m) 。對於所有的非負整數m ,每個發令者通過OM(M) 演算法發送命令給n-1 個副官。下面將說明OM(m) 演算法在最多有m 個背叛者且總將軍數為3m+1 或者更多的情況下可以解決拜占庭將軍問題。(考慮到網路應用實際環境,原文使用了收到值代替收到命令,本文不做修改)
  演算法定義一個函數:majority(com1,com2,…,comn)等於多數派命令。
  OM(0)演算法
  (1)發令者將他的命令發送給每個副官。
  (2)每個副官採用他從發令者發來的命令,或者默認使用撤退命令,如果沒有收到任何命令。
  OM(m)演算法
  (1)發令者將他的命令發送給每個副官。
  (2)對於每個i ,vi 是每個副官i 從發令者收到的命令,如果沒有收到命令則為撤退命令。副官i 在OM(m-1) 中作為發令者將vi 發送給另外n-2 個副官。
  (3)對於每個i,並且j\neq i,vj 是副官i 從第(2)步中的副官j 發送過來的命令(使用OM(m-1) 演算法),如果沒有收到第(2)步中的副官j 的命令則默認為撤退命令。最後副官i 使用majority(v1,…,vn-1)得到命令。
  接下來實際的考慮一個n=4,m=1 的情況:
  1. 當副官3 是背叛者,以副官2 為例
  第一步發令者執行演算法OM(1)將自己的命令發送給三個副官,三個副官都正確地收到了命令。
  
拜占庭將軍問題

  第二步每個收到命令的副官都作為發令者執行演算法OM(0),將自己的命令轉發給其餘副官,因為副官3是背叛者,所以他給副官2 傳遞的消息會是假消息。副官2 最後根據majority 函數來決定命令。
  
拜占庭將軍問題

  這樣背叛的副官3 同理也干擾不了忠誠的副官1 和發令者的決定。下面看看如果發令者是背叛者。
  2. 發令者是背叛者,其餘副官為忠誠的
  第一步:發令者向副官發送了不同的命令,實際情況中是一個攻擊者向不同方發送了不同的值進行欺騙。
  
拜占庭將軍問題

  第二步:副官收到命令后,搖身一變為發令者執行OM(0) 向所有的副官發送命令,這樣所有副官的到命令會都相同( ),這樣所有命令都達不到大部分。
  
拜占庭將軍問題

  文章接著就證明了OM(m) 演算法對任意m 都是可以滿足,首先引入一個引理(歸納法證明):
  引理1:對於任意m 和k ,如果有超過2k+m 個將軍和最多k 個背叛者,那麼演算法OM(m) 滿足IC2 (回顧下IC2 指的是,如果將軍是忠誠的,所有的副官遵守將軍命令)。
  證明:當m=0 的時候,OM(0) 在將軍是忠誠的時候滿足IC2。當m>0 時,首先將軍將命令傳遞給 n-1 個副官,然後每個副官對n-1 個將軍執行OM(m-1) 演算法。因為假設了n>2k+m(引理中有將軍數大於2k+m),所以 n-1 > 2k+(m-1) >= 2k(即每一輪中副官總數不小於背叛者的兩倍),這樣每輪OM(m-k) 演算法中忠誠的副官收到的命令都是majority(v1,v2,...,v(n-1)),其中忠誠副官發送的命令大於或者等於一半。
  接著解決拜占庭將軍問題。
  定理1:對於任意m,如果有超過3m 個將軍和最多m 個背叛者,演算法OM(m) 滿足條件IC1 和條件IC2。
  證明:通過m 的歸納法證明,我們通過假設OM(m-1) 成立來證明OM(m) m>0。首先考慮發送命令的將軍是忠誠的。那麼將引理中k 設為m 則OM(m) 滿足IC2 ,IC1 在發令將軍是忠誠的情況下也滿足。
  接著考慮m 個背叛者中有一個是發令者,那最多就只有m-1 個副官是背叛者了,又因為有3m 個將軍,所以副官的總數超過3m-1,且有3m-1>3(m-1) 。因此通過歸納法假設 OM(m-1) 滿足IC1 和IC2(最多3(m-1) 個將軍和最多m-1 個背叛者)。那麼任意兩個忠誠的副官j 在OM(m-1) 獲得相同命令vj,那麼在OM(m) 演算法中每個忠誠的副官都會收到(v1,v2,...,\v(n-1)),可知滿足條件IC1 和IC2。
  看完這段證明其實我也挺糊塗的~~~~,畫了張圖來看看lamport 是怎麼證明的:
  
拜占庭將軍問題
通過簽名消息

  簽名消息在除了滿足口頭消息A1-A3 三點要求外還應該滿足下面A4:
  A4 (a)簽名不可被偽造,一旦被篡改即可發現
  (b)任何人都可以驗證將軍簽名的可靠性
  下面定義一個類似於上面majority() 函數的choice() 來決定副官的選擇:1.當集合V 只包含了一個元素v ,那麼choice(V)=v ;2. choice(o)=RETREAT。
  有了上面A4 和choice() 基礎我們給出SM(m) 方法:
  SM(m) 演算法
  初始化Vi=空集合
  (1)將軍簽署命令併發給每個副官
  (2)對於每個副官i :
  (A)如果副官i 從發令者收到v:0 的消息,且還沒有收到其他命令序列,那麼:
  (i)使Vi 為{v}
  (ii)發送v:0:i 給其他所有副官
  (B)如果副官i 收到消息v:0:j1:...:jk 且v 不在集合Vi 中則
  (i)添加v 到Vi
  (ii)如果k
  (3)對於每個副官i ,當不再收到消息,則遵守命令choive(Vi)
  演算法的幾點說明:
  演算法第三步並沒有說明副官如何判斷沒有新的消息,可以通過兩個解決方法:一是要求每個副官收到消息后要麼簽名轉發該消息,要麼發送一個通知他將不發送這個消息;二是設置一個超時時間,如果在該時間段還沒有收到消息,則認為不再收到消息。
  演算法SM(m) 中,讓副官簽名是確認其收到了該消息(有點像來了份文件給每個領導批閱)。在SM(1) 中副官收到消息就不用簽字了,因為不用轉發給其他副官。
  定理2:對於任意m,最多只有m 個背叛者情況下,演算法SM(m) 解決拜占庭將軍問題
  Proof:首先證明IC2,如果發令者是忠誠的,那麼所有的副官一定收到相同的命令,因為簽名無法篡改,且IC1 也就滿足了。證明IC1 只用考慮發令者是背叛者的情況(重新回顧下IC1 是指所有忠誠的副官執行相同的命令),IC1 要求兩個忠誠的副官(i,j)必須收到相同的命令集合Vi、Vj,也就是Vi 中每個v 都在Vj 中。會存在兩種情況,其一當副官i 收到v 命令的序列后,加入到Vi,並將其發送給副官j ,j 將命令v 保存;其二副官i 收到命令v:0:j1:...:jk:i,其中有jr=j,所以 由A4 可知副官j 也收到了該命令。如果沒有,則有:
  k
  k=m。發令者是背叛者,最多只有m-1 個副官是背叛者。因此,最少有一個序列j1,...,jm是忠誠的。那麼j 一定收到這個忠誠的副官序列發來的值v ,所以副官j 收到v 。
  證明完畢。

相關評論

同義詞:暫無同義詞