5.領導者選舉算法

 

許多分布式算法需要一個特殊的過程，它具有領導者作為協(xié)調者或發(fā)起者的角色。哪個過程是領導者，唯一過程是否可以成為領導者是一個重要問題，研究人員在過去幾十年中一直在努力。

 

5–1. 欺負算法

 

當協(xié)調員失敗并且任何進程P注意到該情況時，P根據(jù)以下過程激活選舉。

 

· P向所有具有比其自身更高數(shù)值的進程發(fā)送ELECTION消息。

 

· 如果沒有人回復，P將贏得選舉并成為協(xié)調員。

 

· 如果來自具有高于P的數(shù)值的過程的答案，則將替換它。 P的工作結束了。

 

使用該算法，可以唯一地確定協(xié)調器。但是，該算法需要大量的消息和數(shù)據(jù)流量，可以說是冗余的。作為替代方案，存在環(huán)算法。

 

5–2. 環(huán)算法

 

與一般環(huán)算法不同，該算法不使用Token。發(fā)現(xiàn)協(xié)調器不工作的任何進程構造一個包含其自己的進程號的ELECTION消息，并將該消息發(fā)送給其后繼者（環(huán)網中的下一個節(jié)點）。如果繼任者失敗，請?zhí)^。如果沒有比您更高的數(shù)值的節(jié)點，您的消息將仍然返回給您自己的進程號，因此它將被指定為協(xié)調員。

 

在該算法中，執(zhí)行具有減少數(shù)量的消息的領導者選舉，但是還可以通過將消息的目的地設置到兩個相鄰節(jié)點來實現(xiàn)具有較少量數(shù)據(jù)流量的算法。

 

6.阻止鏈和同步作為分布式系統(tǒng)

 

因此，在作為分布式系統(tǒng)之一的塊鏈中，進程之間的同步如何發(fā)生？

 

6–1. 區(qū)塊鏈和時鐘同步

 

塊鏈和邏輯時鐘

 

首先，考慮是否可以使用區(qū)塊鏈中的物理時鐘來掌握絕對時間關系。如第2章所述，參與網絡的每個節(jié)點并不總是保持正確的物理時鐘，并且應該存在時鐘偏差。由于比特幣區(qū)塊鏈的平均生成時間是10分鐘，因此認為即使一定程度的大時鐘偏差也是可接受的。然而，當節(jié)點散布在世界各地時難以同步各個物理時鐘，并且還可能存在偽裝時鐘的節(jié)點。通過引入網絡時間協(xié)議（NTP）來重新同步節(jié)點之間的正確時間是一項困難的技術。

 

區(qū)塊鏈和邏輯時鐘

 

因此，準備邏輯時鐘而不是物理時鐘是切合實際的。實際上，通過在塊中加入時間標記，可以制備出與Lamport邏輯時鐘非常相似的機制。

 

如［比特幣：點對點電子現(xiàn)金系統(tǒng)Satoshi Nakamoto］中所述，對作為礦工的區(qū)塊執(zhí)行寫操作的每個節(jié)點本身具有作為時間戳服務器的角色。每個時間戳通過在其哈希中包含前一個時間戳來形成鏈。但是，無法保證這些節(jié)點保持正確的物理時鐘。時間戳的數(shù)值，即每個事務的順序和時間相對模糊。

 

由于時鐘的這種模糊性，有可能會進行雙重付款。但是，在比特幣區(qū)塊鏈中，只有最長的鏈是合法的，在次要驗證后丟棄不正確的交易。因此，區(qū)塊的順序隨著時間的流逝唯一確定。隨著每個時間戳的增加，前一個時間戳被加強。

 

總之，在區(qū)塊鏈中的模糊時間戳下，事務的順序一致性是不準確的。然而，利用鏈式連接的簡單機制，每個交易的發(fā)生前關系隨著時間的推移而建立。此外，還有一種激勵結構，以便礦工轉移到良好，交易不一致的順序不會發(fā)生。

 

可以說，實現(xiàn)類似于Lamport的邏輯時鐘的時鐘同步方法，因為事務之間的相對順序關系，即發(fā)生在之前的關系變得更清楚。

 

對于大多數(shù)交易，沒有因果關系，因此如果您引入向量時鐘并采用因果關系排序的概念，則可以極大地放松訂單關系的約束。然而，在區(qū)塊鏈中，由于結構本身默認共享所有塊的順序關系，所以保持總排序（相對于在一段時間之后的塊）。

 

6–2. 區(qū)塊鏈和獨占控制算法

 

即使在作為分布式系統(tǒng)的區(qū)塊鏈中，也需要排除控制。在區(qū)塊鏈網絡中，每個節(jié)點并行地異步操作。此時，要共享的區(qū)塊鏈本身的信息不應該不一致。

 

PoW·PoS中的獨占控制算法

 

如第4章所述，分布式排他控制算法可分為以下兩種類型。

 

· 基于Token的解決方案

 

· 基于權限的解決方案

 

PoW和PoS是基于權限的，其中，可以說它是類似于分布式算法的機制。那么，您什么時候獲得訪問資源的權限？是的，就在你找到一個隨機數(shù)時。

 

在PoW中，只有當找到在哈希值后跟0后跟n為0的隨機數(shù)時，才可以執(zhí)行有效的新塊寫操作。執(zhí)行操作的礦工將其廣播給所有礦工并分享。

 

通常，當節(jié)點找到一個nonce并創(chuàng)建一個比他自己更早的塊時，minor會同步該信息并移動以搜索下一個nonce值。這是因為如果您使用最長鏈被認為合法的規(guī)則搜索下一個nonce值，它們可以獲得更多利潤。盡管PoS優(yōu)先為具有較大硬幣持有量的人提供資源訪問，但基本排除控制算法結構也類似于分布式算法。

 

但是，嚴格來說，不執(zhí)行排除控制。這是為了在公共時間內同步并形成共識10分鐘，直到下一個區(qū)塊為止。當兩個或更多個節(jié)點同時找到隨機數(shù)值時，寫入操作以非獨占狀態(tài)執(zhí)行。此時，由于只有最長的鏈被認為是合法的，因此區(qū)塊鏈網絡中的信息與時間的流逝保持一致。叉子發(fā)生的一個問題是因為沒有執(zhí)行嚴格的排他控制而且沒有確認最終結果。

 

BFT類型的獨占控制算法

 

另一方面，通過BFT類型，基于許可的分散算法執(zhí)行排他控制。該算法解決了分叉和終結問題，這是PoW中與分布式算法類似的問題。

 

在BFT類型中，只有一個名為Proposer，Orderer等的節(jié)點有權生成新區(qū)塊。創(chuàng)建區(qū)塊時，您可以從所有參與節(jié)點收集投票，獲得超過2/3的同意，您才有權創(chuàng)建新塊。此時，有必要同意超過2/3而不是多數(shù)的原因是處理拜占庭故障，有關此問題的詳細信息在“分布式系統(tǒng)中的容錯”一文中有所描述。

 

在BFT類型算法中，與PoW等不同，只有一個節(jié)點可以獲得對區(qū)塊鏈的獨占訪問權限，因此不會立即確定fork和finality。但是，任何人都可以作為礦工參與網絡的財產往往會丟失。

 

6–3. 區(qū)塊鏈和領導者選擇算法

 

PoW，PoS和領導者選擇算法

 

區(qū)塊鏈上的領導者選擇算法類似于獨占控制算法的機制。在比特幣中，用于選舉領導者的算法，即，新創(chuàng)建塊的節(jié)點是PoW。

 

PoW允許添加一個塊作為一個好的領導者，為比特幣網絡提供有計算復雜性和發(fā)現(xiàn)nonce的節(jié)點。每個成為領導者的礦工都會嘗試為比特幣網絡做出貢獻，因為更容易早期同步到首先發(fā)現(xiàn)現(xiàn)時的節(jié)點并開始搜索下一個塊的現(xiàn)時值更有可能獲得獎勵。盡管存在鏈條完全由硬叉分支的問題，但是通過基于博弈論準備非常簡單的激勵結構，在塊鏈網絡中實現(xiàn)作為分布式系統(tǒng)的同步。

 

在以太坊的情況下，由于塊生成的時間很短，因此傾向于發(fā)生更多的分叉。關于這一點，通過采用unkle塊的概念，我們實現(xiàn)了一種結構，即使產生不合法的鏈條也會給予一定的獎勵。

 

將來引入未來的PoS允許優(yōu)先生成具有大硬幣保持量的節(jié)點的塊作為引導者。這是一種解決/改善PoW中必要電量變得巨大且易受51％攻擊的問題的算法。這是一種基于博弈論的選舉算法，如果一個節(jié)點持有大量硬幣，就不會采取破壞網絡等惡意行為。

 

BFT和領導者選擇算法

 

BFT類型算法的問題在于如何選擇將投票給塊生成的領導者作為Proposer或Orderer。

 

在PBFT采取的HyperLedger當中，原為可信賴的機構才會注冊為Orderer。 但這是集中式的領導者選擇方法，與分布式系統(tǒng)存在著明顯的區(qū)別。

 

在Tendermint協(xié)議當中，領導者以循環(huán)方式被選出，以通過與不同驗證者的輪換交替來提出建議。 此時，領導候選者是基于PoS，并且可以說是可以在分布式系統(tǒng)中實現(xiàn)領導者選擇的算法之一。