NO IMAGE

在上一篇文章中,介紹了拜占庭將軍問題的描述、條件和結論。在傳輸口頭訊息(Oral Messages)時,少於3m 1個將軍中有m個叛徒時,拜占庭將軍問題是無解的。Leslie在原文1中, 提出了一種傳輸口頭訊息時拜占庭將軍問題的一種解法。

定義

首先,為定義口頭訊息,拜占庭將軍訊息系統具有以下假設:

A1. 每個訊息被正確傳送。
A2. 訊息的接收者知道是誰傳送的訊息
A3. 可以被檢測到缺少訊息

假設A1A2防止叛徒干擾其他兩個將軍的通訊,假設A3防止叛徒通過不發訊息干擾一致性達成。

另外,口頭協議演算法要求每個將軍可以與其他任意將軍直接進行通訊,Leslie在其原文中的第五章中描述了不需要滿足這個條件的演算法。

OM(m)演算法

Leslie針對口頭訊息(Oral Messages)的情況,提出了口頭協議演算法OM(m),其中m為非負。OM(m)演算法是一個遞迴演算法,用來處理在3m 1個將軍中至多存在m個叛徒的情況。

預設行動:副官如果在指定時間內收不到來自司令的命令,則預設採取“撤退”行動。這是為了防止司令官為叛徒時,通過不發出命令來阻礙達成共識。

行動函式:演算法假設使用majority方法作為行動函式,即當vi” role=”presentation”>viviv_i的大多數為v時,則

majority(v1,…,vn−1)=v” role=”presentation”>majority(v1,…,vn−1)=vmajority(v1,…,vn−1)=v

majority(v_1, …, v_{n-1})=v

注:其實對於行動函式,有兩種比較容易想到的選擇:

  • vi” role=”presentation”>viviv_i的大多數值v,如果不存在大多數採取預設行動——“撤退”;
  • 如果vi” role=”presentation”>viviv_i是個有序的集合,採用其中位數。

OM(m)演算法:採用遞迴定義,下面分別說明OM(0)OM(m)的內容。

當m=0″ role=”presentation”>m=0m=0m=0時,

OM(0)演算法

(1) 司令傳送他的值給每個副官;
(2) 如果副官收到司令的值,使用這個值;否則,使用預設值——“撤退”。

當m>0″ role=”presentation”>m>0m>0m>0時,

OM(m)演算法

(1) 司令傳送他的值給每個副官;
(2) 對於每個i” role=”presentation”>iii,令vi” role=”presentation”>viviv_i為副官i” role=”presentation”>iii從司令接收到的值;如果沒有收到值,則vi” role=”presentation”>viviv_i採用預設值——“撤退”。在OM(m-1)演算法中,副官i” role=”presentation”>iii作為司令向另外n-2個副官(不包括OM(m)中的司令)傳送值vi” role=”presentation”>viviv_i。
(3) 對於每個i” role=”presentation”>iii,對於每個j≠i” role=”presentation”>j≠ij≠ij\neq i的j” role=”presentation”>jjj,令vi” role=”presentation”>viviv_i為副官i” role=”presentation”>iii在第(2)步中從副官j” role=”presentation”>jjj接收的值;如果沒有接收到值,則使用預設值——“撤退”。副官i” role=”presentation”>iii用majority(v1,…,vn−1)” role=”presentation”>majority(v1,…,vn−1)majority(v1,…,vn−1)majority(v_1, …, v_{n-1})作為其值。

舉例:m=1, n=4

  • 當一個副官是叛徒時

假設副官3是叛徒,下圖針對副官2收到的訊息對OM(1)進行闡述。

Algorithm OM(1); Lieutenant 3 a traitor

第一步:司令向每個副官傳送他的值v” role=”presentation”>vvv給每個副官;
第二步:副官1執行OM(0),作為司令向副官2傳送v” role=”presentation”>vvv;由於副官3是叛徒,其執行OM(0)向副官2傳送了不同的值,假設為x” role=”presentation”>xxx;
第三步:副官2擁有的行動值集為{v1,v2,v3}={v,v,x}” role=”presentation”>{v1,v2,v3}={v,v,x}{v1,v2,v3}={v,v,x}\{v_1, v_2, v_3\}=\{v, v, x\},採用majority函式,副官2採取的行動值為v=majority{v1,v2,v3}” role=”presentation”>v=majority{v1,v2,v3}v=majority{v1,v2,v3}v=majority\{v_1, v_2, v_3\}。

同理,副官1採取的行動指令也是v” role=”presentation”>vvv,即滿足拜占庭將軍問題一致性條件IC1IC2

注:拜占庭將軍問題一致性條件為:

IC1. 所有忠誠副官遵守同一命令;
IC2. 如果司令官是忠誠的,每個忠誠的副官遵守他的命令。

  • 當司令為叛徒時

下圖描述了當司令為叛徒,三位副官是忠誠的情況對OM(1)演算法進行闡述。

Algorithm OM(1); The commander a traitor

第一步:司令為了阻止忠誠副官達成一致,分別向三位副官傳送值{x,y,z}” role=”presentation”>{x,y,z}{x,y,z}\{x, y, z\};
第二步:每個副官從司令收到的值作為自己的值,並執行OM(0)向其他副官傳送;
第三步:在第三步中,每個副官擁有的值集均為{x,y,z}” role=”presentation”>{x,y,z}{x,y,z}\{x, y, z\},因此,副官執行行動函式majority得到的結果是一樣的。

由於三位忠誠的將軍採取同樣的行動,滿足拜占庭將軍一致性條件IC1

從m=1, n=4的例子可以看出,OM(m)演算法能夠處理拜占庭將軍問題。在OM(m)演算法中,獨立執行了n-1OM(m-1),且每個OM(m-1)演算法獨立執行了n-2OM(m-2)……這就意味著,每個副官可能獨立傳送多輪訊息。為了避免混淆,需要區分每輪訊息。最易想到的方法是,每個副官i” role=”presentation”>iii在為第(2)步的值vi” role=”presentation”>viviv_i新增字首i” role=”presentation”>iii。可以看出,演算法OM(m-k)將被呼叫(n−1)…(n−k)” role=”presentation”>(n−1)…(n−k)(n−1)…(n−k)(n-1)…(n-k)次,傳送擁有k” role=”presentation”>kkk個副官序號字首的值。

OM(m)演算法證明

本節採用歸納法證明OM(m)演算法能夠解決拜占庭將軍問題。

引理

為了證明OM(m)演算法,我們首先來證明一條引理:

對於任意的m” role=”presentation”>mmm和k” role=”presentation”>kkk,如果在多於2k m” role=”presentation”>2k m2k m2k m個將軍中至多存在k” role=”presentation”>kkk個叛徒,則OM(m)演算法滿足條件IC2

證明: 歸納法,針對引數m” role=”presentation”>mmm進行歸納。

當m=0″ role=”presentation”>m=0m=0m=0時,根據假設A1OM(0)演算法,易得如果司令是忠誠的,忠誠的將軍按照司令的指令行動,引理是成立的。

當m>0″ role=”presentation”>m>0m>0m>0時,假設在m−1″ role=”presentation”>m−1m−1m-1時,引理成立,下面來證明在m” role=”presentation”>mmm時,引理也成立。

OM(m)第一步,司令傳送值v” role=”presentation”>vvv給他的n−1″ role=”presentation”>n−1n−1n-1個副官;

第二步,每個忠誠的副官在n−1″ role=”presentation”>n−1n−1n-1個副官中執行OM(m-1)演算法。根據假設n>2k m” role=”presentation”>n>2k mn>2k mn>2k m,則n−1>2k (m−1)” role=”presentation”>n−1>2k (m−1)n−1>2k (m−1)n-1>2k (m-1),所以根據引理在m−1″ role=”presentation”>m−1m−1m-1時成立,可得,每個忠誠的將軍從忠誠的將軍j” role=”presentation”>jjj處獲得的值為vj=v” role=”presentation”>vj=vvj=vv_j=v。

第三步中,由於叛徒最多有k” role=”presentation”>kkk個,且n−1>2k (m−1)≥2k” role=”presentation”>n−1>2k (m−1)≥2kn−1>2k (m−1)≥2kn-1>2k (m-1)\geq 2k,所以n−1″ role=”presentation”>n−1n−1n-1個將軍中的忠誠將軍為大多數。所以第三步每個忠誠的將軍獲得值majority(v1,…,vn−1)=v” role=”presentation”>majority(v1,…,vn−1)=vmajority(v1,…,vn−1)=vmajority(v_1, …, v_{n-1})=v,滿足條件IC2

引理得證。

證明

下面來證明演算法OM(m)能夠解決拜占庭將軍問題。

定理 1:對於任意m” role=”presentation”>mmm,如果存在多於3m” role=”presentation”>3m3m3m個將軍中至多有m” role=”presentation”>mmm個叛徒時,OM(m)演算法滿足條件IC1IC2

證明:針對變數m” role=”presentation”>mmm採用歸納法

當m=0″ role=”presentation”>m=0m=0m=0時,即沒有叛徒存在,則很容易證明OM(0)滿足條件IC1IC2

假設在m−1″ role=”presentation”>m−1m−1m-1時,定理成立,下面證明在m” role=”presentation”>mmm時,定理也成立。

  • 當司令是忠誠的

引理 1中的k=m” role=”presentation”>k=mk=mk=m,即多於3m” role=”presentation”>3m3m3m個將軍中至多存在m” role=”presentation”>mmm個將軍時,OM(m)滿足條件IC2。又因為當司令是忠誠的時,條件IC1包含在條件IC2中,所以OM(m)也滿足條件IC1

  • 當司令是叛徒時

由於至多有m” role=”presentation”>mmm個叛徒,所以至多存在m−1″ role=”presentation”>m−1m−1m-1個副官是叛徒。因為將軍的數量多於3m” role=”presentation”>3m3m3m,所以副官的數量也多於3m−1″ role=”presentation”>3m−13m−13m-1,且3m−1>3(m−1)” role=”presentation”>3m−1>3(m−1)3m−1>3(m−1)3m-1>3(m-1)。根據遞迴假設演算法OM(m-1)滿足條件IC1IC2,所以在第三步,對於每個副官j” role=”presentation”>jjj,任意兩個忠誠的副官得到相同的vj” role=”presentation”>vjvjv_j。(如果副官j” role=”presentation”>jjj是兩個中的一個,運用條件IC2;否則,運用條件IC1)。

所以,任意兩個忠誠的副官能獲得相同的指令值集{v1,…,vn−1}” role=”presentation”>{v1,…,vn−1}{v1,…,vn−1}\{v_1, …, v_{n-1}\},因此,在OM(m)第三步中,忠誠將軍遵從相同的值,即majority(v1,…,vn−1)” role=”presentation”>majority(v1,…,vn−1)majority(v1,…,vn−1)majority(v_1, …, v_{n-1})。所以,演算法OM(m)滿足條件IC1

綜上所述,定理 1得證。

小結

本文介紹了在將軍之間直接傳送口頭訊息(Oral Messages)時,解決拜占庭將軍問題的演算法OM(m),並對其在m=1″ role=”presentation”>m=1m=1m=1且n=4″ role=”presentation”>n=4n=4n=4時進行了舉例說明,最後對OM(m)演算法進行了證明。

接下來的文章中,將對將軍之間傳輸簽名的書面訊息(Signed Messages)時,解決拜占庭將軍問題的演算法進行闡述。


  1. Lamport L, Shostak R, Pease M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 382-401.