5.領(lǐng)導(dǎo)者選舉算法

 

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

 

5–1. 欺負(fù)算法

 

當(dāng)協(xié)調(diào)員失敗并且任何進(jìn)程P注意到該情況時(shí)，P根據(jù)以下過(guò)程激活選舉。

 

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

 

· 如果沒(méi)有人回復(fù)，P將贏得選舉并成為協(xié)調(diào)員。

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

塊鏈和邏輯時(shí)鐘

 

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

 

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

 

因此，準(zhǔn)備邏輯時(shí)鐘而不是物理時(shí)鐘是切合實(shí)際的。實(shí)際上，通過(guò)在塊中加入時(shí)間標(biāo)記，可以制備出與Lamport邏輯時(shí)鐘非常相似的機(jī)制。

 

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

 

由于時(shí)鐘的這種模糊性，有可能會(huì)進(jìn)行雙重付款。但是，在比特幣區(qū)塊鏈中，只有最長(zhǎng)的鏈?zhǔn)呛戏ǖ?，在次要?yàn)證后丟棄不正確的交易。因此，區(qū)塊的順序隨著時(shí)間的流逝唯一確定。隨著每個(gè)時(shí)間戳的增加，前一個(gè)時(shí)間戳被加強(qiáng)。

 

總之，在區(qū)塊鏈中的模糊時(shí)間戳下，事務(wù)的順序一致性是不準(zhǔn)確的。然而，利用鏈?zhǔn)竭B接的簡(jiǎn)單機(jī)制，每個(gè)交易的發(fā)生前關(guān)系隨著時(shí)間的推移而建立。此外，還有一種激勵(lì)結(jié)構(gòu)，以便礦工轉(zhuǎn)移到良好，交易不一致的順序不會(huì)發(fā)生。

 

可以說(shuō)，實(shí)現(xiàn)類(lèi)似于Lamport的邏輯時(shí)鐘的時(shí)鐘同步方法，因?yàn)槭聞?wù)之間的相對(duì)順序關(guān)系，即發(fā)生在之前的關(guān)系變得更清楚。

 

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

 

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

 

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

 

PoW·PoS中的獨(dú)占控制算法

 

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

 

· 基于Token的解決方案

 

· 基于權(quán)限的解決方案

 

PoW和PoS是基于權(quán)限的，其中，可以說(shuō)它是類(lèi)似于分布式算法的機(jī)制。那么，您什么時(shí)候獲得訪(fǎng)問(wèn)資源的權(quán)限？是的，就在你找到一個(gè)隨機(jī)數(shù)時(shí)。

 

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

 

通常，當(dāng)節(jié)點(diǎn)找到一個(gè)nonce并創(chuàng)建一個(gè)比他自己更早的塊時(shí)，minor會(huì)同步該信息并移動(dòng)以搜索下一個(gè)nonce值。這是因?yàn)槿绻褂米铋L(zhǎng)鏈被認(rèn)為合法的規(guī)則搜索下一個(gè)nonce值，它們可以獲得更多利潤(rùn)。盡管PoS優(yōu)先為具有較大硬幣持有量的人提供資源訪(fǎng)問(wèn)，但基本排除控制算法結(jié)構(gòu)也類(lèi)似于分布式算法。

 

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

 

BFT類(lèi)型的獨(dú)占控制算法

 

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

 

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

 

在BFT類(lèi)型算法中，與PoW等不同，只有一個(gè)節(jié)點(diǎn)可以獲得對(duì)區(qū)塊鏈的獨(dú)占訪(fǎng)問(wèn)權(quán)限，因此不會(huì)立即確定fork和finality。但是，任何人都可以作為礦工參與網(wǎng)絡(luò)的財(cái)產(chǎn)往往會(huì)丟失。

 

6–3. 區(qū)塊鏈和領(lǐng)導(dǎo)者選擇算法

 

PoW，PoS和領(lǐng)導(dǎo)者選擇算法

 

區(qū)塊鏈上的領(lǐng)導(dǎo)者選擇算法類(lèi)似于獨(dú)占控制算法的機(jī)制。在比特幣中，用于選舉領(lǐng)導(dǎo)者的算法，即，新創(chuàng)建塊的節(jié)點(diǎn)是PoW。

 

PoW允許添加一個(gè)塊作為一個(gè)好的領(lǐng)導(dǎo)者，為比特幣網(wǎng)絡(luò)提供有計(jì)算復(fù)雜性和發(fā)現(xiàn)nonce的節(jié)點(diǎn)。每個(gè)成為領(lǐng)導(dǎo)者的礦工都會(huì)嘗試為比特幣網(wǎng)絡(luò)做出貢獻(xiàn)，因?yàn)楦菀自缙谕降绞紫劝l(fā)現(xiàn)現(xiàn)時(shí)的節(jié)點(diǎn)并開(kāi)始搜索下一個(gè)塊的現(xiàn)時(shí)值更有可能獲得獎(jiǎng)勵(lì)。盡管存在鏈條完全由硬叉分支的問(wèn)題，但是通過(guò)基于博弈論準(zhǔn)備非常簡(jiǎn)單的激勵(lì)結(jié)構(gòu)，在塊鏈網(wǎng)絡(luò)中實(shí)現(xiàn)作為分布式系統(tǒng)的同步。

 

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

 

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

 

BFT和領(lǐng)導(dǎo)者選擇算法

 

BFT類(lèi)型算法的問(wèn)題在于如何選擇將投票給塊生成的領(lǐng)導(dǎo)者作為Proposer或Orderer。

 

在PBFT采取的HyperLedger當(dāng)中，原為可信賴(lài)的機(jī)構(gòu)才會(huì)注冊(cè)為Orderer。 但這是集中式的領(lǐng)導(dǎo)者選擇方法，與分布式系統(tǒng)存在著明顯的區(qū)別。

 

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