題目：The Byzantine Generals Problem
年份：1982
來源：ACM Transactions on Programming Languages and Systems
作者：LESLIE LAMPORT, ROBERT SHOSTAK, and MARSHALL PEASE

• 1.Introduction
• 2.Impossible Results
  • 2.1 3將軍(1叛徒)問題不存在解/不能達成共識
  • 2.2 少于3m+1個將軍(有m個叛徒)不存在解/不能達成共識。
    • 2.2.1 精確一致性的證明
    • 2.2.2 近似一致性的證明
• 3. A Solution With Oral Messages
  • 3.1 Oral Messages的定義
  • 3.2 OM(m)算法的步驟及其正確性推導
    • 3.2.1 算法步驟
    • 3.2.2 OM(M)算法的正確性證明
• 4. A Solution With Signed Messages
  • 4.1 Signed Message的定義
  • 4.2 SM(m)算法的步驟及其正確性推導
    • 4.2.1 SM(m)算法的步驟
    • 4.2.2 SM(m)算法的正確性證明
• 5. Missing Communication Paths
  • 5.1 對OM(m)的改進OM(m,p)
• 6. Reliable Systems
  • 6.1 可信系統的要素
  • 6.2 消息傳遞系統的約束
    • 6.2.1 A1 每一個正常節點發出的信息都被正確的送達
    • 6.2.2 A2 信息接收者知道信息的發送者
    • 6.2.3 A3 信息缺失能夠被檢測到。
    • 6.2.4 A4 簽名不可篡改及可驗證性
• 7. 結論
• 8. 個人理解&與PBFT的聯系與區別

1.Introduction

問題定義

將軍決定對敵方城市一個統一的計劃，將軍之間通過信使通信。

解決該問題有效算法的限定條件：

A.所有誠實的將軍決定一致的行動計劃（誠實的將軍要么都是撤退，要么都是進攻） B. 少部分的叛徒并不會導致誠實的將軍接受錯誤的計劃

條件A若為真，則后述內容為真：每一個誠實的將軍必須獲得相同的信息（也可表述為：任意兩個城市節點的收到將軍i的v(i)值是相同的）；如果第i個將軍是忠誠的，那么其他將軍用到的他所發出的信息也必須是v(i)。

拜占庭將軍問題：一個commanding general發送給他的n-1個lieutenant generals命令，以達成一致，約束條件如下：

IC1.所有誠實的中尉遵從相同的命令； IC2.如果將軍誠實，每一個誠實的中尉都遵從指揮官的命令。

IC1&IC2也被稱為交互一致性( interactive consistency )。
這里的IC1&IC2分別保證了分布式系統中的Safety與Liveness。

2.Impossible Results

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

?如圖所示，在three-general(one traitor)問題中，不管指揮官還是中尉2是叛徒，中尉1都無法對拜占庭節點進行區分，在圖2中，中尉1最終會選擇進攻，而中尉2會選擇撤退，所以就不滿足IC1。因此，一個指揮官兩個中尉（中尉必須服從指揮官的命令），存在一個叛徒的情況下不能達成一致的的行動計劃。

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

2.2.1 精確一致性的證明

證明（反證法）：
?注意此處的拜占庭將軍并不單指叛徒，而是指所有的將軍。
?本文假設3m個將軍(m個叛徒)存在解，用這一解來構造three-general (one traitor)問題的解。而3將軍解由上文分析可以知道是不存在的（也就是如果構造出來了，那就說明3將軍解存在），但這與已知(3將軍問題不存在解)矛盾，所以假設(即3m將軍問題存在解)不成立。

?將3m將軍m叛徒問題中的將軍稱為阿爾巴尼亞將軍，3將軍1叛徒中的將軍稱為拜占庭將軍，以示區分。

?拜占庭指揮官代表一個阿爾巴尼亞指揮官和m-1個阿爾巴尼亞中尉，兩個拜占庭中尉分別代表m個阿爾巴尼亞中尉。因此對于拜占庭叛徒將軍（代表m個阿爾巴尼亞將軍），最多對應m個阿爾巴尼亞叛徒將軍。
?由IC1可知，m個阿爾巴尼亞中尉（由單個誠實拜占庭中尉所代表）遵循相同的命令，這一命令也是該誠實拜占庭節點所需要遵守的命令。
?對于阿爾巴尼亞將軍，可知是滿足IC1和IC2的，又由以上對應關系，可知3將軍問題是滿足IC1和IC2的，也即3將軍問題存在解，與已知矛盾，故3m將軍問題不存在解

2.2.2 近似一致性的證明

精確一致性與近似一致性是同等困難的
?本文假設將軍必須同意一個大致的攻擊時間，而不是具體的攻擊計劃，即，指揮官下令指示攻擊時間，且滿足以下條件：

IC1'. 所有的誠實中尉在十分鐘內發起攻擊。 IC2'. 指揮官誠實，則誠實的中尉在指揮官命令中的寫的進攻時間的±10min會進攻

（攻擊之前一天該命令就已經被中尉們收到；收到命令的時間不重要。只有在命令中指示的的攻擊時間重要。）

上述問題類似于拜占庭將軍問題，除非誠實的將軍數多于2/3，否則本問題無解。

證明(依舊反證法)：
假設本問題有解，那么我們可以用這個解構造出拜占庭3將軍問題的解。
假設：指揮官發送給中尉信息攻擊的時間。1:00代表進攻，2:00代表撤退。

（1）每個中尉根據收到的攻擊時間而遵循的命令：時間是1:10以前，則攻擊；時間是1:50之后，則撤退；否則轉向（2） （2）查詢其他中尉做出的“進攻”或“撤退”的命令如果其他中尉做出了決定，則該中尉遵循與其他中尉相同的命令；否則，撤退。

對上述問題的分析：
?如果指揮官是忠誠的，那么IC2’就被滿足，由IC2’可以推出IC1’。
?如果指揮官是叛徒，則需要IC2’成立，此時兩個中尉都是誠實的。根據IC1’，如果一個中尉(稱該中尉為L1)決定進攻，那么另一個就不能夠決定是進攻還是撤退（因為不滿足IC1’的條件，稱該不能決定的中尉為L2），所以L2轉向step(2),查詢到L1的決定為進攻，因此L2也決定進攻，那么L1和L2就達到了共識，故IC1’也滿足。因此就構造出了拜占庭問題的3將軍問題的解，同理，拜占庭的3將軍問題不存在解，因此本問題也不存在解。
?同理對于該近似一致性的3m將軍問題的解與上文所述一致。

3. A Solution With Oral Messages

3.1 Oral Messages的定義

Oral messages:

• A1 每一個正常節點發出的信息都被正確的送達；
• A2 信息接收者知道信息的發送者；
• A3 信息缺失能夠被檢測到。

?A1&A2保證叛徒節點不能夠干擾兩個誠實節點的通信，A1保證信息傳輸的正確性，A2保證信息本身的正確性。A3能夠阻止叛徒不發送信息來干擾共識達成。（具體實現在section 6）
?以上要求了將軍之間能夠直接進行通信，section 5 提出了不能進行直接通信的算法。

3.2 OM(m)算法的步驟及其正確性推導

3.2.1 算法步驟

?本節提出的算法OM(m)，m為叛徒個數。叛徒為指揮官時可能不發送進攻或者撤退的消息，本文把撤退作為默認命令。
中尉的編號是1~(n-1)，每個中尉發送的信息是v_i（作者發現用中尉“獲得某一值”比“服從命令”要更加方便）

函數majority:
取收到的消息(v₁,v₂……v_n-1)的大多數。
（大多數的確定：眾數或者中位數）
算法OM(0)：
(1)指揮官發送命令
(2)中尉收到指揮官的命令

算法OM(m) m>0：
(1)指揮官發送其命令給所有中尉
(2)對每一個中尉i，若收到來自指揮官的命令，那么將其值賦給v_i，否則，v_i的值為RETREAT。中尉i作為指揮官執行OM(m-1)算法將他的v_i值發送給其他n-2個中尉。
(3)對每一個中尉i，讓v_j代表i在步驟(2)收到的來自其他中尉j的值v_j。那么中尉i會采用majority(v₁,v₂……v_n-1)。

如圖示例：m=1, n=4.

當一個中尉為叛徒的情況

(1) 在OM(1)的第一階段，指揮官發送值v給其余三個中尉;
(2) 第二階段：中尉1用算法OM(0)發送值v給中尉2，中尉3發送給中尉2值x；
(3) 在第三步，中尉2此時獲得了兩個v和一個x，因此最終中尉2獲得正確的值為v=majority(v,v,x)。中尉1同理。
當指揮官為叛徒的情況
(1) 指揮官發送值x,y,z給中尉1,2,3；
(2)~(3) 最終每一個中尉都得到majority(x,y,z)，并不能得到統一的解。

由以上過程，可知算法是遞歸運行的，從OM(m)到OM(m-1)…OM(0)，OM(m)調用n-1個OM(m-1)，每個OM(m-1)調用n-2個OM(m-2)…一直到OM(0)

節點數n，叛徒數m的情況下若叛徒節點參與通信(發送錯誤信息):

OM(m-1)被調用的次數n-1 OM(m-2)被調用的次數(n-1)(n-2) OM(m-3)被調用的次數(n-1)(n-2)(n-3) OM(m-k)被調用的次數(n-1)(n-2)(n-3)..(n-k) 總的次數：n-1+(n-1)(n-2)+(n-1)(n-2)(n-3)+(n-1)(n-2)(n-3)..(n-k)

這里是以上遞歸算法的流程

3.2.2 OM(M)算法的正確性證明

引理1：對任意m,k，若系統中將軍總數超過2k+m，叛徒最多有k個，算法OM(m)滿足IC2，即如果指揮官誠實，那么每一個誠實的中尉都遵從指揮官的命令。

引理1證明：
當m=0時，由A1可知，IC2滿足；
當m>0時，在OM(m)算法的step(1)，指揮官把值傳給n-1個中尉，在step(2)中，每一個誠實的中尉調用OM(m-1)，前文已知n>2k+m，因此n-1>2k+(m-1)，所以每一個誠實的中尉i都會得到城實中尉的v_j=v。又因為n-1>2k+(m-1)>=2k，即這n-1個中尉的半數以上都是誠實的，所以step(3)中獲得的majority(v₁,v₂……v_n-1)必等于v，即滿足IC2。

定理1 對任意m，如果將軍數量大于3m且叛徒數最多是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個叛徒。中尉的數量是3m-1，且3m-1>3(m-1),因此OM(m-1)滿足IC1&IC2。對于每一個j，任意兩個誠實的中尉得到的都是相同的v_j的值(這任意兩個中尉有一個是j的話就由IC2可以推出；若不包括j的話，由IC1可以推出)。因此，任意兩個誠實的中尉最終會得到相同的v₁,v₂……v_n-1，也即算法step(3)的majority(v₁,v₂……v_n-1)相同，OM(m)的IC1的以證明。

對于證明的思路分析： 采用了歸納演繹法， 顯然OM(0)恒成立； 假設OM(m-1)成立，若指揮官誠實，那么由引理1可推OM(m)的IC2成立，進而OM(m)IC1成立。若指揮官為叛徒，通過歸納法證明過程中對任意j由OM(m-1)的IC2推出任意兩個誠實中尉有相同v_j的值，這是因為如果j為兩個誠實中尉之一，那么就符合OM(m-1)的IC2條件；如果j不是這兩個誠實中尉之一，那么j是誠實將軍自不必多說，如果j是叛徒的話，因為該任意兩個中尉是誠實的，由IC1也可推知二者Vj的值也相同，雖然不是正確值，但達成了共識。因此滿足IC1，即OM(m)滿足IC1&IC2。

綜上，定理1成立。

4. A Solution With Signed Messages

4.1 Signed Message的定義

??叛徒能夠“撒謊”導致拜占庭將軍問題變的難以解決。可以通過讓將軍發送不可偽造的信息的方式進行解決。
??在A1~A3的基礎上添加A4約束：

(a) 誠實將軍的簽名不可偽造且可以檢測到任何其簽名的信息的改動； (b) 任何人都可以驗證將軍的簽名的真實性。 并未對叛徒將軍的信息進行約束，因此叛徒將軍之間可以共謀。

有了以上約束，3將軍問題就存在了解。
m叛徒任意數量將軍算法：(將軍總數少于m+2是無意義的)

4.2 SM(m)算法的步驟及其正確性推導

4.2.1 SM(m)算法的步驟

算法大致流程：

指揮官發送帶有自己簽名的信息給所有中尉； 中尉在指揮官簽名的基礎上附上自己的簽名并發給其他中尉； 其他中尉重復操作。

定義choice函數將一組命令轉變成單個命令：

1. 如果集合V由單個元素v組成，choice(V)=v; 2. choice(None)=RETREAT。

choice函數的定義也可以是中位數。
x:i表示被將軍i簽名的信息x，v:j:i表示先被j簽名的信息v，然后又被i簽名的v:j。
General 0代表commander.
每一個lieutenant i都維持一個集合V_i，V_i是當前收到的被正確簽名的命令的集合。(如果指揮官誠實，那么此集合只有一個元素。)

算法SM(m)步驟:
??(1). Initially $V_i=\Phi$
??(2). For each i:
???? (A) If Lieutenant i receives a message of the form v:0 from the commander and he has not yet received any order, ??????then
??????(i) he lets $V_i$ equals ($v$):
??????(ii) he sends the message $v:0:i$ to every other lieutenant.
????(B) If Lieutenant i receives a message of the form $v:0:j_1:...:j_k$ and $v$ is not int the set $V_i$, then:
??????(i) he adds $v$ to $V_i$;
??????(ii) if $k<m$, then he sends the messages $v:0:j_1:...:j_k:i$ to every lieutenant other than $j_1:...:j_k$.
??(3). For each i: When Lietenant i will receive no more messages, he obeys the order $choice(V_i)$.

在步驟(2)，中尉i會忽略任何已經包含在集合$V_i$中的命令$v$的信息。
在step(3)如果一個中尉不接受到信息該如何決斷呢？一個中尉在step(2)能夠最多接收到一次 $v:0:j_1:...:j_k:i$ 信息，若約束中尉$j_k$要么發送該信息(指 $v:0:j_1:...:j_k:i$ )，要么發送一個其停止接收該信息的信息，就能夠在收到所有信息較容易地做出決定。(通過A3約束，即任何信息的缺失都能夠被檢測到，任一中尉都能夠檢測到上述關于$j_k$上述兩個信息的缺失) 。除此以外，當無信息到達時超時機制也可用于進行決斷(Section 6給出)。
step(2)中收到簽名的中尉會丟棄具有不正確簽名格式的信息，這是為了節省存儲空間。因為如果不這么辦的話，當一個命令$v$被$k$個中尉簽名并以消息形式傳遞給其他中尉的時候，系統中就會存在$(n?k?2)(n?k?3)...(n?m?2)$個拷貝。
以n=7,m=2為例：(本文應該是默認叛徒不參與通信(也可能是無法進行通信)或且發出的信息并不留存)

被k個中尉簽名拷貝數目(理論值)消息發出時狀態

0	n-1	$v:0$
1	4*(7-2-2)	$v:0:j_1$
2	3 (此時k=1<m,并不會停止傳播)	$v:0:j_1:j_2$

之后所有節點發現k=m，轉step(3)

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-wzyavUv2-1596772239276)(3-SM1-commanderTraitor.png)]

上圖5展示了算法SM(1)的運行過程，叛徒指揮官發給中尉1命令$"attack":0$ ，發給中尉2命令$"retreat":0$ 。經過step(2)，兩個中尉的$V_1=V_2="attack","retreat"$,且都遵循該命令$choice=("attack","retreat")$，與圖2的OM算法不同之處在于中尉通過最后的$choice$可以知道指揮官是叛徒，并且A4也能保證其結論的正確性。
事實上，第m個將軍并不需要繼續在命令的后邊附上自己的簽名，因為他收到命令之后就不會再轉發給別人了。因此SM(1)的簽名是不必要的。

4.2.2 SM(m)算法的正確性證明

定理2 對任意m，算法能夠解決最多m個叛徒的拜占庭將軍問題。

證明：
先證IC2，當指揮官是誠實的情況下，在step(1)他會發送$v:0$給他的中尉們，每一個誠實的中尉在step(2)(A)都會收到命令$v$,因為叛徒中尉并不能偽造指揮官簽名，因此在step(2)(B)并不能對消息進行篡改，所以誠實的中尉在step(2)(B)并不能收到除了$v$以外的其他命令。這就保證了集合$V_i$只會有一個命令$v$，再經由step(3)的$choice$函數，最后每一個中尉的命令都是一樣的，也即滿足IC2。
因為在指揮官是誠實的情況下IC1可以由IC2推導出，因此只需要證明指揮官是叛徒的情況下是否符合IC1即可。若兩個中尉$i,j$最后在步驟3服從相同的命令，那么他們倆在step(2)的$V_i,V_j$也是一樣的。因此，證明IC1就是證明
如果$i$在step(2)將$v$加入到集合$V_i$，那么$j$也一定在step(2)把$v$加入到$V_j$中。
如果i在step(2)(A)收到了命令$v$，那么他就會將其在step(2)(A)(ii)發送給$j$，所以$j$就會收到這一信息(因為消息的A1約束)。如果$i$在step(2)(B)將命令添加到自身的$V_i$中,那他一定收到了信息 $v:0:j_1:...:j_k$ 。如果$j$是其中一個$j_r$那么通過A4約束，他一定已經收到了消息$v$，如果$j$不在該簽名隊列( $j_1:...:j_k$ )中，分兩種情況

$k<m$的話，i就會將信息$v:0:j_1:...:j_k:i$發給$j$，$j$同樣會收到命令$v$。

$k=m$的話，除叛徒指揮官之外，n-1個中尉中最多還有m-1個叛徒中尉，因此至少在$j_1，j_2...:j_m$中，至少有一個中尉是誠實的。那么這個誠實的中尉也在他收到消息的第一時間將$v$發給$j$。

所以無論如何$j$還是會收到$v$
綜上所述，SM(m)算法滿足IC1&IC2，定理2成立。

5. Missing Communication Paths

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

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-C4WH1bVg-1596772239279)(3-3-regular_graph.png)]

如果兩個將軍有邊相連，那么稱這兩個將軍為鄰居。

定義1 ：
??(a) 節點i的鄰居正則集合(regular set of neighbors)是滿足以下條件的點集$i_1,...,i_p$
????(i) 每一個$i_j$是點$i$的鄰居，且
????(ii) 對每一個不同于$i$的將軍$k$，存在至少兩條從$i_j$到$k$的不經過$i$且只有終點$k$重合的路徑${\gamma }_j{,}_k$。
??(b) 如果圖G的每一個點都有一個由p個點構成的regular set of neighbors，那么圖G被稱為p-正則圖(p-regular)。

圖6就是一個$3?regular$，圖7就不是，因為中心點沒有有3個點的regular set of neighbors。

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

前提：需要將軍(包括叛徒將軍)之間的能夠發送消息的圖是一個$3m?regular$。
對所有的正數$m,p$，如果圖G是一個$p?regular$，定義算法$OM(m,p)$如下所示。
$OM(m,p):$
??(0) 選擇指揮官的由$p$個中尉組成的正則鄰居集合$N$。
??(1) 指揮官將其值發給$N$中的每一個中尉。
??(2) 對$N$中的每一個中尉$i$，以$V_i$代表$i$收到的值，或RETREAT代表未收到任何值。中尉$i$按照如下方式將$V_i$發給其他中尉$k$：
????(A) 如果$m=1$，通過定義1中符合(a)(ii)要求的路徑${\gamma }_j{,}_k$發送值。
????(B) 如果$m>1$，那么在圖中去除指揮官且$i$扮演新的指揮官運行算法$OM(m?1,p?1)$。
??(3) 對每一個$k$，且每一個在$N$中不同于$k$的$i$，將中尉$k$在step(2)中收到的來自中尉$i$的值賦給$v_i$，如果沒有收到就賦值RETREAT給$v_i$。當$N=i_1,...i_p時，$中尉$k$采用$majority(v_{i_1},...v_{i_p})$的值。
注意：在移除$p?regular$圖的單個點之后，就得到了一個$p?1?regular$圖，因此$OM(m?1,p?1)$在step(2)(B)仍然是適用的。

引理2 對任意$m>0$且$p\ge 2k+m$，在最多有$k$個叛徒的情況下，算法$OM(m,p)$仍然滿足$IC2$。

證明引理2：

定理3 對任何$m>0,p>3m$，在最多有$m$個叛徒的情況下，算法$OM(m,p)$能夠解決拜占庭將軍問題。

證明定理3：

定理4 對任何$m,d$，在最多有$m$個叛徒并且誠實將軍的子圖直徑(相聚最遠的兩點)$d$的情況下，算法$SM(m+d?1)$能夠解決拜占庭將軍問題。

證明定理4：

推論 如果誠實將軍的圖是連通圖，那么$SM(n?2)$能夠解決$n$將軍問題的拜占庭將軍問題。

6. Reliable Systems

6.1 可信系統的要素

可信系統的兩大要素：一致性(Safety)、可用性(Liveness)。(分別對應下列1,2)

所有正常(nonfaulty)的$processors$必須采用相同的輸入值以保證相同的輸出。

如果輸入單元正常工作的話，所有正常的$processors$用輸入單元提供的值作為輸入來進行處理，以便于正確地輸出。

事實上，以上$processors$代表中尉，輸入單元代表指揮官，誠實意味著$nonfaulty$。
除了$processors$之間互相交流來解決拜占庭將軍問題，沒有方法能夠保證不同的$processors$從一個可能發生故障的設備獲取的是相同的值。

針對輸入設備可能存在提供無意義的輸入值的情況，如果該值十分重要的話，可以通過設置多個獨立輸入設備的方式來提供冗余。當然，冗余輸入也不是一定能保證可信，還是得需要確保$nonfaultyprocessors$使用這些冗余至計算出相同的輸出。

針對正常輸入設備可能在不同時有不同值的情況，假設$majority$或者$choice$取的是中位數，那最后得出的結果很大程度上依賴于輸入設備提供的值的范圍。

6.2 消息傳遞系統的約束

本文所給出的構建可信系統的解決辦法(OralMessages or SignedMessages)，將軍算法的實施并不難(就是OM(m)和SM(m)及它們的改進OM(m,p)和SM(m+d-1))，難點在滿足$A1A3及A4$的消息傳遞系統的實現。以下對$A1A4$給出考量。

6.2.1 A1 每一個正常節點發出的信息都被正確的送達

在現實系統中，信道可能隨時失效。
在$OralMessages$的算法中，兩個$processors$之間的信道失效則等同于一個$processors$失效，因此可以容忍的錯誤數$m$包括單純的$processors$故障以及信道失效(當然，一個$processors$的多個信道失效等同于那一個$processors$故障)。
在$SignedMessages$的算法中，如果信道的失效不能導致消息的偽造的話，那么算法$SM(m)$其實是對信道失效并不敏感的。這是因為定理4在信道失效的時候依然有效。

6.2.2 A2 信息接收者知道信息的發送者

這一點也是十分必要的，因為一個$faultyprocessor$不能扮演一個$nonfaultyprocessor$。實際上，這意味著進程間通信是通過固定線路而不是通過某些消息交換網絡進行的。(如果使用交換網絡，則必須考慮故障網絡節點，然后拜占庭將軍問題還會出現)如果$A4$存在的話，其實$A2$是不必要的。因為假扮某一個$processer$都會表現為偽造他的信息。

6.2.3 A3 信息缺失能夠被檢測到。

信息的缺失只能通過超過規定時間內到達來檢測到。能夠滿足$A3$約束的超時設置有以下要求：

消息的生成和傳送都有一個最大固定時間。

在固定最大錯誤范圍內，發送者和接收者時鐘是同步的。(類似于時間相差±20ms)

對以上兩個約束的解釋：

• 1是為了保證接收者能夠知道自己等了多久(消息的生成時間是指$processer$接收到必要輸入并生成消息之后開始所花費的用來發送消息的時間)
• 2是為了拜占庭將軍問題能夠解決的必要條件。假設將軍只有在以下情況發生時才會采取行動：對所有將軍而言固定的初始時間、在消息一到達的時候、當一個隨機選取的時間段結束的時候。
  給傳輸延遲設置上限或者下限可以使得$processor$在消息來回傳輸的過程中實現時鐘。

1&2兩個設定讓A3具有可行性。讓$\mu$代表消息最大產生和傳輸的延遲，且無論何時正常$processors$之間的時鐘之間的誤差在$\tau$之間。那么所有在本地時間$T$時間正常生成的信息，都會在接收者本地時間$T+\mu +\tau$時間收到，因此，如果接收者沒有收到信息的話，就可以認為信息未被發送。(如果信息未在規定時間內送達，那么發送者一定是出了故障，因此算法的正確性不能依賴于正在發送的信息。)因此，在設置了輸入處理單元發送值的時間之后，接收者就可以依此來決定自己需要等待的時間了。例如，算法$SM(m)$中一個$processor$必須等待$T_0+k(\mu +\tau )$時間(k指消息已經被k個將軍簽過名)，$T_0$指指揮官開始執行算法的時間。
和拜占庭將軍問題同樣難的問題在保持$processors$的時鐘同步，因為即使剛開始都是同步的，那么隨著算法的執行也會變得不同步。

6.2.4 A4 簽名不可篡改及可驗證性

(a) 誠實將軍的簽名不可偽造且可以檢測到任何其簽名的信息的改動；
(b) 任何人都可以驗證將軍的簽名的真實性。

用$S_i(M)$表示$i$對$M$的簽名。為了滿足$A4$約束，$S_i$必須滿足：(a) 如過$processori$正常，那么沒有其他$processor$能夠生成$S_i(M)$；(b) 給出$M,X$，任何$process$都能夠驗證$X$是否等于$S_i(M)$。性質(a)是無法被確保的，因為$S_i(M)$只是一個數據項，而$faultyprocessor$是可以去產生任何數據項的。但是仍然可以采取以下措施來減少這一可能：

• Random Malfunction $S_i(M)$
• Malicious Intelligence 針對人為操作正常的$processor$來擾亂系統的正常運行，可以通過密碼學的方法構造$S_i$

當簽名被看到的時候就很容易去偽造$S_i(M)$，因此，應當避免相同的信息被兩次簽名，這就意味著當使用$SM(m)$重復的發送一個值的時候，需要給值加上序列號以保證其唯一性。

7. 結論

本文提出的應對拜占庭將軍問題的解在對時間和消息數量上的花費是很多的。$OM(m),SM(m)$都要求信道數量需要大于m+1條。換句話說，每一個中尉都要去等待指揮官發出的命令并且通過$m$個其他中尉轉發該消息。非強連通圖的解決算法需要消息傳遞路徑數大于$m+d$，$d$代表忠誠將軍所代表的子圖的路徑。

幾個獨立的消息可以被合并發送，但是消息數量的壓縮雖有可能但是有待進一步研究。
隨機故障下的可靠性是一個難題且其解決方法是很昂貴的。唯一的方法就是去限定錯誤發生的類型，比如說人們經常假定計算機無法響但是永遠無法返回錯誤的響應，而這種假設在拜占庭將軍問題中并不能行。

8. 個人理解&與PBFT的聯系與區別

滿足IC1&IC2并不一定會是正確的解，只是達成了共識。
例如：
疑問：假設叛徒指揮官發給1&2是y, 發給3是z，最后是否能達成y共識。怎么區別叛徒指揮官的問題

$SM(m)$與PBFT的區別（僅僅筆者看出來的，歡迎補充）
[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-EGADYsxO-1596772239280)(2020-07-29-09-38-05.png)]
PBFT弱化了Liveness強調Safety，PBFT achieves safety even in fully asynchronous network condition, and liveness under period of synchrony, as permitted by FLP. 保證的是最終一致性

參考文獻：
L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3), 1982

總結

以上是生活随笔為你收集整理的The Byzantine Generals Problem拜占庭将军问题理解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。