成卫青^{1, 2,,},
张蕾¹
1.南京邮电大学计算机学院 南京 210023
2.东南大学计算机网络和信息集成教育部重点实验室 南京 211189
基金项目:国家自然科学基金(61170322)，江苏省研究生教育教学改革课题(JGZZ19_038)

详细信息

作者简介:成卫青：女，1972年生，教授，研究方向为网络测量、分布式系统和模式识别
张蕾：女，1994年生，硕士，研究方向为分布式系统

通讯作者:成卫青　chengweiq@njupt.edu.cn

中图分类号:TP391; TP393

计量

文章访问数:112
HTML全文浏览量:79
PDF下载量:15
被引次数:0

出版历程

收稿日期:2020-02-11
修回日期:2021-03-23
网络出版日期:2021-06-03
刊出日期:2021-12-21

Research on Gossip Algorithms with Binary Exponential Backoff

Weiqing CHENG^{1, 2,,},
Lei ZHANG¹
1. School of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
2. Key Laboratory of Computer Network and Information Integration (Ministry of Education), Southeast University, Nanjing 211189, China


摘要
摘要:为减少Gossip算法进行信息传播的通信开销，该文提出一个将二进制指数退避算法与经典Gossip算法相结合的二进制指数退避的Gossip算法(BEBG)，其信息传播策略是一个节点收到同一信息的次数越多，继续传播该信息的概率就越低。理论分析与仿真实验表明，BEBG能够有效减少信息传播冗余，网络中有10⁴个节点时比经典Gossip算法减少了约61%网络负载。为解决BEBG存在的边缘节点问题，进一步提出了两个BEBG改进算法，引入Pull的PBEBG和引入向邻居节点Push的NBEBG。实验结果表明，两个算法能够消除边缘节点，当网络中有10⁴个节点时，它们与相应的分别引入相同Pull和Push的经典Gossip算法相比，分别减少了约34%和37%的网络负载。
关键词:分布式系统/
信息传播/
Gossip算法
Abstract:In order to reduce the communication cost of classic Gossip algorithm for information dissemination, an improved Gossip algorithm BEBG (Gossip with Binary Exponential Backoff) is proposed, which combines the binary exponential backoff algorithm with Gossip algorithm. Its information dissemination strategy is that the more times that a node has received the same information, the lower probability it continues to spread the information. Theoretical analysis and simulation results show that the BEBG can effectively reduce the redundancy of information propagation, and compared with the classic Gossip algorithm, the network load is reduced by about 61% when there are 10⁴ nodes in the network. In order to solve the problem of edge nodes in the BEBG, two improved BEBG algorithms PBEBG that introduces Pull operations and NBEBG that introduces pushing information to a Neighbor node are further proposed. Experimental results show that the two algorithms can eliminate the edge nodes, and when there are 10⁴ nodes in the network, they reduce the network load by about 34% and 37% respectively compared with the corresponding improved classic Gossip algorithms which introduce the same pull and push respectively.
Key words:Distributed systems/
Information dissemination/
Gossip algorithm



PDF全文下载地址:

https://jeit.ac.cn/article/exportPdf?id=f6fa0831-1ddc-4135-8b00-4e20e658f708