拜占庭问题论文翻译
The Byzantine Generals Problem
? 可靠的計(jì)算機(jī)系統(tǒng)必須處理會(huì)向系統(tǒng)的不同部分提供沖突信息的故障組件。這種情況可以用拜占庭軍隊(duì)的將軍和他們的部隊(duì)圍困在敵方城市附近來概括地表達(dá)。 將軍們只能通過使者交流，他們必須商定共同的戰(zhàn)斗計(jì)劃。 但是，其中一個(gè)或多個(gè)可能是叛徒，他們會(huì)試圖混淆其他人。 問題是找到一種算法來確保忠實(shí)的將軍們達(dá)成共識(shí)。 結(jié)果表明，僅在口頭表達(dá)的情況下，只有并且只有三分之二以上的將軍忠誠(chéng)時(shí)，這個(gè)問題才能解決。 所以一個(gè)叛徒可以混淆兩個(gè)忠實(shí)的將軍。 有了不可偽造的書面信息，這個(gè)問題對(duì)于任何數(shù)量的將軍和可能的叛徒來說都是可以解決的。 然后討論該解決方案在可靠的計(jì)算機(jī)系統(tǒng)中的應(yīng)用。
1.引言
? 可靠的計(jì)算機(jī)系統(tǒng)必須能夠應(yīng)對(duì)一個(gè)或多個(gè)組件的故障。 發(fā)生故障的組件可能表現(xiàn)出一種通常被忽略的行為，即，將沖突的信息發(fā)送到系統(tǒng)的不同部分。 應(yīng)對(duì)此類故障的問題抽象表示為拜占庭將軍問題。 我們將本文的主要部分專門討論了這個(gè)抽象問題，并通過指出如何將我們的解決方案用于實(shí)現(xiàn)可靠的計(jì)算機(jī)系統(tǒng)來進(jìn)行總結(jié)。 我們假設(shè)拜占庭軍隊(duì)的幾個(gè)師駐扎在一個(gè)敵方城市之外，每個(gè)師由其自己的將軍指揮。將軍只能通過使者相互溝通。 觀察敵人之后，他們必須決定共同的行動(dòng)計(jì)劃.但是，有些將軍可能是叛徒，試圖阻止忠實(shí)的將軍達(dá)成協(xié)議。
將軍們必須有一種算法來保證:
A.所有忠實(shí)的將軍都決定相同的行動(dòng)計(jì)劃。
? 忠實(shí)的將軍都會(huì)按照算法說的去做，但是叛徒可以做他們想做的任何事情。無論叛徒做什么，該算法都必須保證條件A。忠實(shí)的將軍們不僅應(yīng)該達(dá)成協(xié)議，而且應(yīng)該就合理的計(jì)劃達(dá)成協(xié)議。因此，我們還想確保
B.少數(shù)叛徒不會(huì)使忠誠(chéng)的將軍們采取錯(cuò)誤的計(jì)劃。
? 條件B很難形式化，因?yàn)樗枰獪?zhǔn)確說出一個(gè)不好的計(jì)劃，我們不會(huì)嘗試這樣做。相反，我們考慮將軍們?nèi)绾巫龀鰶Q定。每個(gè)將軍觀察敵人并將他的觀察力傳達(dá)給其他人。令v（i）為第i個(gè)將軍傳達(dá)的信息。每個(gè)將軍使用某種方法將值v（1）… v（n）組合到一個(gè)單獨(dú)的行動(dòng)計(jì)劃中，其中n是將軍的數(shù)量。條件A通過讓所有將軍使用相同的方法來組合信息來實(shí)現(xiàn)，條件B通過使用魯棒的方法來實(shí)現(xiàn)。例如，如果要做出的唯一決定是進(jìn)攻還是撤退，則v（i）將是通過將軍 i認(rèn)為哪種選擇最好的決定，而最終決定可以基于其中的多數(shù)票。只有忠實(shí)的將軍在兩種可能性之間幾乎均等地劃分時(shí)，少數(shù)叛徒才會(huì)影響決策。
? 雖然這種方法可能不是滿足條件 A 和 B 的唯一方法，但它是我們所知道的唯一方法。它假定將軍們用一種方法彼此交流他們的信息V(i)。顯而易見的方法是通過信使相互發(fā)送 v(i)。然而，這不起作用，因?yàn)闈M足條件 A要求每個(gè)忠誠(chéng)的將軍獲得相同的值 v(1)…V(n)。一個(gè)叛國(guó)的將軍可以給不同的將軍發(fā)出不同的價(jià)值觀。要滿足條件 B，下列條件必須滿足:
**1.每個(gè)忠誠(chéng)的將軍都必須獲得相同的信息。**一致性
? 條件 1 意味著一個(gè)將軍不一定能直接使用從第一個(gè)將軍那里得到的 v(i)值，因?yàn)橐粋€(gè)叛國(guó)的將軍可以給不同的將軍發(fā)送不同的值。這意味著，如果我們不小心，在滿足條件 1 的情況下，我們可能會(huì)引入一種可能性，即將軍們使用的 v(i)值不同于第一個(gè)將軍發(fā)出的 v(i)值——即使第一個(gè)將軍是忠誠(chéng)的。如果要滿足條件 b，我們就不能允許這種情況發(fā)生。例如，如果每一個(gè)忠誠(chéng)的將軍都發(fā)出“進(jìn)攻”的信號(hào)，我們就不能允許少數(shù)叛徒使忠誠(chéng)將軍以“撤退”、“…”、“撤退”的信號(hào)為基礎(chǔ)作出決定。因此，我們對(duì)每個(gè) i 都有以下要求:
**2.如果第i個(gè)將軍是忠誠(chéng)的，那么他發(fā)送的值必須被每個(gè)忠誠(chéng)的將軍用作 v(i)的值。**正確性
我們可以重寫條件 i 作為條件，即對(duì)于每一個(gè) i(不管第一個(gè)將軍是否忠誠(chéng))，1’。任何兩個(gè)忠誠(chéng)的將軍使用相同的價(jià)值 v(i)。條件 1’和 2 都是由第 i 個(gè)將軍發(fā)送的單個(gè)值的條件。因此，我們可以考慮限制在一個(gè)將軍如何把他的信息傳遞給其他將軍的問題上。我們用一個(gè)指揮官向他的副官們發(fā)出命令的方式來表達(dá)這個(gè)意思，得到以下的問題。
拜占庭將軍問題指揮官必須向他的n-1中將下達(dá)命令
IC1. 所有忠誠(chéng)的副官都遵守同樣的命令。
IC2.如果指揮官是忠誠(chéng)的，那么每個(gè)忠誠(chéng)的中尉都會(huì)服從他發(fā)出的命令。
? 條件 IC1 和 IC2 稱為交互式一致性條件。請(qǐng)注意，如果指揮官是忠誠(chéng)的，那么 IC1就跟隨 IC2。然而，指揮官并不需要忠誠(chéng)。
? 為了解決我們最初的問題，第一位將軍用一個(gè)解決方案向拜占庭將軍問題發(fā)出命令，“使用 v(i)作為我的信息”，其他將軍充當(dāng)中尉，從而發(fā)出 v(i)的價(jià)值。
2.不可能的結(jié)果
? 拜占庭將軍問題看起來簡(jiǎn)單得讓人難以置信。如果將軍們只能發(fā)送口頭信息，那么除非三分之二以上的將軍們忠誠(chéng)，否則任何解決方案都不會(huì)奏效。特別是，只有三個(gè)將軍，沒有任何解決辦法可以在一個(gè)單一的叛徒存在。口頭信息的內(nèi)容完全在發(fā)送者的控制之下，因此叛國(guó)的發(fā)送者可以傳遞任何可能的信息。這種信息對(duì)應(yīng)于計(jì)算機(jī)通?；ハ喟l(fā)送的信息類型。在第四部分，我們考慮簽名的，書面的協(xié)議，因此這不是真的。
? 我們現(xiàn)在表明，口頭信息沒有解決三個(gè)將軍可以處理一個(gè)叛徒。為簡(jiǎn)單起見，我們考慮這樣一種情況，即唯一可能的決定是“進(jìn)攻”或“撤退”。讓我們首先看看圖
- 司令是忠誠(chéng)的
? 圖1 中的場(chǎng)景，在這個(gè)場(chǎng)景中，指揮官是忠誠(chéng)的，并且發(fā)出了一個(gè)“攻擊”命令，但是中尉2 是一個(gè)叛徒，并且向中尉 1 報(bào)告他收到了一個(gè)“撤退”命令。為了滿足IC2 (所有忠誠(chéng)的副官都遵守同樣的命令)的要求，中尉 1 必須服從進(jìn)攻命令。
- 司令是叛徒
? 現(xiàn)在考慮另一個(gè)場(chǎng)景，如圖 2 所示，其中指揮官是一個(gè)叛徒，向中尉 1 發(fā)出一個(gè)“攻 擊”命令，向中尉 2 發(fā)出一個(gè)“撤退”命令。中尉 1 不知道誰是叛徒，他不能告訴什么信息的指揮官實(shí)際上發(fā)送給中尉 2。因此，這兩張圖片中的場(chǎng)景在中尉 1 看來完全相同。如果叛徒一貫說謊，那么中尉 1 就沒有辦法區(qū)分這兩種情況，所以他必須服從“攻擊”命令在他們兩個(gè)。因此，每當(dāng)中尉一號(hào)接到指揮官的“攻擊”命令時(shí)，他必須服從。
? 然而，一個(gè)類似的論點(diǎn)表明，如果中尉 2 接到指揮官的“撤退”命令，那么他必須服從命令，即使中尉 1 告訴他指揮官說“進(jìn)攻”。因此，在圖 2 的場(chǎng)景中，中尉 2 必須服從“撤退”命令，而中尉 1 服從“攻擊”命令，因此違反了條件 IC1。因此，三個(gè)將軍在一個(gè)叛徒面前工作是沒有解決辦法的。
? 這個(gè)論點(diǎn)可能看起來令人信服，但是我們強(qiáng)烈建議讀者對(duì)這種非嚴(yán)格的推理非常懷疑。雖然這個(gè)結(jié)果確實(shí)是正確的，但我們已經(jīng)看到了同樣似是而非的無效結(jié)果的“證明”.我們知道在計(jì)算機(jī)科學(xué)或數(shù)學(xué)中，沒有一個(gè)領(lǐng)域的非正式推理比這類算法的研究更容易導(dǎo)致錯(cuò)誤。為了嚴(yán)格證明可以處理單個(gè)叛逆者的三通解是不可能的，我們請(qǐng)讀者參考[3]。
? 利用這個(gè)結(jié)果，我們可以證明少于 3m+1 個(gè)將軍的解決方案不能應(yīng)付 m個(gè) 叛徒。更確切地說，三個(gè)或更多的將軍不存在這樣的解決方案，因?yàn)檫@個(gè)問題對(duì)兩個(gè)將軍來說是微不足道的。
? 解一組 3m 或更少的問題，然后用它構(gòu)造一個(gè)拜占庭將軍問題的三通解，這是我們知道不可能的。為了避免兩種算法之間的混淆，我們稱假設(shè)解的將軍為阿爾巴尼亞將軍，構(gòu)造解的將軍為拜占庭將軍。因此，從允許 300 萬或更少的阿爾巴尼亞將軍對(duì)付 300 萬叛徒的算法出發(fā)，我們構(gòu)造了一個(gè)允許三個(gè)拜占庭將軍對(duì)付一個(gè)叛徒的解決方案。
? 通過讓拜占庭的每一位將軍模擬大約三分之一的阿爾巴尼亞將軍，得到三個(gè)一般解，這樣每一位拜占庭將軍模擬的阿爾巴尼亞將軍最多不超過萬人。拜占庭指揮官模擬阿爾巴尼亞指揮官和最多 m-1 阿爾巴尼亞中尉，兩個(gè)拜占庭中尉模擬最多m 阿爾巴尼亞中尉。因?yàn)橹挥幸粋€(gè)拜占庭將軍可以成為叛徒，而且他假裝最多億阿爾巴尼亞人，最多億阿爾巴尼亞將軍是叛徒。因此，假定的解決辦法保證了 IC1 和IC2 對(duì)阿爾巴尼亞將軍們適用。通過 IC1，所有的阿爾巴尼亞中尉被忠誠(chéng)的拜贊廷中尉模仿，服從同樣的命令，這是他必須服從的命令。阿爾巴尼亞將軍解的 IC1 和IC2 條件是否暗示了拜占庭將軍解的相應(yīng)條件是很容易驗(yàn)證的，因此我們構(gòu)造了所需的不可能解。
? 有人可能會(huì)認(rèn)為，解決拜占庭將軍問題貿(mào)易協(xié)定的困難源于達(dá)成確切協(xié)議的要求。我們現(xiàn)在通過表明達(dá)成近似協(xié)議與達(dá)成確切協(xié)議同樣困難來證明情況并非如此。讓我們假設(shè)，將軍們不是試圖商定一個(gè)精確的作戰(zhàn)計(jì)劃，而是必須商定一個(gè)大約的進(jìn)攻時(shí)間。更確切地說，我們假設(shè)指揮官命令進(jìn)攻的時(shí)間，我們要求保持以下兩個(gè)條件：
? IC1’. 所有忠誠(chéng)的副官在 10 分鐘內(nèi)互相攻擊。
? IC2’.如果指揮官是忠誠(chéng)的，那么每個(gè)忠誠(chéng)的中尉都會(huì)在指揮官命令的 10 分鐘內(nèi)發(fā)動(dòng)攻擊。
(我們假設(shè)命令是在攻擊前一天發(fā)出和處理的，接收命令的時(shí)間與此無關(guān)——只是命令中給出的攻擊時(shí)間有關(guān)。)
? 像拜占庭將軍問題一樣，這個(gè)問題是無法解決的，除非超過三分之二的將軍是忠誠(chéng)的。我們首先證明了這一點(diǎn)，如果對(duì)付一個(gè)叛徒的三個(gè)將軍有一個(gè)解決方案，那么我們就可以構(gòu)造一個(gè)對(duì)付一個(gè)叛徒的拜占庭將軍問題的三個(gè)通用解決方案。假設(shè)指揮官希望發(fā)出“進(jìn)攻”或“撤退”的命令。他通過發(fā)送 1:00 的攻擊時(shí)間命令攻擊，并使用假定的算法發(fā)送 2:00 的攻擊時(shí)間命令撤退。每個(gè)中尉使用以下程序獲得他的命令。
? (1) 在收到指揮官的攻擊時(shí)間后，一名中尉做了以下事情之一:
? (a) 如果時(shí)間是 1:10 或更早，然后攻擊。
? (b) 如果時(shí)間是 1:50 或更晚，那么就撤退。
? ?否則，繼續(xù)步驟(2)。IC2`
? (2) 問問另一個(gè)中尉，他在第(1)步做了什么決定。
? (a)如果另一個(gè)中尉做出了決定，那么就做出和他一樣的決定。
? (b) 否則，就撤退。
? 根據(jù) IC2’，如果指揮官是忠誠(chéng)的，那么忠誠(chéng)的中尉將在步驟(1)中獲得正確的順序，因此 IC2 是滿意的。如果指揮官是忠誠(chéng)的，那么 IC1 就跟隨 IC2，所以我們只需要在指揮官是叛徒的假設(shè)下證明 IC1。因?yàn)樽疃嘀挥幸粋€(gè)叛徒，這意味著兩個(gè)副手都是忠誠(chéng)的。因此，如果一個(gè)中尉決定第(1)步進(jìn)攻，那么另一個(gè)中尉不能決定第(1)步撤退。因此，要么他們都會(huì)在步驟(1)中做出相同的決定，要么他們中至少有一個(gè)會(huì)推遲到步驟(2)再做決定。在這種情況下，很容易看到它們都得到了相同的決定，因此 IC1 是滿意的。因此，我們構(gòu)建了一個(gè)拜占庭將軍問題的三通解決方案來處理一個(gè)叛徒，這是不可能的。因此，我們不能有一個(gè)三通用的算法來維護(hù) ICI’和 IC2’的存在一個(gè)叛徒。
現(xiàn)在可以用一般模擬法證明少于 3m+1 的解決方案不能對(duì)付 m 個(gè)叛徒。這個(gè)證明與原始拜占庭將軍問題的證明相似，由讀者自己去證明。
3.口頭信息的解決方案
? 我們?cè)谏厦嬲故玖艘粋€(gè)用口頭信息來對(duì)付拜占庭將軍問題叛徒的解決方案，必須至少有 3 百萬+1 個(gè)將軍。我們現(xiàn)在給出了一個(gè)對(duì) 3 百萬+1 或更多的將軍有效的解決方案。然而，我們首先確切地說明“口頭信息”是什么意思。每個(gè)將軍都應(yīng)該執(zhí)行一些算法，包括向其他將軍發(fā)送消息，我們假設(shè)一個(gè)忠誠(chéng)的將軍正確地執(zhí)行他的算法。定義口頭信息體現(xiàn)在我們對(duì)將軍信息系統(tǒng)的下列假設(shè)中:
A1. 每條發(fā)送的信息都被正確傳遞。 A2. 信息的接收者知道是誰發(fā)送的。 A3. 可以檢測(cè)到消息的缺失。假設(shè) A1 和 A2 防止叛徒干擾其他兩位將軍之間的通訊，因?yàn)橥ㄟ^ A1 他不能干擾他們發(fā)送的信息，通過 A2 他不能通過引入虛假信息來混淆他們之間的交流。假設(shè) A3 將挫敗一個(gè)試圖僅僅通過不發(fā)送信息來阻止一個(gè)決定的叛徒。這些假設(shè)的實(shí)際應(yīng)用將在第 6 節(jié)中討論。
? 本節(jié)和下面的算法要求每個(gè)通用程序都能夠直接向其他通用程序發(fā)送消息。在第 5節(jié)中，我們描述了不具備這一要求的算法。叛國(guó)指揮官可以決定不下達(dá)任何命令。由于中尉們必須服從一些命令，在這種情況下，他們需要一些默認(rèn)命令來服從。我們讓 retreat 是這個(gè)默認(rèn)順序。
? 我們歸納性地定義了所有非負(fù)整數(shù)的口頭協(xié)議算法 OM(m)，通過這些算法，指揮官可以向 n-1 中尉發(fā)送命令。我們證明 OM(m)在最多 m 叛徒面前解決 3m+1 或更多的將軍的拜占庭將軍問題。我們發(fā)現(xiàn)用“獲得一個(gè)值”而不是“服從一個(gè)值”來描述這個(gè)算法更方便排序".
該算法假設(shè)函數(shù) majority 具有如下性質(zhì):如果大多數(shù)值 vi = v，則 majority(V1,…,Vn)=v .(實(shí)際上，它假定了一系列這樣的函數(shù)——每個(gè) n )對(duì)于函數(shù)majority(V1,…Vn)的值有兩個(gè)自然的選擇:
1. 如果大多數(shù)值中存在vi，否則為 retreat;2. 假設(shè)它們來自一個(gè)有序集合,選擇中位數(shù) vi 。下面的算法只需要上述的majority（）性質(zhì)。
Algorithm OM(0).
(1) 指揮官把他的價(jià)值傳遞給每個(gè)中尉。 (2) 每個(gè)中尉使用他從指揮官那里得到的價(jià)值，或者如果他沒有得到價(jià)值就使用 RETREAT。Algorithm OM(m), m > O
(1) 指揮官把他的價(jià)值傳遞給每個(gè)中尉。 (2)對(duì)每一個(gè)中尉i,令vi為中尉i收到的命令，如果沒有收到則使用撤退。中尉i作為算法OM(m-1) 的指揮官，發(fā)送vi給余下的n-2個(gè)將領(lǐng)。 (3)對(duì)每一個(gè) i和j(i！=j),令vj為第二步（2）將領(lǐng)i從將領(lǐng)j獲得的信息，如果沒有收到則使用撤退。將領(lǐng)i使用majority（v1 ,…,vn-1）的值作為最終命令值。? 為了理解這個(gè)算法是如何工作的，我們考慮 m=1，n=4 的情況。圖 3 展示了當(dāng)指揮官發(fā)送值v 而中尉 3 是叛徒時(shí)，中尉 2 接收到的消息。在 OM(1)的第一步中，指揮官向所有三名中尉發(fā)送 v。在第二步中，Lieutenant1 使用平凡算法 OM(0)將值 v 發(fā)送給 Lieutenant2。同樣在第二個(gè)步驟中，叛變的中尉 3 給中尉 2 一些其他的值 x。在步驟 3 中，中尉 2 然后有 v1=v2 和v3=x，所以他得到正確的value v = majority ( v , v, x) .值 v=majorty(v，v，x)。證明過程https://www.jianshu.com/p/538e6c9fac81
? 接下來，我們看看如果指揮官是叛徒會(huì)發(fā)生什么。圖 4 顯示了如果一個(gè)叛變的指揮官將三個(gè)任意值 x、y 和 z 發(fā)送給三個(gè)中尉，中尉們所接收到的值。每個(gè)中尉得到v1 = x, v2 = y, and v3 = z, 因此在步驟(3)中它們都得到相同的值majority(x，y，z)，不管這三個(gè)值 x，y 和 z 是否相等。
圖3：副官是叛徒
第一步：司令向每個(gè)副官發(fā)送他的值vvv給每個(gè)副官；
第二步：副官1執(zhí)行OM(0)，作為司令向副官2發(fā)送v；由于副官3是叛徒，其執(zhí)行OM(0)向副官2發(fā)送了不同的值，假設(shè)為x；
第三步：副官2擁有的行動(dòng)值集為{v1,v2,v3}={v,v,x}，采用majority函數(shù)，副官2采取的行動(dòng)v=majority{v1,v2,v3}
同理，副官1采取的行動(dòng)指令也是v，即滿足拜占庭將軍問題一致性條件IC1和IC2。
圖4：將軍是叛徒
第一步：司令為了阻止忠誠(chéng)副官達(dá)成一致，分別向三位副官發(fā)送值{x,y,z}{x, y, z}{x,y,z};
第二步：每個(gè)副官?gòu)乃玖钍盏降闹底鳛樽约旱闹?#xff0c;并執(zhí)行OM(0)向其他副官發(fā)送；
第三步：在第三步中，每個(gè)副官擁有的值集均為{x,y,z}{x, y, z}{x,y,z}，因此，副官執(zhí)行行動(dòng)函數(shù)majority得到的結(jié)果是一樣的。
由于三位忠誠(chéng)的將軍采取同樣的行動(dòng)，滿足拜占庭將軍一致性條件IC1。
**從m=1, n=4的例子可以看出，OM(m)算法能夠處理拜占庭將軍問題。遞歸算法 OM(m)調(diào)用算法 OM(m-1)的 n-1 個(gè)獨(dú)立執(zhí)行，每個(gè)執(zhí)行都調(diào)用 OM(m-2)等的 n- 2 個(gè)執(zhí)行。**這意味著，對(duì)于 m>1，一個(gè)中尉會(huì)給彼此發(fā)送許多不同的信息。必須有某種方法來區(qū)分這些不同的信息。讀者可以驗(yàn)證，如果每個(gè)中尉 i 在步驟(2)中將數(shù)字 i 前綴為他發(fā)送的值 vi，那么所有的模糊性都消除了。隨著遞歸的“展開”，算法 OM(m-k)將被調(diào)用(n-1)…(n-k)次，以發(fā)送一個(gè)以 k 中尉的數(shù)字序列為前綴的值。
**為了證明算法OM(m)，**對(duì)任意的m,的正確性。首先證明以下引理。
Lemma1. 對(duì)任意的m和k,如果將軍個(gè)數(shù)大于2k+m，有最多k個(gè)叛徒，算法 OM(m)滿足IC2 。
證明：針對(duì)m的取值情況進(jìn)行分析。
1.m= 0，忠誠(chéng)的將軍只要服從將軍的命令就可以了，引理成立。
2.假設(shè)m-1，m>0,時(shí)算法滿足IC2，證明對(duì)m 成立。（歸納法）
算法第一步（1），忠誠(chéng)的司令發(fā)送值v給n-1個(gè)將領(lǐng)。第二步（2），每一個(gè)忠誠(chéng)的將領(lǐng)調(diào)用算法OM(m-1)。
n>2k+m => n-1>2k+(m -1)>2k，多數(shù)的將領(lǐng)是忠誠(chéng)的，每一個(gè)忠誠(chéng)的將領(lǐng)得到一個(gè)vi=v 從n-1個(gè)值i中，在第三步majority(v1,…,vn-1)=v，滿足IC2.
證明算法成立的定理1：
Theorem1.對(duì)任意的m,在人數(shù)大于3m，有m個(gè)叛徒的情況下，算法OM(m)滿足條件IC1和條件IC2。
證明：針對(duì)m的取值情況進(jìn)行分析。
1.m= 0，定理成立。
2.假設(shè)m-1，m>0,時(shí)成立，證明對(duì)m 成立。（歸納法）
在司令忠誠(chéng)的情況下，令m=k,根據(jù)引理1可知，IC2成立從而IC1成立。
所以只需要證明司令是叛徒的情況。有最多m個(gè)叛徒，司令為其中一個(gè)，所以還有m-1個(gè)將領(lǐng)是叛徒。人數(shù)大于3m,所以將領(lǐng)人數(shù)大于3m-1。
3m-1>3(m-1)
使用歸納假設(shè)法證明OM(m-1)滿足條件CI1和CI2。因此，在第三步，對(duì)每一個(gè)j,任意兩個(gè)忠誠(chéng)的將軍獲得相同的值vj。從而任意兩個(gè)忠誠(chéng)的將軍獲得相同的值 在函數(shù)majority(v1,…,v**n-1)在第三步，IC1的證。
4.帶簽名信息的解決方案
正如我們?cè)趫D 1 和圖 2 中看到的場(chǎng)景，正是叛徒撒謊的能力使得拜占庭將軍問題變得如此困難。如果我們能夠限制這種能力，問題就會(huì)變得更容易解決。一種方法是允許將軍們發(fā)送不可偽造的簽名信息。更確切地說，我們?cè)?A1-A3以下假設(shè):
A4 (a) 忠誠(chéng)的將軍的簽名是不能偽造的，并且可以檢測(cè)到他簽名信息內(nèi)容的任何變更。(b) 任何人都可以核實(shí)將軍簽字的真實(shí)性。請(qǐng)注意，我們對(duì)叛國(guó)將軍的簽名不做任何假設(shè)。特別是，我們?cè)试S另一個(gè)叛徒偽造他的簽名，從而允許叛徒之間相互勾結(jié)。現(xiàn)在，我們已經(jīng)介紹了簽名信息，我們以前的論點(diǎn)，即四個(gè)將軍必須處理一個(gè)叛徒不再成立。事實(shí)上，確實(shí)存在三個(gè)通用解決方案。我們現(xiàn)在給出了一個(gè)算法，可以處理任意數(shù)量的將軍的萬叛徒。(如果少于 m+2 個(gè)將軍，問題就是空洞的。)
在我們的算法中，指揮官向每個(gè)副官發(fā)送一個(gè)簽名命令。然后每個(gè)中尉在命令上簽名，并將其發(fā)送給其他中尉，中尉再加上他們的簽名，然后再發(fā)送給其他人，如此類推。這意味著中尉必須有效地接收一條簽名信息，復(fù)制幾份，并簽名和發(fā)送這些副本。如何獲得這些副本并不重要;一條消息可能是復(fù)印的，或者每條消息可能由一堆相同的消息組成，這些消息根據(jù)需要進(jìn)行了簽名和分發(fā)。
算法定義一個(gè)選擇函數(shù)choice,其在一個(gè)集合命令信息中選出一個(gè)，如下：
1.如果集合V只有一個(gè)值v,Choice(V) = v。2.choice(?) = RETREAT(撤退)?？占闆r下。? 可以注意到，可選擇中值為函數(shù)的值。
定義
x:i 表示被將軍i簽名的值x ，則v:j:i 表示值v被將軍j簽名以后，然后又被將軍i簽名。令將軍0號(hào)為命令的發(fā)送者。在算法里每一個(gè)將領(lǐng)i都有一個(gè)集合Vi ,集合里面包括他收到的被其他將軍簽名的信息。
算法SM(m).
初始化 Vi =?.
(1)司令發(fā)送其簽名信息v:0給每一個(gè)將領(lǐng)。
(2)對(duì)每一個(gè)將領(lǐng)i ：
(A)如果將領(lǐng) i 收到從司令v:0，且其Vi =?。 其操作如下：
? (i)他令其Vi ={v}；
? (ii)他發(fā)送v:0：i給每一個(gè)其他的將領(lǐng).
? (B)如果將領(lǐng) i 收到信息v:0：j1:…:jk ,且v?Vi，則：
? (i)他將v加入自己的集合Vi；
? (ii)如果k<m,則其發(fā)送v:0：j1:…:jk:i 給其他的將領(lǐng)?j1，…，jk。
(3)對(duì)每一個(gè)將領(lǐng)i ：當(dāng)將領(lǐng)i 不再收到信息后，其遵守choice(Vi)
注意，在第二步中，副官i將忽略任意值已經(jīng)在Vi出現(xiàn)的消息。通過對(duì)k的歸納，對(duì)于每個(gè)副官序列j1,…,jk , 且k<m，每個(gè)副官至多收到一條v:0:j1:…:jk 消息。在第(3)步中可以使用超時(shí)來判斷沒有消息再回到來。
舉例： m=1, n=3
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-AXBM88Aw-1587040554637)(https://hongery.github.io/images/bft/bft4.png)]
在第(1)步，司令發(fā)送發(fā)送“attack”給副官1并發(fā)送“retreat”給副官2；
在第(2)步，每個(gè)副官將收到兩個(gè)命令值，即V1=V2={"attack","retreat"}
在第(3)步，兩個(gè)忠誠(chéng)的副官執(zhí)行choice(Vi得到的結(jié)果也是一樣的。
因此，當(dāng)司令叛徒時(shí)，算法滿足條件IC1。
當(dāng)司令是忠誠(chéng)的時(shí)，叛徒副官無法篡改司令的命令，因此忠誠(chéng)的副官的行動(dòng)值集Vi只有一個(gè)元素，即司令發(fā)送的命令。因此，SM(m)算法滿足條件IC1和IC2。
定理2.對(duì)任意的m，在至多m個(gè)叛徒的情況下，算法SM(m)解決拜占庭問題。
證明，在司令是忠誠(chéng)的情況下，沒有信息可被篡改。顯然成立。
在司令是叛徒的情況下，需要證明IC1成立，則任意兩個(gè)忠誠(chéng)的將領(lǐng)i和j將遵循第三步獲得的一致的命令。所以必須證明 將領(lǐng)i和j在第二步將相同的命令信息放進(jìn)自己的集合。情況分析,可得有以下兩種情況，如果將軍i獲得信息v,他把信息發(fā)送給將軍j。如果將軍i獲得信息v：0：j1:…:jk ，且j在簽名當(dāng)中，則j已經(jīng)把值v放進(jìn)自己的集合。如果j不在簽名當(dāng)中,分析兩種情況：
證明結(jié)束。
5.通訊路徑缺失
? 到目前為止，我們假設(shè)一個(gè)將軍可以直接向其他所有將軍發(fā)送消息。我們現(xiàn)在移除這個(gè)假設(shè)。相反，我們認(rèn)為物理障礙對(duì)誰可以向誰發(fā)送信息設(shè)置了一些限制。我們認(rèn)為將軍構(gòu)成一個(gè)簡(jiǎn)單的 2 個(gè)有限無向圖 g 的節(jié)點(diǎn)，其中兩個(gè)節(jié)點(diǎn)之間的弧表示這兩個(gè)將軍可以發(fā)送消息
2 一個(gè)簡(jiǎn)單圖是這樣一個(gè)圖，其中最多有一條弧連接任意兩個(gè)節(jié)點(diǎn)，每條弧連接兩個(gè)不同的節(jié)點(diǎn)。
接下來 對(duì)算法OM(m)和SM(m)進(jìn)行拓展，G 為全聯(lián)通圖。
首先對(duì)算法OM(m)進(jìn)行拓展，給出以下定義：
定義1.
(a)節(jié)點(diǎn)集合{i1 ,…,ip}為節(jié)點(diǎn)i的正則鄰接集，滿足：
(i)每一個(gè)i j都鄰接點(diǎn) i
(ii)對(duì)任意的將軍 k （k 和 i 不相等），則有路徑 γj,k ,從 ij 到 k 無需通過 i，且任意兩條路徑 γj,k 除了節(jié)點(diǎn) k 沒 有共同節(jié)點(diǎn)。
(b)圖 G 是 p正則的 ，如果每個(gè)節(jié)點(diǎn)的正則集都有 p 個(gè)不同的節(jié)點(diǎn)。
如圖所示，圖六是 3-正則圖，每個(gè)節(jié)點(diǎn)有三個(gè)度（三條邊）。
圖七 不是 3-正則圖 ，中間節(jié)點(diǎn)有四條邊。
[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來直接上傳(img-fRvdNybD-1587040554654)(https://hongery.github.io/images/bft/bft5.png)]
拓展的OM(m,p)算法
m個(gè)叛徒 ，G 為 3-正則圖。（注意到， 3m-正則圖 必至少含有 3m +1 個(gè)節(jié)點(diǎn) ）。對(duì)任意的正整數(shù) m , p 。且將軍通信情況構(gòu)成 p-正則圖。通過分析 m 如下：
算法 OM(m,p).
(0)選擇司令（commander）的正則鄰接集 N (含有 p 個(gè) 將領(lǐng))。p為3
(1) 司令將信息發(fā)送給集合 N 里的每一個(gè)將領(lǐng)。
(2)對(duì)每一個(gè) i ∈ N ，令 vi 為 將領(lǐng) i 收到的從司令發(fā)過來的命令，或者沒有收到信息則默認(rèn)為 撤退 （RETREAT）。將領(lǐng) i 按照以下規(guī)則將 vi 發(fā)送給其他將領(lǐng) k：
(A) 如果 m = 1 通過路徑 γj,k 發(fā)送信息，路徑存在定義1由(a)(ii)保證.
(B)如果 m > 1 ,則 將領(lǐng) i扮演司令的角色在OM(m-1,p-1)，圖由去掉原先的司令構(gòu)成。
(3)對(duì) 每一個(gè) k ，和 i ∈ N ， k ≠ i 。令 vi 為將領(lǐng) k 從 i （i 在第二步（2））） 收到的信息，或者 RETREAT 如 果沒有收到信息。將領(lǐng) k 使用 函數(shù)值 majority(vi，… ,v ~i p~), N = {i1 ，… , ip }.
接下來證明 在至多 m 個(gè)叛徒的情況下 ，OM(m,3m) 解決拜占庭將軍問題 。首先對(duì)引理1 進(jìn)行拓展（見 一）。
定理2：
Lemma 2 .對(duì)任意的 m >0 和任意的 p ≥ 2k + m ，如果至多有 k 個(gè)叛徒 ，算法 OM(m,p)滿足條件IC2(見一)。
證明
? 當(dāng) m = 1, 注意到 一個(gè)將領(lǐng)獲得的值 majority(v1，… ,v p) 中，每一個(gè) vi 的命令發(fā)送者是通過不相交的路徑發(fā)送的信息。且至多有 k 個(gè)叛徒. 在 p ≥ 2k + m 的情況下知道 忠誠(chéng)將軍的人數(shù)超過半數(shù)。當(dāng)將軍是忠誠(chéng)的情況下，算法保證IC2 從而的證。運(yùn)用歸納法可得對(duì) m -1, m >1 .引理成立。
繼續(xù)證明…
定理 3：
Theorem 3. 對(duì)任意的 m >0 和對(duì)任意的 p ≥ 3m ,在至多 m 叛徒的情況下 ，算法OM(m,p) 解決拜占庭問題。
證明。根據(jù)引理2，令 k = m ,可知算法滿足IC2，在司令是忠誠(chéng)的情況下。現(xiàn)在只需要證明司令為叛徒的情況。假設(shè)所有忠誠(chéng)的將領(lǐng)再第三步（3）要獲得一致的值 v i 集合.
? 如果 m = 1,則所有將領(lǐng)都是忠誠(chéng)的，成立。
? 如果 m >1 ,簡(jiǎn)單的歸納 p ≥ 3m 可得 p -1 ≥ 3 (m -1) ，算法成立。
? 證畢。
算法假設(shè)圖G 為3-正則 ，是一個(gè)條件很強(qiáng)的連通假設(shè)。事實(shí)上當(dāng)總共有3m +1人時(shí)，3 m-正則意味著全連通，算法OM(m,3m) 可推出 OM(m）?？梢钥闯?#xff0c;拓展算法 SM(m) 只需要更弱的連通條件。
? 分析多少連通條件能解決拜占庭問題。IC2 要求 忠誠(chéng)的將領(lǐng)服從忠誠(chéng)的司令，這要求他們之間要能夠通信。特別地，當(dāng)每一條信息都會(huì)通過一個(gè)叛徒中轉(zhuǎn)的時(shí)候，不能保證將領(lǐng)能獲得司令的信息。類似的，如果兩個(gè)將領(lǐng)只能通過有叛徒的路徑通信則IC1無法保證。
拜占庭將軍的弱連通假設(shè)為，忠誠(chéng)將軍構(gòu)成的G 的子圖要互相連接。在這個(gè)條件下，總?cè)藬?shù)為 n ，不管叛徒的個(gè)數(shù)，算法 SM(n-2)成立。
接下來證明更加普遍的結(jié)果。定義一個(gè)圖的半徑為最小的數(shù) d ,任意兩個(gè)節(jié)點(diǎn)相連至多需要 d 條邊。
定理4.
Theorem4. 對(duì)任意的 m 和 d ,如果有 m 個(gè)叛徒且 忠誠(chéng)將軍構(gòu)成的子圖有直徑 d, 則 SM(m + d - 1) 解決拜占庭問題。
證明和定理2的證明類似（略）。
推論.如果忠誠(chéng)將軍構(gòu)成的子圖是連接的，則 SM(n - 2)可解決拜占庭問題。
證明，令 d 為忠誠(chéng)將軍構(gòu)成的圖的直徑。且已知 d 小于 節(jié)點(diǎn)數(shù)，所以忠誠(chéng)將軍的人數(shù)大于d ，叛徒人數(shù)少于 n - d 。令 m = n - d -1 可的證。
可靠的系統(tǒng)大多使用多數(shù)票方法保證可靠性，其使用多個(gè)處理器得出一致的結(jié)果，然后使用多數(shù)票表決的方法得到單個(gè)值。
使用多數(shù)票方法是基于假設(shè)不出錯(cuò)的處理器將得到一致的結(jié)果。這在它們獲得一致的輸入時(shí)成立。其基于假設(shè)出錯(cuò)的處理器不會(huì)得到一致的錯(cuò)誤結(jié)果。但是也有很多其他的情況，無法獲得一致的輸入，比如出錯(cuò)的程序發(fā)送不同的值給其他處理器。比如獲取時(shí)鐘值的時(shí)候，很難保證兩個(gè)處理器獲取相同的值等等。所以給出以下前提條件：
1.所有無故障的處理器使用相同的輸入。（可以獲得相同的輸出）
2.如果只輸入單元無故障，那么所有無故障的處理器要使用其提供的值作為輸入。
這里，司令是作為 輸入值的提供者，將領(lǐng)是處理器，忠誠(chéng)為無故障。
6.可靠的系統(tǒng)
? 除了使用本質(zhì)上可靠的電路元件，我們知道實(shí)現(xiàn)一個(gè)可靠的計(jì)算機(jī)系統(tǒng)的唯一方法是使用幾個(gè)不同的“處理器”來計(jì)算相同的結(jié)果，然后對(duì)它們的輸出進(jìn)行多數(shù)表決，以獲得一個(gè)單一的值。(投票可以在系統(tǒng)內(nèi)進(jìn)行，也可以由輸出的用戶在外部進(jìn)行。)無論是使用冗余電路來防止單個(gè)芯片故障的可靠計(jì)算機(jī)，還是使用冗余計(jì)算站點(diǎn)來防止單個(gè)站點(diǎn)被核攻擊破壞的彈道導(dǎo)彈防御系統(tǒng)，都是如此。唯一的區(qū)別在于復(fù)制的“處理器”的大小。
使用多數(shù)表決來實(shí)現(xiàn)可靠性是基于所有非故障處理器將產(chǎn)生相同的輸出的假設(shè)。只要它們都使用相同的輸入，這就是正確的。然而，任何單個(gè)輸入數(shù)據(jù)都來自單個(gè)物理元件——例如，來自可靠計(jì)算機(jī)中的其他電路，或者來自導(dǎo)彈防御系統(tǒng)中的某個(gè)雷達(dá)站點(diǎn)——和一個(gè)故障定位元件，可以為不同的處理器提供不同的值。此外，不同的處理器可以獲得不同的值，甚至從一個(gè)非故障的輸入單元，如果他們讀取的值，而它正在變化。例如，如果兩個(gè)處理器在時(shí)鐘前進(jìn)時(shí)讀取時(shí)鐘，那么一個(gè)處理器可能獲得舊時(shí)間，另一個(gè)處理器獲得新時(shí)間。這只能通過與時(shí)鐘推進(jìn)同步讀操作來防止。可靠的制度，必須滿足以下兩個(gè)條件:
所有非故障處理器必須使用相同的輸入值(因此它們產(chǎn)生相同的輸出)。
如果輸入單元是非故障的，那么所有非故障進(jìn)程都使用它提供的值作為輸入(因此它們產(chǎn)生正確的輸出)。
這些只是我們的交互式一致性條件 IC1 和 IC2，其中“指揮官”是產(chǎn)生輸入的單位，“中尉”是程序，“忠誠(chéng)”意味著沒有錯(cuò)誤。
? 嘗試用“硬件”解決方案來規(guī)避這個(gè)問題是很誘人的。例如，可以嘗試通過讓所有處理器都從相同的線路讀取輸入值來確保所有處理器獲得相同的輸入值。然而，一個(gè)錯(cuò)誤的輸入單元可以沿著線路發(fā)送一個(gè)邊際信號(hào)----這個(gè)信號(hào)可以被某些處理器解釋為 0，而其他處理器可以解釋為 1。沒有辦法保證不同的處理器將從一個(gè)可能出錯(cuò)的輸入設(shè)備獲得相同的值，除非讓處理器相互通信來解決拜占庭將軍問題。
? 當(dāng)然，有故障的輸入設(shè)備可能提供無意義的輸入值。一個(gè)拜占庭將軍解決方案所能做的就是保證所有處理器使用相同的輸入值。如果輸入是重要的，那么應(yīng)該有幾個(gè)獨(dú)立的輸入設(shè)備提供冗余值。例如，在導(dǎo)彈防御系統(tǒng)中應(yīng)該有冗余雷達(dá)和冗余處理站點(diǎn)。然而，冗余輸入不能實(shí)現(xiàn)可靠性，仍然需要確保非故障處理器使用冗余數(shù)據(jù)產(chǎn)生相同的輸出。
? 如果輸入設(shè)備是非故障的，但是由于它在值變化時(shí)被讀取而給出不同的值，我們?nèi)匀幌Ｍ枪收咸幚砥鳙@得一個(gè)合理的輸入值?？梢宰C明，如果多數(shù)函數(shù)和選擇函數(shù)都是中值函數(shù)，那么我們的算法具有這樣的性質(zhì)，即非故障處理器獲得的值在輸入單元提供的值范圍之內(nèi)。因此，只要輸入單元產(chǎn)生合理的值范圍，非故障處理器將獲得合理的值。
? 我們已經(jīng)給出了幾種解決方案，但是它們都是用拜占庭式的將軍而不是用計(jì)算系統(tǒng)來表述的。我們現(xiàn)在研究如何將這些解決方案應(yīng)用于可靠的計(jì)算系統(tǒng)。當(dāng)然，用處理器實(shí)現(xiàn)“通用”算法是沒有問題的。問題在于實(shí)現(xiàn)滿足 A1-A3(算法 SM(m)的 A1-A4 假設(shè))假設(shè)的消息傳遞系統(tǒng)。我們現(xiàn)在按順序考慮這些假設(shè)。
A 1。假設(shè) A1 指出，沒有錯(cuò)誤的處理器發(fā)送的每條消息都是正確的。
在實(shí)際系統(tǒng)中，通信線路可能會(huì)失靈。對(duì)于口信算法 OM(m)和 OM(m，p)，連接兩個(gè)處理器的通信線路的故障與其中一個(gè)處理器的故障是無法區(qū)分的。因此，我們只能保證這些算法將工作在存在多達(dá)億故障，無論是處理器或通信線路故障。(當(dāng)然，連接到同一個(gè)處理器的多條通信線路的故障相當(dāng)于單個(gè)處理器的故障。)如果我們假設(shè)失敗的通信線路不會(huì)導(dǎo)致偽造有符號(hào)消息——我們將在下面看到這個(gè)假設(shè)是相當(dāng)合理的，那么我們的有符號(hào)消息算法 SM(m)對(duì)通信線路失敗不敏感。更準(zhǔn)確地說，定理 4 即使在通信線路故障的情況下仍然有效。失敗的通信線路與簡(jiǎn)單地刪除通信線路具有同樣的效果——它降低了處理器圖形的連接性。
A 2。假設(shè) A2 指出，處理器可以確定它所接收的任何消息的發(fā)出者。
實(shí)際上需要的是有故障的處理器不能模擬一個(gè)沒有故障的處理器。在實(shí)踐中，這意味著進(jìn)程間通信是通過固定的線路而不是通過某些報(bào)文交換網(wǎng)絡(luò)進(jìn)行的。(如果使用交換網(wǎng)絡(luò)，那么必須考慮有故障的網(wǎng)絡(luò)節(jié)點(diǎn)，然后拜占庭將軍問題節(jié)點(diǎn)再次出現(xiàn)。)請(qǐng)注意，如果假設(shè)A4 并且所有消息都有簽名，則不需要假設(shè) A2，因?yàn)槟M另一個(gè)處理器將意味著偽造其消息。
A 3。假設(shè) A3 要求可以檢測(cè)到消息的缺失。
消息的缺失只能通過其未能在某個(gè)固定時(shí)間內(nèi)到達(dá)來檢測(cè)——換句話說，通過使用某種超時(shí)限制。使用超時(shí)來滿足 A3 需要兩個(gè)假設(shè):
生成和傳輸消息所需的最長(zhǎng)時(shí)間是固定的。
發(fā)送方和接收方都有時(shí)鐘，這些時(shí)鐘在某個(gè)固定的最大誤差范圍內(nèi)同步。
第一個(gè)假設(shè)的必要性是相當(dāng)明顯的，因?yàn)榻邮苷弑仨氈浪枰榷嗑貌拍苁盏较ⅰ?生成時(shí)間是處理器在接收到生成消息所需的所有輸入之后發(fā)送消息所需的時(shí)間。)第二個(gè)假設(shè)的必要性就不那么明顯了。然而，可以證明這個(gè)假設(shè)或者一個(gè)等價(jià)的假設(shè)對(duì)于解決拜占庭將軍問題問題是必要的。更確切地說，假設(shè)我們?cè)试S算法，將軍們只在下列情況下采取行動(dòng):
在某個(gè)固定的初始時(shí)間(所有的將軍都一樣)。
在收到信息后。
當(dāng)一段隨機(jī)選擇的時(shí)間過去時(shí)。(也就是說，一個(gè)普通人可以將計(jì)時(shí)器設(shè)置為一個(gè)隨機(jī)值，并在計(jì)時(shí)器結(jié)束時(shí)行動(dòng)。)
{這產(chǎn)生了我們可以想象到的最一般的算法類別，它們不允許構(gòu)造同步的時(shí)鐘。)可以證明，如果消息可以任意快速地傳遞，即使存在消息傳遞延遲的上界，這種算法也不能解決拜占庭將軍問題問題。而且，即使我們限制叛徒，只允許他們不正確的行為是不發(fā)送信息，也不可能有解決辦法。這個(gè)結(jié)果的證明超出了本文的范圍。請(qǐng)注意，在傳輸延遲上設(shè)置一個(gè)下限和一個(gè)上限，將使處理器通過來回發(fā)送消息來實(shí)現(xiàn)時(shí)鐘。
? 以上兩個(gè)假設(shè)使得檢測(cè)未發(fā)送的消息變得容易。假設(shè)/z 是最大的消息生成和傳輸延遲，并且假設(shè)沒有故障的處理器的時(shí)鐘在任何時(shí)候最多相差 t。然后，任何非故障進(jìn)程應(yīng)該開始在其時(shí)鐘上按時(shí)間 t 生成的消息將在接收方時(shí)鐘上的時(shí)間 t+#+t 到達(dá)其目的地。因此，如果接收者到那時(shí)還沒有接收到消息，那么它可能假設(shè)消息沒有被發(fā)送。(如果它晚一點(diǎn)到達(dá)，那么發(fā)送者一定是錯(cuò)誤的，因此我們的算法的正確性并不取決于發(fā)送的消息。)通過對(duì)輸入處理器發(fā)送其值的時(shí)間進(jìn)行 fLxing，可以計(jì)算出處理器在自己的時(shí)鐘上必須等待每條消息的時(shí)間。例如，在算法 SM(m)中，處理器必須等到對(duì)于任何有+ k(# +~) 簽名的消息，其中 To 是指揮官開始執(zhí)行算法的時(shí)間(在他的時(shí)鐘上)。沒有兩個(gè)時(shí)鐘以完全相同的速率運(yùn)行，所以無論最初處理器的時(shí)鐘同步得多么精確，它們最終會(huì)偏離得任意遠(yuǎn)，除非它們周期性地重新同步。因此，我們面臨的問題是，即使有些處理器出現(xiàn)故障，也要保持處理器的時(shí)鐘同步到某個(gè)固定的數(shù)量。這是一個(gè)和拜占庭將軍問題本身一樣困難的問題。時(shí)鐘同步問題的解決方案與我國(guó)拜占庭式的解決方案密切相關(guān)。它們將在未來的論文中加以描述。
A 4。假設(shè) A4 要求處理器能夠以這樣一種方式對(duì)其消息進(jìn)行簽名，即不能偽造沒有錯(cuò)誤的處理器簽名。
簽名是由進(jìn)程 i 從數(shù)據(jù)項(xiàng) m 生成的一段冗余信息 Si(m)。由 i 簽名的消息由一對(duì)(m，Si(m))組成。滿足部分(a)和(b)對(duì)于 A4，Si 函數(shù)必須具有以下兩個(gè)性質(zhì):
? (a)如果處理器 i 是非故障的，那么沒有故障的處理器可以生成 Si(m)。
? (b)給定 M 和 X，任何過程都可以確定 ifX 等于 Si(m)。
屬性(a)永遠(yuǎn)不能得到保證，因?yàn)?Si(m)只是一個(gè)數(shù)據(jù)項(xiàng)，故障處理器可能生成任何數(shù)據(jù)項(xiàng)。然而，我們可以使違反它的概率小到我們所希望的程度，從而使系統(tǒng)如我們所希望的那樣可靠。如何做到這一點(diǎn)取決于我們預(yù)期會(huì)遇到的故障類型。有兩個(gè)令人感興趣的案例:
1.隨機(jī)故障。通過使Si 成為一個(gè)適當(dāng)?shù)摹半S機(jī)化”函數(shù)，我們可以使處理器中的一個(gè)隨機(jī)故障產(chǎn)生正確簽名的概率本質(zhì)上等于它通過一個(gè)隨機(jī)選擇過程產(chǎn)生正確簽名的概率**——即可能簽名數(shù)目的倒數(shù)。下面是一個(gè)實(shí)現(xiàn)這一點(diǎn)的方法。假設(shè)消息被編碼為小于 p 的正整數(shù)，其中 p 是 2 的冪。設(shè) Si(m)等于 m Ki mod p，其中 Ki 是小于 p 的一個(gè)隨機(jī)選擇的奇數(shù)。如果另一個(gè)處理器的內(nèi)存中沒有 Ki，那么它為單個(gè)(非零)消息 m 生成正確簽名 m*Ki 的概率應(yīng)該是 l/p:它通過隨機(jī)選擇生成正確簽名 mKi *的概率。(**注意，如果處理器可以通過一些簡(jiǎn)單的程序獲得 Ki，那么在計(jì)算時(shí)用Ki 代替 k，可能會(huì)有更大的可能性出現(xiàn)處理器錯(cuò)誤地偽造 i 的簽名 Sj(M).)律政司(m))
2.惡意情報(bào)。如果錯(cuò)誤的處理器被惡意的智能引導(dǎo)*----例如，如果一個(gè)完美的處理器被一個(gè)試圖破壞系統(tǒng)的人操作**----那么信號(hào)函數(shù)* Si 的構(gòu)造就成了一個(gè)密碼學(xué)問題。我們建議讀者參閱[1]和[4]來討論如何解決這個(gè)問題。
請(qǐng)注意，如果進(jìn)程已經(jīng)看到簽名，則很容易生成簽名 Si(m)。因此，重要的是，相同的消息永遠(yuǎn)不必被簽名兩次。這意味著，當(dāng)重復(fù)使用 SM(m)分發(fā)一個(gè)值序列時(shí)，序列號(hào)應(yīng)該附加到值上以保證唯一性。
7.結(jié)論
? 在各種假設(shè)下，我們已經(jīng)向拜占庭將軍問題提出了幾種解決方案，并展示了如何使用它們來實(shí)現(xiàn)可靠的計(jì)算機(jī)系統(tǒng)。這些解決方案在時(shí)間量和所需的消息數(shù)量上都很昂貴。算法 OM(m)和 SM(m)都要求消息路徑的長(zhǎng)度達(dá)到 m+1。換句話說，每個(gè)中尉可能不得不等待來自指揮官的信息，然后通過其他名中尉轉(zhuǎn)發(fā)。費(fèi)舍爾和林奇已經(jīng)證明，這對(duì)任何可以對(duì)付萬叛徒的解決方案都是正確的，所以我們的解決方案在這方面是最佳的。對(duì)于不完全連通的圖，我們的算法需要長(zhǎng)度為 m+d 的消息路徑，其中 d 是忠誠(chéng)將軍子圖的直徑。我們認(rèn)為這也是最佳選擇。
? 算法 OM(m)和 SM(m)包括發(fā)送到(n-1)(n-2)…。(n-m-1)信息。通過組合消息，必然可以減少所需的單獨(dú)消息的數(shù)量。也許還可以減少傳輸?shù)男畔⒘?#xff0c;但這一點(diǎn)尚未得到詳細(xì)研究。但是，我們預(yù)計(jì)仍然需要大量的消息。
? 在任意故障的情況下實(shí)現(xiàn)可靠性是一個(gè)困難的問題，其解決方案似乎本身就代價(jià)高昂。降低成本的唯一方法是對(duì)可能發(fā)生的故障類型進(jìn)行假設(shè)。例如，通常假設(shè)計(jì)算機(jī)可能無法響應(yīng)，但是絕不會(huì)錯(cuò)誤響應(yīng)。然而，當(dāng)需要極高的可靠性時(shí)，這樣的假設(shè)是不可能做出的，并且需要一個(gè)拜占庭將軍解決方案的全部費(fèi)用。
總結(jié)
- 上一篇： Python库collections中的
- 下一篇： 计算机鼠标老跳动,用win10系统，鼠标