分布式系統(tǒng)由Tanenbaum定義，“分布式系統(tǒng)是一組獨(dú)立的計(jì)算機(jī)，在”分布式系統(tǒng)?—?原理和范例“中作為用戶的單一，連貫的系統(tǒng)出現(xiàn)”。

區(qū)塊鏈通過(guò)構(gòu)建全球分布式系統(tǒng)，嘗試實(shí)現(xiàn)分散的新數(shù)據(jù)存儲(chǔ)和組織結(jié)構(gòu)。

首先，定位到分布式系統(tǒng)的原因主要是可擴(kuò)展性，位置和可用性。區(qū)塊鏈也不例外。地理可擴(kuò)展性，形成全球價(jià)值存儲(chǔ)網(wǎng)絡(luò)/信息保護(hù)區(qū)域，包括非集中式結(jié)構(gòu)下的防篡改/零停機(jī)時(shí)間的可用性。這些未來(lái)都是使用分布式系統(tǒng)在block中實(shí)現(xiàn)的。

0.目錄

X.區(qū)塊鏈和分布式系統(tǒng)

1.簡(jiǎn)介（同步和整體流程概述）

2.時(shí)鐘同步

2–1。物理時(shí)鐘（時(shí)鐘和時(shí)鐘偏移）

2–2。 時(shí)鐘同步算法（網(wǎng)絡(luò)時(shí)間協(xié)議（NTP）/伯克利算法）

3.邏輯時(shí)鐘

3–1。 Lamport的邏輯時(shí)鐘（完全有序的多播）

3–2。 矢量時(shí)鐘（因果訂單組播）

4.獨(dú)家控制

4–1。 集中算法

4–2。 分散算法

4–3。 分布式算法

5.選舉算法

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

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

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

6–1。 塊鏈和時(shí)鐘同步（塊鏈和物理/邏輯時(shí)鐘）

6–2。 塊鏈和獨(dú)占控制算法（PoW·PoS·BFT中的獨(dú)占控制算法）

6–3。 塊鏈和領(lǐng)導(dǎo)者選舉算法（PoW·PoS·BFT中的領(lǐng)導(dǎo)者選擇算法）

1.簡(jiǎn)介（同步和整體流程概述）

與集中式系統(tǒng)不同，在分布式系統(tǒng)中就時(shí)間達(dá)成一致并不容易。

在前一種情況下，可以基于全局共享時(shí)鐘確定絕對(duì)順序關(guān)系，但是在后一種情況下，由于存在時(shí)鐘值錯(cuò)誤和對(duì)應(yīng)時(shí)間，因此難以共享絕對(duì)時(shí)間。

但是，絕對(duì)時(shí)間的順序并不是絕對(duì)必要的，如果相對(duì)順序是固定的，通常就足夠了。

在本文中，將按以下順序解釋節(jié)點(diǎn)之間的同步。

時(shí)鐘同步是如何發(fā)生的？

使用邏輯時(shí)鐘和矢量時(shí)鐘的相對(duì)排序方法

關(guān)于分布式系統(tǒng)一致性的排除控制算法

關(guān)于分布式系統(tǒng)中的領(lǐng)導(dǎo)選舉算法

2.時(shí)鐘同步

2–1. 物理時(shí)鐘

時(shí)鐘和時(shí)鐘歪斜

大多數(shù)計(jì)算機(jī)都有保持時(shí)間的電路，這種設(shè)備稱為“時(shí)鐘”。這是基于頻率的振動(dòng)，該振動(dòng)可以通過(guò)晶體類型，切割方法和向精確加工的石英增加張力時(shí)的壓力大小明確定義。

雖然這個(gè)頻率相當(dāng)穩(wěn)定，但不能保證不同計(jì)算機(jī)的所有晶體都能以完全相同的頻率運(yùn)行。由此引起的同步時(shí)間的差異稱為時(shí)鐘偏差。

在這種情況下，特別是在實(shí)時(shí)系統(tǒng)中，如何使多個(gè)時(shí)鐘與現(xiàn)實(shí)時(shí)鐘同步以及如何同步時(shí)鐘是一個(gè)問(wèn)題。

現(xiàn)實(shí)世界中的時(shí)間最初基于平均太陽(yáng)秒，但現(xiàn)在銫133過(guò)渡9，192，631，770次的時(shí)間定義為1秒，并且定義了國(guó)際原子時(shí)間和通用協(xié)調(diào)時(shí)間（UTC）。為了向需要準(zhǔn)確時(shí)間的人提供UTC，使用WWV并且時(shí)間以±10毫秒的精度提供。

2–2. 時(shí)鐘同步算法

但是，大多數(shù)機(jī)器沒(méi)有WWV接收器。因此，每臺(tái)機(jī)器都需要時(shí)間跟蹤和管理算法，以便所有機(jī)器都可以同步時(shí)間。

順便提及，用于確定是否需要重新同步的錯(cuò)誤，即時(shí)鐘偏移，如下測(cè)量。

將H定義為每臺(tái)機(jī)器計(jì)數(shù)的晶體振動(dòng)引起的每秒中斷次數(shù)（刻度數(shù)），并將C表示為該時(shí)鐘的值。設(shè)Cp（t）表示機(jī)器的時(shí)鐘值，當(dāng)UTC時(shí)間為t時(shí)。

如果將p定義為定義允許的時(shí)鐘偏差量的最大漂移率，則假定它在以下范圍內(nèi)運(yùn)行。

1-p 《= dC/dt 《= 1+p

也就是說(shuō)，在從先前同步開(kāi)始經(jīng)過(guò)At秒之后，兩個(gè)時(shí)鐘最多分開(kāi)2pΔt。

當(dāng)保證在操作執(zhí)行時(shí)沒(méi)有大于＆的偏差時(shí)，必須至少每＆/2p重新同步軟件。

網(wǎng)絡(luò)時(shí)間協(xié)議（NTP）

在許多協(xié)議中很常見(jiàn)，［Cristian，1989］首先提出的方法是一種與客戶服務(wù)器通信的方法。由于時(shí)間服務(wù)器具有WWV接收器或具有準(zhǔn)確的時(shí)鐘，因此它可以提供當(dāng)前時(shí)間。在與服務(wù)器通信時(shí)，重要的是延遲報(bào)告消息傳播延遲的時(shí)間，但是通過(guò)估計(jì)延遲，這里可以最小化錯(cuò)誤。目前，已知NTP能夠在1至50毫秒的范圍內(nèi)實(shí)現(xiàn)精度。

伯克利算法

在諸如NTP的許多算法中，時(shí)間服務(wù)器是被動(dòng)的并且僅回答查詢。另一方面，在Berkeley算法中，時(shí)間服務(wù)器接收每個(gè)參與節(jié)點(diǎn)所持有的時(shí)間，并且還基于平均值改變其自己的時(shí)間。當(dāng)時(shí)間值不必與現(xiàn)實(shí)世界有關(guān)系時(shí)，很容易在同一當(dāng)前時(shí)間達(dá)成一致，并且它對(duì)此算法有效。

3.邏輯時(shí)鐘

到目前為止，雖然我們描述了一種根據(jù)實(shí)際時(shí)鐘將時(shí)鐘與絕對(duì)時(shí)間同步作為參考的方法，但通常只執(zhí)行相對(duì)同步。這里，邏輯時(shí)鐘的概念用于確定相對(duì)順序。

3–1. Lamport的邏輯時(shí)鐘

為了同步邏輯時(shí)鐘，Lamport定義了一個(gè)名為happen-before的關(guān)系。表達(dá)式a→b表示“a發(fā)生在b之前”，這意味著事件首先發(fā)生，然后所有進(jìn)程都同意事件b將發(fā)生。發(fā)生之前?—?可以在以下兩種情況下直接觀察到關(guān)系。

如果a和b是同一過(guò)程中的事件且a出現(xiàn)在b之前，則a→b為真。

2. 如果a是由一個(gè)進(jìn)程發(fā)送的消息的事件，并且b是由另一個(gè)進(jìn)程接收的該消息的事件，那么a→b也是如此。在發(fā)送消息之前無(wú)法接收消息，即使消息同時(shí)也需要有限的非零時(shí)間。

因?yàn)榘l(fā)生前關(guān)系處于過(guò)渡關(guān)系中，如果a→b和b→c，則可以證明a→c。如果事件x，y出現(xiàn)在不交換消息的不同進(jìn)程中，則x→y和y→x都不為真，并且這些事件被認(rèn)為是并發(fā)的。 （之前發(fā)生的關(guān)系未知。）

利用邏輯時(shí)鐘，通過(guò)分配所有進(jìn)程對(duì)每個(gè)事件a一致的時(shí)間C（a）來(lái)測(cè)量相對(duì)時(shí)間。如果這些時(shí)間值是a→b，則通過(guò)向時(shí)間添加正值來(lái)校正它們，使得C（a）《C（b）。通過(guò)分配如下圖所示的時(shí)間值，可以掌握之前發(fā)生的關(guān)系。

在Lamport的邏輯時(shí)鐘中，如果a→b，則可以證明C（a）《C（b），但如果C（a）《C（b）則a→b不一定成立。換句話說(shuō)，a→b是C（a）《C（b）的必要條件，并且不是充分條件。 Lamport的邏輯時(shí)鐘增加了改進(jìn)，它是一個(gè)矢量時(shí)鐘，可以滿足這種必要和充足的條件。

完全有序的多播

有關(guān)詳細(xì)信息，請(qǐng)參閱“分布式系統(tǒng)一致性”一文中的內(nèi)容

在許多情況下，有必要在重復(fù)的副本之間執(zhí)行完全有序的多播。換句話說(shuō)，所有消息都需要以相同的順序傳遞給每個(gè)收件人。 Lamport的邏輯時(shí)鐘可用于在完全分布式系統(tǒng)下實(shí)現(xiàn)完全有序的多播。

當(dāng)進(jìn)程收到某個(gè)消息時(shí)，它會(huì)根據(jù)時(shí)間戳按順序放入本地隊(duì)列。收件人向另一個(gè)進(jìn)程多播確認(rèn)。如果您按照Lamport的算法調(diào)整本地時(shí)鐘，則所有進(jìn)程實(shí)際上都具有本地隊(duì)列的相同副本。只有當(dāng)消息位于隊(duì)列的頭部并且被所有其他進(jìn)程確認(rèn)時(shí)，才有一個(gè)進(jìn)程可以將隊(duì)列中的消息傳遞給正在運(yùn)行的應(yīng)用程序，因此，所有消息都以相同的順序傳遞到各處。換句話說(shuō)，已經(jīng)建立了完全有序的多播。

3–2. 矢量時(shí)鐘

使用矢量時(shí)鐘，可以掌握Lamport邏輯時(shí)鐘無(wú)法掌握的因果關(guān)系。 假設(shè)事件a的向量時(shí)鐘是VC（a），則執(zhí)行以下步驟，使得a→b成為VC（a）《VC（b）的必要和充分條件。

在通過(guò)網(wǎng)絡(luò)發(fā)送消息之前，節(jié)點(diǎn)Pi向矢量時(shí)鐘VCi ［i］添加1，或者操作一些內(nèi)部事件。

2. 如果處理Pi將消息m發(fā)送到Pj，則Pi在執(zhí)行前一步驟之后將m的向量時(shí)間戳ts（m）設(shè)置為等于VCi。

3. 當(dāng)接收到消息m時(shí)，進(jìn)程Pj執(zhí)行步驟1，將消息分發(fā)給應(yīng)用程序，然后更新其自己的向量時(shí)鐘的每個(gè)k，如下所示：VCj ［k］←max {VCj ［k］，ts（m）［k］}。

因果關(guān)系多播

通過(guò)使用向量時(shí)鐘，可以實(shí)現(xiàn)稍微弱于上述完全有序多播的因果有序多播。

通過(guò)比較矢量時(shí)鐘的值并掌握發(fā)生在之前的關(guān)系，對(duì)于特定事件x，其他事件可以被分類為過(guò)去事件，并發(fā)事件和未來(lái)事件。例如，在上圖中，當(dāng)事件d用作參考點(diǎn)時(shí)，過(guò)去事件是a，b，c，i，并發(fā)事件是j，l，m，未來(lái)事件是f，g，h。

此時(shí)，假設(shè)因果有序多播是過(guò)去事件和因果事件的序列，其中發(fā)生所有因果關(guān)系，以便在所有過(guò)程中保持一致，但是關(guān)于并發(fā)事件的順序是無(wú)關(guān)緊要的。通過(guò)這種方式，與Lamport的邏輯時(shí)鐘不同，可以用向量時(shí)鐘來(lái)掌握因果關(guān)系。

4.獨(dú)家控制

多個(gè)進(jìn)程之間的并發(fā)操作和協(xié)作操作是分布式系統(tǒng)的基本，但是為了保證對(duì)資源的獨(dú)占訪問(wèn)，以便通過(guò)多個(gè)進(jìn)程同時(shí)訪問(wèn)相同資源時(shí)不處于不一致?tīng)顟B(tài)時(shí)，需要分布式排他算法。

分布式獨(dú)占控制算法可以分為以下兩種類型。

基于Token的解決方案

基于權(quán)限的方法

在基于Token的方案中，很容易避免Starvation（很長(zhǎng)時(shí)間內(nèi)不允許訪問(wèn)資源）和死鎖（多個(gè)進(jìn)程等待彼此的進(jìn)展）。一個(gè)代表性的例子是Token環(huán)算法。但是，當(dāng)持有Token的過(guò)程異常停止并且Token丟失，有必要只生成一個(gè)新Token，這種復(fù)雜性是一個(gè)嚴(yán)重的缺點(diǎn)。

許多其他分散的獨(dú)占控制算法采用基于權(quán)限的方法，并有許多不同的獲取權(quán)限的方法，我們將分別具體解釋。

4–1. 集中算法

通過(guò)模擬單處理器系統(tǒng)的功能，可以輕松實(shí)現(xiàn)分布式系統(tǒng)中獨(dú)占控制的單一訪問(wèn)。在集中式算法中，一個(gè)進(jìn)程被指定為協(xié)調(diào)器，并且當(dāng)進(jìn)程訪問(wèn)共享資源時(shí)，請(qǐng)求消息被發(fā)送到協(xié)調(diào)器以獲得許可。如果其他進(jìn)程未訪問(wèn)共享資源，則協(xié)調(diào)器返回權(quán)限響應(yīng)，并且在接收到回復(fù)之后，所請(qǐng)求的進(jìn)程執(zhí)行該進(jìn)程。

很容易看出，該算法保證了對(duì)資源的獨(dú)占訪問(wèn)，但它具有單點(diǎn)故障的嚴(yán)重缺點(diǎn)。雖然這可能是大型系統(tǒng)中的性能瓶頸，但這種簡(jiǎn)單性帶來(lái)的優(yōu)勢(shì)仍然可以彌補(bǔ)這些缺點(diǎn)。

4–2. 分散算法

假設(shè)各項(xiàng)都會(huì)重復(fù)n次。在分散算法中，當(dāng)進(jìn)程訪問(wèn)資源時(shí)，需要批準(zhǔn)大多數(shù)m》 n / 2。如果獲得大多數(shù)批準(zhǔn)，則該過(guò)程獲得許可并可以進(jìn)行處理。

雖然該方案解決了集中式算法的單點(diǎn)故障問(wèn)題，但是如果有太多的節(jié)點(diǎn)試圖訪問(wèn)，則存在另一個(gè)問(wèn)題，即沒(méi)有節(jié)點(diǎn)可以獲得足夠的投票而無(wú)法獲得充分的性能。

4–3. 分布式算法

在該算法中，假設(shè)系統(tǒng)上所有事件的順序可以定義為完全有序的關(guān)系。作為這個(gè)基礎(chǔ)，使用了前一章中描述的Lamport的邏輯時(shí)鐘，并且假設(shè)沒(méi)有消息會(huì)丟失。

當(dāng)進(jìn)程嘗試訪問(wèn)共享資源時(shí)，它會(huì)創(chuàng)建一條消息，其中包含資源名稱，自己的進(jìn)程號(hào)和當(dāng)前邏輯時(shí)鐘，并將其發(fā)送給所有其他進(jìn)程。當(dāng)接收到該請(qǐng)求消息時(shí)，根據(jù)其自身狀態(tài)執(zhí)行以下操作。

1. 如果收件人未訪問(wèn)該資源且未嘗試訪問(wèn)該資源，則收件人會(huì)向發(fā)件人返回“確定”消息。

2. 如果收件人已在訪問(wèn)資源，請(qǐng)不要回復(fù)并執(zhí)行排隊(duì)請(qǐng)求。

3. 如果收件人正在嘗試訪問(wèn)資源但尚未完成，請(qǐng)將輸入消息中的時(shí)間戳與發(fā)送給其他進(jìn)程的消息中的時(shí)間戳進(jìn)行比較，并將較低的一個(gè)作為獲勝者。如果收到的消息具有小的時(shí)間戳，則收件人返回OK消息。如果自己的消息具有較小的時(shí)間戳，則接收方將不會(huì)將輸入消息排隊(duì)。

顯然，如果它不像process1或2那樣沖突，這個(gè)算法就能正常工作。即使在沖突的情況下，也只建立了唯一一個(gè)進(jìn)程可以訪問(wèn)的條件。

與集中式算法一樣，該算法可以保證獨(dú)占控制，不會(huì)出現(xiàn)死鎖或饑餓。 此外，沒(méi)有單點(diǎn)故障。 盡管如此，單點(diǎn)故障被故障n位置特征所取代。 它可以通過(guò)回復(fù)權(quán)限或拒絕權(quán)限并引入超時(shí)來(lái)解決，但也會(huì)出現(xiàn)其他問(wèn)題，例如需要多播通信原語(yǔ)。 不幸的是，目前尚未設(shè)計(jì)出超越集中式算法的分布式算法，并且仍在研究中。

當(dāng)比較各個(gè)算法時(shí)，變?yōu)槿缦隆?/p>

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)類似于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章所述，分布式排他控制算法可分為以下兩種類型。

· 基于Token的解決方案

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

PoW和PoS是基于權(quán)限的，其中，可以說(shuō)它是類似于分布式算法的機(jī)制。那么，您什么時(shí)候獲得訪問(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)先為具有較大硬幣持有量的人提供資源訪問(wèn)，但基本排除控制算法結(jié)構(gòu)也類似于分布式算法。

但是，嚴(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類型的獨(dú)占控制算法

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

在BFT類型中，只有一個(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類型算法中，與PoW等不同，只有一個(gè)節(jié)點(diǎn)可以獲得對(duì)區(qū)塊鏈的獨(dú)占訪問(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)者選擇算法類似于獨(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類型算法的問(wèn)題在于如何選擇將投票給塊生成的領(lǐng)導(dǎo)者作為Proposer或Orderer。

在PBFT采取的HyperLedger當(dāng)中，原為可信賴的機(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)者選擇的算法之一。