二进制指数退避的Gossip算法研究  

Research on Gossip Algorithms with Binary Exponential Backoff

作　　者：成卫青[1,2] 张蕾 CHENG Weiqing;ZHANG Lei(School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210023,China;Key Laboratory of Computer Network and Information Integration(Ministry of Education),Southeast University,Nanjing 211189,China)

机构地区：[1]南京邮电大学计算机学院,南京210023 [2]东南大学计算机网络和信息集成教育部重点实验室,南京211189

出　　处：《电子与信息学报》2021年第12期3486-3495,共10页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(61170322);江苏省研究生教育教学改革课题(JGZZ19_038)。

摘　　要：为减少Gossip算法进行信息传播的通信开销,该文提出一个将二进制指数退避算法与经典Gossip算法相结合的二进制指数退避的Gossip算法(BEBG),其信息传播策略是一个节点收到同一信息的次数越多,继续传播该信息的概率就越低。理论分析与仿真实验表明,BEBG能够有效减少信息传播冗余,网络中有104个节点时比经典Gossip算法减少了约61%网络负载。为解决BEBG存在的边缘节点问题,进一步提出了两个BEBG改进算法,引入Pull的PBEBG和引入向邻居节点Push的NBEBG。实验结果表明,两个算法能够消除边缘节点,当网络中有104个节点时,它们与相应的分别引入相同Pull和Push的经典Gossip算法相比,分别减少了约34%和37%的网络负载。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 104 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 104 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.

关 键 词：分布式系统 信息传播 Gossip算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] TP393[自动化与计算机技术—计算机科学与技术]