當前位置:首頁 » 區塊鏈知識 » paxos是區塊鏈通信協議嗎

paxos是區塊鏈通信協議嗎

發布時間: 2021-04-21 10:07:16

㈠ 如何淺顯易懂地解說 Paxos 的演算法

Phase1:確定誰的編號最高,只有編號最高者才有權利提交proposal;
Phase2:編號最高者提交proposal,如果沒有其他節點提出更高編號的proposal,則該提案會被順利通過;否則,整個過程就會重來。
反復如此,演算法永遠無法結束,這叫活鎖。FLP Impossibility已經證明,在非同步通信中不存在任何一致性演算法,活鎖便是Paxos無法解決的硬傷。
Phase1,Phase2非常像2PC中的兩個階段,因此paxos本質上是多個2PC交替執行!
另外,即使明白了,在實現時會知道有多難,工程實現與理論差距很大。

㈡ 分布式共識包含哪三種方法

PoW 、PoS 、DPOW都是什麼意思?
說到區塊鏈,我們必然會談及它的共識機制。不了解區塊鏈的共識機制,就無法理解區塊鏈的真正意義。那麼,今日份的區塊鏈的共識機制了解一下?
共識機制是什麼?
什麼是共識?直取它的字面意思,就是"共同的認識".
人與人是不同的,這種不同不僅體現在身材、長相、能力,更體現在文化、觀點、想法、利益訴求等等方面。
共識,簡而言之,就是一個群體的成員在某一方面達成的一致意見。
我們了解到,信任是社會運轉中的一大痛點,銀行有自己的信用體系,過去的金融體系服務於只服務於極少的企業家,因為建立信用體系耗資巨大。後來支付寶有了芝麻信用,信用已經關繫到生活的很多方面,信用卡額度、花唄額度,芝麻信用高出國還可以免簽。我們正享受著信用給我們帶來的便捷。
區塊鏈本質是去中心化,去中心化的核心是共識機制,區塊鏈上的共識機制主要解決由誰來構造區塊,以及如何維護區塊鏈統一的問題。
區塊鏈共識機制的目標是使所有的誠實節點保存一致的區塊鏈視圖,同時滿足兩個性質:
1)一致性:所有誠實節點保存的區塊鏈的前綴部分完全相同。
2)有效性:由某誠實節點發布的信息終將被其他所有誠實節點記錄在自己的區塊鏈中。
區塊鏈的自信任主要體現於分布於區塊鏈中的用戶無須信任交易的另一方,也無須信任一個中心化的機構,只需要信任區塊鏈協議下的軟體系統即可實現交易。
共識機制是什麼?PoW 、PoS 、DPOW都是什麼意思?
共識機制的必要性?
分布式系統中,多個主機通過非同步通信方式組成網路集群。在這樣的一個非同步系統中,需要主機之間進行狀態復制,以保證每個主機達成一致的狀態共識。錯誤信息可能出現在非同步系統內並不斷傳播,因此需要在默認不可靠的非同步網路中定義容錯協議,以確保各主機達成安全可靠的狀態共識,這就是共識機制誕生的必要性。
這種自信任的前提是區塊鏈的共識機制(consensus),即在一個互不信任的市場中,要想使各節點達成一致的充分必要條件是每個節點出於對自身利益最大化的考慮,都會自發、誠實地遵守協議中預先設定的規則,判斷每一筆記錄的真實性,最終將判斷為真的記錄記入區塊鏈之中。attachments-2018-08-9yY7VRHa5b738e3d96021.jpg
換句話說,如果各節點具有各自獨立的利益並互相競爭,則這些節點幾乎不可能合謀欺騙你,而當節點們在網路中擁有公共信譽時,這一點體現得尤為明顯。區塊鏈技術正是運用一套基於共識的數學演算法,在機器之間建立"信任"網路,從而通過技術背書而非中心化信用機構來進行全新的信用創造。
當今區塊鏈的幾種共識機制介紹
區塊鏈上的共識機制有多種,但任何一種都不是完美無缺,或者說適用於所有應用場景的。
PoW 工作量證明
整個系統中每個節點為整個系統提供計算能力(簡稱算力),通過一個競爭機制,讓計算工作完成最出色的節點獲得系統的獎勵,即完成新生成貨幣的分配,簡單理解就是多勞多得,bitcoin、LTC等貨幣型區塊鏈就應用POW機制。
優點
完全去中心化節點自由進出,演算法簡單,容易實現破壞系統花費的成本巨大,只要網路破壞者的算力不超過網路總算力的50%,網路的交易狀態就能達成一致
缺點
浪費能源,這是最大的缺點區塊的確認時間難以縮短,如bitcoin每秒只能做7筆交易,不適合商業應用新的區塊鏈必須找到一種不同的散列演算法,否則就會面臨bitcoin的算力攻擊對節點的性能網路環境要求高容易產生分叉,需要等待多個確認無法達成最終一致性
PoS 權益證明
也稱股權證明,類似於你把財產存在銀行,這種模式會根據你持有加密貨幣的數量和時間,分配給你相應的利息。
優點
對節點性能要求低,達成共識時間短
缺點
沒有最終一致性,需要檢查點機制來彌補最終性
DPOW 委託股權證明
DPOW是 PoS 的進化方案,在常規 PoW和 PoS 中,任何一個新加入的區塊,都需要被整個網路所有節點做確認,非常影響效率。
DPoS則類似於現代董事會的投票機制,通過選舉代表來進行投票和決策。被選舉出的n個記賬節點來做新區塊的創建、驗證、簽名和相互監督,這樣就極大地減少了區塊創建和確認所需要消耗的時間和算力成本。
優點
大幅縮小參與驗證和記賬節點的數量,可以達到秒級的共識驗證
缺點
犧牲了去中心化的概念,不適合公有鏈
PBFT 實用拜占庭容錯
實用拜占庭容錯機制是一種採用"許可投票、少數服從多數"來選舉領導者並進行記賬的共識機制,該共識機制允許拜占庭容錯,允許強監督節點參與,具備許可權分級能力,性能更高,耗能更低,而且每輪記賬都會由全網節點共同選舉領導者,允許33%的節點作惡,容錯率為33%.實用拜占庭容錯特別適合聯盟鏈的應用場景。
優點
會背離中心化,加密貨幣的存在及獎勵機制會產生馬太效應,讓社區中的窮者更窮,富者更富共識效率高,可實現高頻交易
缺點
當系統只剩下33%的節點運行時,系統會停止運行
dBFT 授權拜占庭容錯
這種機制是用權益來選出記賬人,然後記賬人之間通過拜占庭容錯演算法達成共識。授權拜占庭容錯機制最核心的一點,就是最大限度地確保系統的最終性,使區塊鏈能夠適用於真正的金融應用場景。
優點
專業化的記賬人可以容忍任何類型的錯誤記賬由多人協同完成,每一個區塊都有最終性,不會分叉演算法的可靠性有嚴格的數學證明
缺點
當三分之一或以上記賬人停止工作後,系統將無法提供服務當三分之一或以上記賬人聯合作惡,可能會使系統出現分叉
Pool 驗證池
基於傳統的分布式一致性技術,加上數據驗證機制。
優點
不需要加密貨幣也可以工作,在成熟的分布式一致性演算法(Pasox、Raft)基礎上,實現秒級共識驗證。
缺點
去中心化程度不如bitcoin,更適合多方參與的多中心商業模式。
Paxos
這是一種傳統的分布式一致性演算法,是一種基於選舉領導者的共識機制。領導者節點擁有絕對許可權,並允許強監督節點參與,其性能高,資源消耗低。所有節點一般有線下准入機制,但選舉過程中不允許有作惡節點,不具備容錯性。
Paxos演算法中將節點分為三種類型:
proposer:提出一個提案,等待大家批准為結案。往往是客戶端擔任該角色
acceptor:負責對提案進行投票。往往是服務端擔任該角色
learner:被告知結案結果,並與之統一,不參與投票過程。可能為客戶端或服務端
Paxos 能保證在超過50%的正常節點存在時,系統能達成共識。
瑞波共識機制
瑞波共識演算法使一組節點能夠基於特殊節點列表形成共識,初始特殊節點列表就像一個俱樂部,要接納一個新成員,必須由該俱樂部51%的會員投票通過。共識遵循這些核心成員的"51%權利",外部人員則沒有影響力。由於該俱樂部由中心化開始,它將一直是中心化的,而如果它開始腐化,股東們什麼也做不了。與bitcoin及Peercoin一樣,瑞波系統將股東們與其投票權隔開,因此,它比其他系統更中心化。
Peercoin
Peercoin(點點幣,PPC),混合了POW工作量證明及POS權益證明方式,其中POW主要用於發行貨幣,未來預計隨著挖礦難度上升,產量降低,系統安全主要由POS維護。
在區塊鏈網路中,由於應用場景的不同,所設計的目標各異,不同的區塊鏈系統採用了不同的共識演算法。每種共識演算法都不是完美的,都有其優點和局限性。
區塊鏈解決了在不可信信道上傳輸可信信息、價值轉移的問題,而共識機制解決了區塊鏈如何分布式場景下達成一致性的問題。
雖然區塊鏈目前還處於發展的早期,行業發展還面臨著一些阻礙,但社會已經足夠多地認識到區塊鏈的價值,區塊鏈發展的腳步絕不會停滯不前,行業發展也定會找到突破阻礙的方法。

㈢ 一致性hash和paxos什麼區別

一致性演算法:用於保證在分布式系統中每個節點都順序執行相同的操作序列,在每一個指令上執行一致性演算法就能夠保證最終各個節點的數據都是一致的。
Paxos就是用於解決一致性問題的演算法,有多個節點就會存在節點間通信的問題,

㈣ 什麼是區塊鏈的共識機制

區塊鏈是一種去中心化的分布式賬本系統,它可以用於登記和發行數字化資產、產權憑證、積分等,並以點對點的方式進行轉賬、支付和交易。區塊鏈系統與傳統的中心化賬本系統相比,具有完全公開、不可篡改、防止多重支付等優點,並且不依賴於任何的可信第三方。
由於點對點網路下存在較高的網路延遲,各個節點所觀察到的事務先後順序不可能完全一致。因此區塊鏈系統需要設計一種機制對在差不多時間內發生的事務的先後順序進行共識。這種對一個時間窗口內的事務的先後順序達成共識的演算法被稱為「共識機制」。
-----知鏈(chainknow)

㈤ paxos演算法是什麼

Paxos演算法是萊斯利·蘭伯特(Leslie Lamport,就是LaTeX中的"La",此人現在在微軟研究院)於1990年提出的一種基於消息傳遞的一致性演算法。這個演算法被認為是類似演算法中最有效的。

蘭伯特提出的Paxos演算法包含2個部分:

一個是Basic Paxos演算法,描述的是多節點之間如何就某個值(提案Value)達成共識;

另一個是Multi-Paxos思想,描述的是執行多個Basic Paxos實例,就一系列值達成共識

可因為蘭伯特提到的Multi-Paxos思想,缺少代碼實現的必要細節(比如怎麼選舉領導者),所以在理解上比較難。Basic Paxos是Multi-Paxos思想的核心。

(5)paxos是區塊鏈通信協議嗎擴展閱讀

背景

Paxos演算法解決的問題是一個分布式系統如何就某個值(決議)達成一致。一個典型的場景是,在一個分布式資料庫系統中,如果各節點的初始狀態一致,每個節點執行相同的操作序列,那麼他們最後能得到一個一致的狀態。

為保證每個節點執行相同的命令序列,需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。

一個通用的一致性演算法可以應用在許多場景中,是分布式計算中的重要問題。因此從20世紀80年代起對於一致性演算法的研究就沒有停止過。節點通信存在兩種模型:共享內存(Shared memory)和消息傳遞(Messages passing)。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。

㈥ 剛剛了解,誰能告訴我區塊鏈是什麼通俗解釋一下區塊鏈技術的方法

大家共同記賬的方式,也被稱為「分布式」或「去中心化」,因為人人都記賬,且賬本的准確性由程式演算法決定,而非某個權威機構。

這就是區塊鏈,核心講完了,區塊鏈就這么簡單,一個共同記賬的賬本

區塊鏈技術六大核心演算法:

區塊鏈核心演算法一:拜占庭協定

拜占庭的故事大概是這么說的:拜占庭帝國擁有巨大的財富,周圍10個鄰邦垂誕已久,但拜占庭高牆聳立,固若金湯,沒有一個單獨的鄰邦能夠成功入侵。任何單個鄰邦入侵的都會失敗,同時也有可能自身被其他9個鄰邦入侵。拜占庭帝國防禦能力如此之強,至少要有十個鄰邦中的一半以上同時進攻,才有可能攻破。然而,如果其中的一個或者幾個鄰邦本身答應好一起進攻,但實際過程出現背叛,那麼入侵者可能都會被殲滅。於是每一方都小心行事,不敢輕易相信鄰國。這就是拜占庭將軍問題。

區塊鏈核心演算法二:非對稱加密技術

在上述拜占庭協定中,如果10個將軍中的幾個同時發起消息,勢必會造成系統的混亂,造成各說各的攻擊時間方案,行動難以一致。誰都可以發起進攻的信息,但由誰來發出呢?其實這只要加入一個成本就可以了,即:一段時間內只有一個節點可以傳播信息。當某個節點發出統一進攻的消息後,各個節點收到發起者的消息必須簽名蓋章,確認各自的身份。

區塊鏈核心演算法三:容錯問題

我們假設在此網路中,消息可能會丟失、損壞、延遲、重復發送,並且接受的順序與發送的順序不一致。此外,節點的行為可以是任意的:可以隨時加入、退出網路,可以丟棄消息、偽造消息、停止工作等,還可能發生各種人為或非人為的故障。我們的演算法對由共識節點組成的共識系統,提供的容錯能力,這種容錯能力同時包含安全性和可用性,並適用於任何網路環境。

區塊鏈核心演算法四:Paxos 演算法(一致性演算法)

Paxos演算法解決的問題是一個分布式系統如何就某個值(決議)達成一致。一個典型的場景是,在一個分布式資料庫系統中,如果各節點的初始狀態一致,每個節點都執行相同的操作序列,那麼他們最後能得到一個一致的狀態。為保證每個節點執行相同的命令序列,需要在每一條指令上執行一個「一致性演算法」以保證每個節點看到的指令一致。一個通用的一致性演算法可以應用在許多場景中,是分布式計算中的重要問題。 節點通信存在兩種模型:共享內存和消息傳遞。Paxos演算法就是一種基於消息傳遞模型的一致性演算法。

區塊鏈核心演算法五:共識機制

區塊鏈共識演算法主要是工作量證明和權益證明。拿比特幣來說,其實從技術角度來看可以把PoW看成重復使用的Hashcash,生成工作量證明在概率上來說是一個隨機的過程。開采新的機密貨幣,生成區塊時,必須得到所有參與者的同意,那礦工必須得到區塊中所有數據的PoW工作證明。與此同時礦工還要時時觀察調整這項工作的難度,因為對網路要求是平均每10分鍾生成一個區塊。

區塊鏈核心演算法六:分布式存儲是一種數據存儲技術,通過網路使用每台機器上的磁碟空間,並將這些分散的存儲資源構成一個虛擬的存儲設備,數據分散的存儲在網路中的各個角落。所以,分布式存儲技術並不是每台電腦都存放完整的數據,而是把數據切割後存放在不同的電腦里。就像存放100個雞蛋,不是放在同一個籃子里,而是分開放在不同的地方,加起來的總和是100個。想了解更多可以多利用網路搜索,網路搜索結果-小知識

㈦ paxos怎麼與分布式聯系起來

這么說吧,paxos是一個會者不難,難者不會的演算法,門檻高,但一旦明白又感覺很簡單!
總體說來,paxos就是通過兩個階段確定一個決議:
Phase1:確定誰的編號最高,只有編號最高者才有權利提交proposal;
Phase2:編號最高者提交proposal,如果沒有其他節點提出更高編號的proposal,則該提案會被順利通過;否則,整個過程就會重來。
你編號高,我比你更高,反復如此,演算法永遠無法結束,這叫活鎖。FLP Impossibility已經證明,在非同步通信中不存在任何一致性演算法,活鎖便是Paxos無法解決的硬傷。
Phase1,Phase2非常像2PC中的兩個階段,因此paxos本質上是多個2PC交替執行!
另外,即使你明白了,在實現時會知道有多難,工程實現與理論差距很大!

㈧ 簡單的理解為區塊鏈是防篡改的,量子保密通信是防竊取的,對嗎

1、區塊鏈是一種防篡改、共享的、可追溯的一種分布式的賬本技術,防篡改在於單個節點的修改必須通過其他多個節點的共識才能得到認可;可追溯是區塊鏈整個賬本只允許寫入,不允許刪除,所有的整個修改記錄在整個鏈上都會留痕;共享是指整個區塊鏈的賬本對於分布式網路裡面多個節點來講它是透明的。
區塊鏈中的哈希函數是防篡改的關鍵,哈希演算法是區塊鏈中保證交易信息不被篡改的單向密碼機制。哈希演算法接收一段明文後,會以一種不可逆的方式將其轉化為一段長度較短、位數固定的散列數據。所以區塊聯具有但不僅限於防篡改!
2、量子保密通信分為量子密碼通信、量子遠程傳態和量子密集編碼等。按其所傳輸的信息內容分為是經典通信和量子通信而分為兩類。前者主要傳輸量子密鑰,後者則可用於量子隱形傳態和量子糾纏的分發。量子通信在被人竊聽時,雖然竊聽者無法得到信息,但通信中斷,影響正常通信,他防竊聽是以中斷通信為代價的,所以好像也沒有傳說中的那麼好。。目前量子通信還有很多難題未解決,如傳輸距離短,中繼困難等,不成熟。
3、在保密通信中,技術的競爭和互補是此消彼長相互借鑒、共同發展的,區塊鏈在保密通信中應該屬於網路層吧,量子通信應該屬於物理層保密通信。所以應該不會出現誰會替代誰的那種競爭結果。

㈨ Paxos 演算法的幾種演算法

上面通過證明如果一個協議滿足B1-B3 約束條件,那麼就可以保證一致性。直接從這些約束得到preliminary protocol ,basic protocol 是preliminary protocol 的限製版,保證了一致性。complete Synod protocol 進一步限制了basic protocol ,滿足一致性和過程需求(progress requirements)。下面將這三個演算法的具體過程。 滿足B1,牧師發起選舉的編號必須滿足偏序關系,有一個方法是每個發起牧師使用遞增的數值作為選舉編號,但這樣牧師無法立即知道他們選的數值有沒有被其他牧師選作選舉編號已經被使用。還有一個方法是使用數字+牧師姓名作為選舉編號,這樣就避免了自己的選舉編號被其他牧師使用。
滿足B2,每次選舉的法定人數必須是一個大部分集合(majority set)Q,這樣任意兩個選舉都會有一個共同的牧師。這里大部分集合是一個靈活的選擇,在原文中Lamport 使用體重打比方,體重的人更有可能呆在議會大廳,這樣就可以使用體重超過一半的牧師集合作為大部分集合。至於實際情況中的大部分集合是什麼要看具體情況了。
滿足B3,要求每個牧師p 每次在發起選舉前必須找到B_qrm 中每個牧師q 的MaxVote(b,q,B)。
根據以上要求,可以得到初始協議:
1. 牧師p 選擇一個選舉編號b ,並發送NextBallot(b)送給其他牧師
2. 其他牧師q 在收到NextBallot(b) 後,返回LastVote(b,v) 給牧師p,v=MaxVote(b,q,B)$是小於b 編號的q 投的最大的贊成票。為了保證B3,q 不能在b 和b_bal 之間的選舉投贊成票。(如果q 在發送了LastVote(b,v)又對新的選舉投票了那麼v 也就不是q 投的最大贊成票)
3. 牧師p 從一個大部分集合Q 中每個牧師q 中都收到LastVote(b,v) 後,發起一個新的選舉,編號為b,法定人數為Q,法律d滿足B3。然後牧師p 將這個法律寫在自己賬目的背面,發送BeginBallot(b,d)給Q 中每個牧師。
4. 牧師q 收到BeginBallot(b,d) 後決定是否為這次選舉投贊成票,如果贊同,則他將發送Vote(b,q) 給牧師p。
5. 如果牧師p 收到Q 中每個牧師q 發來的贊成票Vote(b,q),則將法律d 寫入他的賬目中,並向所有q發送Success(d) 消息。
6. 收到Success(d) 消息後,牧師q 將法律d 寫入到自己的賬目中。
說明:第一步表示發起法律的牧師p 希望下一個選舉的編號是b 。牧師q 用LastVote(b,v) 回應了牧師p 的請求,也就是向牧師p 通過法律時保證了v=MaxVote(b,q,B) 的被改變,具體來說就是不在b 和b_bal 之間的選舉投贊成票。
第三步要求法律d 需要滿足B3,這里我開始有點迷糊,實際系統中的值是客戶端決定的,而不應該是B3 決定的。這里我們還是用上面的key-value 資料庫的例子來理清下思路:當某個節點/牧師第一次發起更新前相當於B為空集,發起更新/選舉的操作不斷進行,直至所有法定人數(quorum)都對法律投了贊成票(即majority set 的節點都更新了該key-value 的值則認為更新成功),B3對應的就是之前的更新沒有成功,那麼新的選舉值需要保持的情況。第四步允許牧師可以不發送Vote(b,q) 或者發送幾次,對應的是發送的信息可能因為通信而失敗而未發送或者被多次發送。一旦牧師投了贊成票則確認可以修改該值。
考慮到最後第六步法律d 才被牧師q 寫入到賬目,有可能出現的情況就是在第五步的時候牧師p 將法律寫入到了自己賬目中,接著發送Success(d) 給其他牧師,其中因為通信或者牧師離開議會大廳而沒有被寫入到自己的賬目中,導致不一致。所以真正寫入到賬目時機應該是在第四步牧師q 在發送給牧師p 贊成票的同時就法律寫入到了各自賬目中。而不用考慮如何保證牧師q 第四步寫入的法律會導致不一致,因為法律如果沒有通過則還有更多的選舉來保證一致性。後面也談到了當法律第一次別寫入到賬目中算通過法律。 初始協議(Preliminary Protocol)要求每個牧師都保存 (i) 他發起的每個選舉; (ii) 他投的每個贊成票; (iii) 他發送的每個$LastVote$。為了簡化牧師需要保存的數據,我們對上面的協議做一個限制,得到基礎(Basic Protocol)協議。首先介紹三個新的參數:
lastTried[p] 牧師p 發起的最後一個選舉
prevVote[p] 牧師p 最近一次的投票
nextBal[p] 收到的選舉編號的b 的最大值,即牧師p參加的最大選舉編號
在初始協議中,每個牧師可以同時發起任意個選舉,在基礎協議中要求每個牧師只能發起一個選舉lastTried[p],一旦發起一個選舉,那麼之前發起選舉的信息就都不重要了。在初始協議中要求每個牧師不能在b_bal 和b 之間投贊成票,在基礎協議中則更嚴格地要求不能給小於b 的選舉投贊成票。那麼基礎協議可以概述為下面幾步:
1. 牧師p 選擇一個大於lastTried[p] 的選舉編號b ,發送NextBallot(b)給其他牧師
2. 牧師q 收到NextBallot(b) 且b>nextBal[q]後設置nextBal[q]=b ,接著發送LastVote(b,v) 給牧師p,其中v==prevBa[q] 。(如果b 小於或等於nextBal[q],則不回復)
3. 從滿足某個大部分集合Q 中每個牧師收到了LastVote(b,v) 信息,牧師p 發起一個編號為b ,法定人數為Q ,法律為d(滿足B3 )的選舉,並將BeginBallot(b,d) 發送給Q 中每個牧師。(如果沒有滿足任意大部分集合Q 的牧師返回,則返回第一步)
4. 牧師q 收到BeginBallot(b,d) ,決定投贊成票,設置prevVote[p] 為這次投票,並發送Vote(b,q) 給牧師p。(如果在收到BeginBallot(b,d) 後發現b 不等於nextBal[q] 則忽略這條信息,說明這期間牧師q 還收到了其他的編號更大的選舉)
5. 牧師p 從大部分集合Q 中每個牧師q 收到了Voted(b,d) ,且b==lastTried[p] ,則認為這次選舉成功,將法律d 記錄在賬目中,並向Q 中每個牧師q 發功成功消息Success(d) 。
6. 每個牧師q 收到Success(d) 消息後將法律寫入賬目。
基礎協議是初始協議的限製版,因為兩者都對牧師沒有行為要求,所以也不保證過程(QS)。下面介紹一個保證過程的協議— 完整議會協議(complete Synode protocol)。 基礎協議保證了一致性卻沒有保證任何過程,因為它只闡述了牧師可能做什麼,沒有要求牧師應該做什麼。為了達到之前談到的過程需求(Qrogress Requirements),我們需要添加一些額外的要求使得牧師們盡快執行完2-6 步。
考慮一種情況如果牧師q 第二步收到的選舉編號b 都比之前收到的要大,那麼他就要放棄之前收到的所有選舉。可是在選舉編號為b 的選舉在未確認前,可能又會收到更大編號的選舉b』 ,這樣就無法通過任何法律,過程也不能保證。所以為了達到過程需求則需要一個選舉成功後再發起另一個選舉。而首先應該知道服務員傳遞消息和牧師處理消息的時間,在網路中常常通過設置timeout 來實現,同樣的如果超過了一定時間牧師沒有收到服務員的回復,則認為該服務員或者對應的牧師離開了議會大廳。
假設牧師執行一個動作在7 分鍾以內,服務員傳遞一個消息在4 分鍾以內,那麼一個牧師p 發送消息給牧師q ,希望其回復的時間應該是在22 分鍾內(7+4+7+4 分鍾)。
有了上面時間的假設,再考慮上面討論過的情況,如果發起選舉的牧師p 會在第二步和第四步期望22 分鍾內收到其他牧師的回復,如果沒有則可能是一些牧師或者服務員離開了議會大廳,或者還有一些牧師發起了編號更大的選舉。遇到這兩種情況都牧師p 應該終止本次選舉,而重新開始發起一個新的選舉,為了不至於新發起的選舉編號還是太小而仍不能執行,需要從其他牧師哪裡獲取最新的選舉編號,從而選取一個更大的編號發起選舉。
進而假設牧師p 是唯一能夠發起選舉的牧師且議會大廳內有大部分集合的牧師,那麼可以保證在99分鍾內通過一條法律:22 分鍾內發現了有更大編號的法律,22 分鍾內獲取最大編號並選擇個更大的編號,55 分鍾內完成1-6 步完成一次成功的選舉(疑問:既然只有牧師p 能夠發起選舉,那麼編號都是由其控制的,前兩步發現並選擇更大的編號似乎就沒有必要了。答:並不是所有的選舉都是president發起的,其他牧師發起選舉,president向其他希望發起選舉的牧師配發選舉編號)。從上面的過程我們發現完整議會協議需要一個選舉president的過程,president的選舉演算法不是文章重點,所以文章中僅用T 分鍾代替了選舉president的時間,這樣T+99 分鍾內可以通過一部法律。
文中選擇president的方法是誰的姓在字母表中最後,並將自己的姓發送給議會大廳內所有牧師,如果在T-11 分鍾內某個牧師沒有收到比自己姓在字母表中更靠後的姓,則認為自己是president(我覺得廣播體重也應該不錯,不是說體重更重的呆在議會大廳會更久么?^_^)。還有一個細節:在選舉president的時候每個牧師p 需要將自己的lastTried[p] 發送給其他牧師,以使得president能夠在第一次選舉時選擇一個足夠大的編號。
至此,通過選舉president和設置超時,完整議會協議就可以保證過程了。
多法律國會協議
上節的議會協議(complete Synod protocol)中,president被選舉出來後,每個希望發起選舉的牧師通知他,president給牧師配發選舉編號,每次僅通過一部法律。多法律國會協議(The Multi-Decree Parliment)選擇一個president通過一系列法律,且只需要執行前兩步一次即可。
具體方法是president第一步發送NextBallot(b,n) 代替NextBallot(b) ,表示希望通過n-b 之間的所有的法律,在president 的賬目上,編號n 之前的法律都是連續記錄了的,b>n 。其他牧師q 收到消息後將每部已經出現在其賬目中編號大於$n$的法律都返回給president,不在賬目上的返回正常的LastVote 信息。
下面談到多法律國會協議有關性質,首先是法律的順序,不同法律編號的選舉同時進行,發起選舉的每個牧師都認為自己是president(不知道president 是怎麼選舉出來的,也不知道法律通過的順序)。在完整議會協議第三步中法律被提議,第一次寫入到賬目上時稱法律被通過。當一個president需要提出新的法案時,他必須從大部分集合牧師中學習到那麼法律他們都投了贊成票,每部法律都被大部分集合牧師中至少一個牧師投了票,所以president發起新的選舉前總能學到所有之前通過了的法律。president不會在空缺的法律編號內填補重要的法律。,也不會亂序提議法律,所以協議滿足「法律有序性」:如果法律A 和法律B 都是重要的法律,法律A 在法律B 提議之前通過,那麼法律A 有比法律B 更低的法律編號。第二點屬性是president在選舉出後且沒有人再進出議會大廳,法律是按照下面步驟不斷通過的(對應完整議會協議的3-5步):
3. president 向一個法定人數牧師中每個牧師發送BeginBallot ;
4.每個牧師向president 發送Voted 信息。
5.president向每個牧師發送Success 消息。這樣通過每部法律只需要三次消息傳遞,通過合並BeginBallot 和Success 命令可以進一步減少消息傳遞。

熱點內容
比特幣礦機怎麼挖幣 發布:2025-05-15 12:09:28 瀏覽:661
eth轉出一直未確認 發布:2025-05-15 11:51:58 瀏覽:601
比特幣礦機生產商曹 發布:2025-05-15 11:51:05 瀏覽:169
去錫滬路家藝中心坐車 發布:2025-05-15 11:46:41 瀏覽:395
杭州區塊鏈補貼政策 發布:2025-05-15 11:45:54 瀏覽:759
eth和btc在哪裡購買 發布:2025-05-15 11:36:53 瀏覽:233
志願者區塊鏈平台 發布:2025-05-15 11:30:23 瀏覽:186
17年6月份比特幣價格行情 發布:2025-05-15 11:28:48 瀏覽:589
虛擬區塊代幣數字貨幣場 發布:2025-05-15 11:23:26 瀏覽:436
持有數字貨幣合法嗎 發布:2025-05-15 11:20:27 瀏覽:456