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

【文章來源】：浙江師范大學(xué)浙江省

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

【學(xué)位級別】：碩士

【部分圖文】：

Push模式

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

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

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

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



本文編號：3525886