Gossip算法是一種分布式網絡系統(tǒng)中的重要算法,因此許多基于半分布式網絡的區(qū)塊鏈項目都采用Gossip算法來進行節(jié)點之間的數(shù)據(jù)同步。雖然Gossip算法具有簡單、高效、容錯性強等特點,但是在實際的區(qū)塊鏈網絡中,原始的Gossip算法是以固定的概率選擇目標節(jié)點傳播消息的,因此在數(shù)據(jù)同步的過程中會產生大量的冗余消息,同時數(shù)據(jù)同步的效率也會受到影響。本文以傳統(tǒng)Gossip算法已有的相關研究為基礎,針對半分布式區(qū)塊鏈網絡中消息的傳播模型,設計了兩種改進的Gossip算法。本文的主要工作如下:（1）提出了一種改進的HNA-Gossip算法,該算法新增了一個歷史節(jié)點列表結構,該列表用來存放散播過程中已收到消息的歷史節(jié)點,并將其加入到發(fā)送消息中,隨著散播的進行不斷更新。從而達到了避免向列表中的節(jié)點發(fā)送重復消息的情況,降低了消息的冗余程度,同時提高了數(shù)據(jù)同步的效率。（2）針對HNA-Gossip算法在傳播分支路徑較多的情況下表現(xiàn)較差的問題,提出了一種改進的HMS-Gossip算法,該算法在HNA-Gossip算法的基礎上增加了基于狀態(tài)消息的廣播機制。每個分支路徑中的節(jié)點在接收到消息后,通過主動向其他... 

【文章來源】：浙江師范大學浙江省

【文章頁數(shù)】：71 頁

【學位級別】：碩士

【部分圖文】：

Push模式

2預備知識11圖2.1Push模式Pull：無新信息的節(jié)點主動的向目標節(jié)點拉取信息，目標節(jié)點的選擇同樣是隨機的。Pull方式的特點是在信息傳播的初級階段，已擁有信息的節(jié)點數(shù)目增長較慢。當網絡中有一半的節(jié)點完成傳播時，每個周期已擁有信息的節(jié)點數(shù)目的增長呈乘性減少。其交互模式圖如圖2.2所示。圖2.2Pull模式Push＆Pull：該模式是將Push和Pull兩種方式結合起來，既主動的向目標節(jié)點發(fā)送信息，同時又從目標節(jié)點拉取信息。其交互模式圖如圖2.3所示。在一個全連通網絡中，Push和Pull這兩種方式都需要nO)(ln個周期和nnO)ln(次信息交換來完成Gossip傳播，而Push＆Pull方式比較復雜，這里不再詳細討論。但是研究者們已經得出結論，三種模式中，Push＆Pull方式的效率最高。圖2.3Push&Pull模式（2）網絡結構一般情況下，我們用網絡中節(jié)點之間的連接關系來表示網絡結構，并用圖進行抽象化。由于Gossip算法在每個周期內都會選擇一定數(shù)量的目標節(jié)點進行數(shù)據(jù)交互，這個數(shù)量是一個可配置的常量。發(fā)起節(jié)點與目標節(jié)點之間必然存在一定的連接關系，因此節(jié)點之間的連接關系即網絡結構會直接影響到Gossip算法的

2預備知識11圖2.1Push模式Pull：無新信息的節(jié)點主動的向目標節(jié)點拉取信息，目標節(jié)點的選擇同樣是隨機的。Pull方式的特點是在信息傳播的初級階段，已擁有信息的節(jié)點數(shù)目增長較慢。當網絡中有一半的節(jié)點完成傳播時，每個周期已擁有信息的節(jié)點數(shù)目的增長呈乘性減少。其交互模式圖如圖2.2所示。圖2.2Pull模式Push＆Pull：該模式是將Push和Pull兩種方式結合起來，既主動的向目標節(jié)點發(fā)送信息，同時又從目標節(jié)點拉取信息。其交互模式圖如圖2.3所示。在一個全連通網絡中，Push和Pull這兩種方式都需要nO)(ln個周期和nnO)ln(次信息交換來完成Gossip傳播，而Push＆Pull方式比較復雜，這里不再詳細討論。但是研究者們已經得出結論，三種模式中，Push＆Pull方式的效率最高。圖2.3Push&Pull模式（2）網絡結構一般情況下，我們用網絡中節(jié)點之間的連接關系來表示網絡結構，并用圖進行抽象化。由于Gossip算法在每個周期內都會選擇一定數(shù)量的目標節(jié)點進行數(shù)據(jù)交互，這個數(shù)量是一個可配置的常量。發(fā)起節(jié)點與目標節(jié)點之間必然存在一定的連接關系，因此節(jié)點之間的連接關系即網絡結構會直接影響到Gossip算法的

【參考文獻】：
期刊論文
[1]P2P網絡現(xiàn)狀與發(fā)展研究[J]. 賀文華,劉浩,賀勁松.  軟件工程. 2019(04)
[2]區(qū)塊鏈P2P網絡協(xié)議演進過程[J]. 武岳,李軍祥.  計算機應用研究. 2019(10)
[3]區(qū)塊鏈技術及其在信息安全領域的研究進展[J]. 劉敖迪,杜學繪,王娜,李少卓.  軟件學報. 2018(07)
[4]基于Gossip協(xié)議的拜占庭共識算法[J]. 張仕將,柴晶,陳澤華,賀海武.  計算機科學. 2018(02)
[5]一種基于移動P2P改進的Gossip算法[J]. 張國印,李軍,王向輝,徐國坤.  計算機科學. 2013(09)
[6]Chord網絡環(huán)境下的Gossip算法[J]. 劉德輝,尹剛,王懷民,鄒鵬.  計算機工程與科學. 2011(09)
[7]分布環(huán)境下的Gossip算法綜述[J]. 劉德輝,尹剛,王懷民,鄒鵬.  計算機科學. 2010(11)
[8]混合內容分發(fā)網中社群感知的Gossip協(xié)議[J]. 汪洋,陳京文,黑曉軍,程文青.  北京郵電大學學報. 2010(05)
[9]P2P關鍵技術研究綜述[J]. 王學龍,張璟.  計算機應用研究. 2010(03)
[10]網格環(huán)境下一種改進的Gossip資源聚集算法[J]. 張學敏,陳建新.  微電子學與計算機. 2009(01)

碩士論文
[1]基于Gossip算法的分布式盲區(qū)檢測[D]. 潘斯琦.哈爾濱工業(yè)大學 2016



本文編號：3525886