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

成卫青 张 蕾

①(南京邮电大学计算机学院 南京 210023)

②(东南大学计算机网络和信息集成教育部重点实验室 南京 211189)

1 引言

Gossip算法是一个依靠感染行为传播信息的算法，具有简单、高效、健壮、可扩展性和抗干扰能力强的特点，应用场景十分广泛。大型分布式系统常使用Gossip算法进行信息扩散，随着对等网络的发展，其应用领域不断扩大。Gossip算法的应用有数据库复制[1]、聚合计算[2]、网络拓扑构造[3,4]、数据挖掘[5]、故障检测[6]、网络监控[7]等。

Gossip算法常用于聚合计算和达成共识。文献[8]提出了一种新的基于Gossip算法的聚合计算方案，在O(log2n)轮通信中发送O(nlog2n)的消息。文献[9]提出了一种局部平均信息交换算法来计算网络中每个节点的初始测量值的全局一致性；在每一轮扩散过程中，每个节点与所有相邻节点交流，计算和交换局部平均值，使所有节点都能很快地以分布式方式逐渐达到全局一致。针对现有共识算法对拜占庭节点的容错能力低且对区块链系统可扩展性差的问题，文献[10]提出了基于Gossip的拜占庭共识算法，使系统可以容忍小于一半的节点为拜占庭节点。文献[11]提出了一种在不可靠网络中估计未知参数的异步广播Gossip算法，该算法允许新的传感器加入，旧的传感器离开，并能容忍链路故障。

Gossip算法可用于网络拓扑构造。如文献[4]提出了一个支持多个交互参与者和大量消费者的自组织流媒体解决方案，该方案利用基于Gossip的覆盖网的可伸缩性和健壮性来构建延迟感知的流播树，以便向多个用户提供多个不同的流。Gossip算法可用于数据挖掘。例如文献[5]针对淘宝等大型推荐系统中冷启动和稀疏评价严重降低推荐性能的问题，提出了一种基于圆桌流言算法的稀疏信任挖掘方法。文献[12]提出了基于Gossip的非结构化P2P网络分布式聚类算法，不依赖中央服务器来执行数据聚类任务，也不需要同步操作。文献[13]提出了一种能够提高测量精度的基于Gossip算法的数据聚类算法。还有其他一些应用，比如文献[14]提出了一种新的基于Gossip的信令传播方法，文献[15]以无线传感器网络中的分布式定位问题为研究背景，成功地将成对和广播Gossip算法引入到原有定位算法框架之中。为了加速服务器群间的多批数据传输，文献[16]提出了一种编码排列流言算法，研究了最佳的块划分、批划分和分批调度策略，以达到最小的广播完成时间。

影响Gossip算法性能的因素有很多，主要因素有时间模型、网络结构、信息交互模式以及每个周期、每个节点选择联系的节点个数等。因此Gossip算法只要稍作改变就可以适应很多应用场景。传统Gossip算法最大的缺点是冗余，冗余通信会造成对网路带宽和计算机资源的过多占用，因此降低Gossip算法的冗余度非常重要。本文的目的是降低Gossip算法的冗余度并提高算法的收敛速度。本文的主要贡献是：(1)提出一种二进制指数退避的Gossip算法(Gossip with Binary Exponential Backoff，BEBG)，有效降低了算法的网络负载，但BEBG存在边缘节点问题。(2)提出一个引入Pull的BEBG改进算法PBEBG，以及一个增加向邻居节点Push的BEBG改进算法NBEBG，解决边缘节点问题并提高算法的收敛速度。

2 Gossip算法概述

Gossip算法是一种非常著名的信息传播算法，其信息传播过程和图的着色类似。假设网络中只有两种颜色的节点，一种是已着色节点，一种是未着色节点，已着色节点是当前网络状态下已经收到信息的节点，未着色节点为网络中没有收到信息的节点。一个节点在网络中只有两种状态，要么是已着色的，要么是未着色的。刚开始，网络中只有一个已着色节点，第1轮这个节点会随机选择一个节点发送信息。接下来的每一轮次，网络中已着色的节点会随机选择另一节点发送信息。假设未着色节点为红色，已着色节点为蓝色。刚开始网络中只有一个蓝色节点，随着网络状态的变化，蓝色节点会变得越来越多。当蓝色完全覆盖了整个网络，意味着信息已经传播到网络中的所有节点。

2.1 时间模型

时间模型是Gossip算法的基础，不同的时间模型有着不同的研究方式。目前常用的时间模型有两种，即同步时间模型和异步时间模型。时间模型是对系统时间的简单假设，现实的时间模型更为复杂。

同步时间模型：将时间分为均匀的时隙，每个时隙，节点选择与自己的邻居节点进行通信，邻居节点选择的过程是随机且相互独立的。同步模型下，节点与节点之间的信息交换均在同一时刻进行，信息的发送与接收都在该时隙内同步完成，因此整个分布式网络中需要一个全局的时钟来同步各个节点的时间。为了简化分析过程，本文设定的时间模型是同步的。

异步时间模型：网络中每个节点都有自己的时钟，按照自己的节奏发送信息。节点根据自己时钟来发起信息交换过程，节点之间的信息发送是互相独立的。异步时间模型不需要全局时钟的同步，这种异步的Gossip算法在分布式环境下更容易实现。

2.2 Gossip算法信息交换方式

假设A和B是大规模分布式系统中的两个节点。Gossip算法中A节点和B节点信息交换的方式一般有3种：Push, Pull, Push&Pull。

Push：拥有更新信息的节点A发起信息交换，在网络中随机选择一个节点B，A节点把自己的更新信息发送给B节点，B节点收到信息后更新本地信息。

Pull：未着色节点A在网络中随机选择一个节点B，要求从B节点那里获得更新信息。

Push&Pull：节点之间互相发送更新信息给对方。A节点在网络中随机选择一个节点B，A节点将自己的更新信息发送给B节点，B节点接收到信息后更新本地信息，并将自己的更新信息发送给A节点，A节点收到B节点的信息后也要更新本地信息。

总的来说，采用Push方式，信息传播先快后慢，Pull方式相反，先慢后快。Push&Pull将两种方式结合起来，这种方式速度是最快的，但也是最消耗网络资源的。

2.3 相关研究

文献[17]为Gossip算法提供一个简单而通用的框架，并使用该框架来描述Gossip算法在不同领域中的解决方案。该文献将Gossip算法的过程抽象为3个步骤：节点的选择、信息交换和数据处理。选择节点的方式有很多种，一般情况下，每个周期节点随机选择另一个节点向其发送信息。但是，节点选择向哪些节点发送信息，每个周期发送几条信息，节点发送信息的概率都是可以随着应用场景的改变而改变的。

Gossip算法可以容忍数据包丢失和链路崩溃，尽管流言传播具有很高的容错性和可扩展性，但它仍会受到网络性能下降和网络流量负载过大的影响。因此对于必须同时提供可靠性和及时性的应用，尤其在易拥塞的网络中它可能不是最优的。文献[18]通过确定哪些节点应该接收流言消息来改进流言传播方案，提出采用分布式策略学习逻辑来高效地确定这些节点，文中提出了两个启发式方案：一个是基于QoS(Quality of Service)选择，依据损失模式，从根节点开始沿着路径选择链路质量差的节点；另一个是基于拓扑，根据位置选择组播树内更偏离根的节点。

为了提高算法的收敛速度，以及将信息传播到网络上所有的节点，文献[19]提出了Corrected Gossip算法，将蒙特卡罗式流言和确定性修正相结合，构造一个拉斯维加斯式的可靠广播，在执行Gossip算法有限周期后进入修正阶段，保证以低成本到达所有节点。该文献将未被感染的节点称为未着色的节点。文献[20]在布尔网络模型的基础上提出了布尔流言网络模型。在布尔网络中，每个节点只有两种状态“开” 和“关”，而在某个时刻每个节点只能处于其中一种状态。节点之间相互作用，节点的状态随之发生改变。文献中的网络模型只考虑一对节点间的相互作用。布尔流言网络模型是布尔网络模型的一种特殊形式，可以应用在基因调控、社会意见问卷、病毒传播等多个领域。文献[21]研究了一种网络中节点数目为奇数的Gossip模型，深入研究了同步奇Gossip算法模型和异步奇Gossip算法模型的时间下界，给出了n=2k-1 时的一个最优同步算法。

为了解决C/S架构信息系统采用的中心化数据同步模式导致的服务器性能下降，并影响信息系统整体性能的问题，文献[22]改进了Gossip算法以解决其冗余通信量大且收敛速度慢的问题，并提出了基于改进Gossip算法的数据同步方法。该方法将Gossip算法与选举算法中的环算法相结合，提高了数据同步效率，减少数据同步对系统整体性能的影响。文献[23]研究和分析了两种自然的基于流言传播的发现过程，即基于Push和Pull的发现过程，对这两个随机过程在无向n节点图及在有向n节点图中的收敛时间进行了较严密的分析。

3 基于二进制指数退避的Gossip算法

以太网介质访问控制协议CSMA/CD要求站点在发送数据之前要先监听信道，监听到信道空闲才发送数据，还需要边发边进行冲突检测，一旦检测到冲突，就采用二进制指数退避算法来决定站点再次尝试发送数据前要退避的时间，经过退避时间后再重复上述步骤。退避时间设定方法：从整数集合[0,20,21,···,(2k-1)]中随机取出一个数r，其中k=min(冲突次数,10)；退避时间=2τr，其中2τ是局域网端到端往返时延。使用随机退避时间是为了降低冲突站点再次同时尝试发送数据而又发生冲突的概率。

为降低冗余，减少Gossip算法中节点在信息传播过程中发送的信息量，本文借鉴二进制指数退避算法的思想对经典Gossip算法(classic Gossip Algorithm, GA)做改进，提出二进制指数退避的Gossip算法BEBG。该算法的思想是节点重复收到同一信息时降低传播信息的概率，重复收到同一信息的次数越多，传播该信息的概率越低。此外，针对BEBG存在边缘节点的不足，从两个方面对其进行改进，进一步提出了PBEBG和NBEBG两个算法。

3.1 二进制指数退避的Gossip算法

BEBG与GA两算法最大的不同在于，GA中，每一轮已着色节点向外传播更新信息的概率恒为1，而BEBG中已着色节点向外传播更新信息的概率是变化的。这个概率的大小与节点的网络状态有关，一条新的更新信息在网络中流传，节点重复收到这条信息的轮数越多，节点向外传播这条信息的概率越低。这与现实中人们转发新闻情形类似，对于广为流传的信息人们会失去传播它的欲望。

BEBG中，节点向外传播信息的概率p是一个变量，每个轮次一个节点的p值可能不一样；未着色节点的p值设为0，刚收到信息的节点的p值设为1。根节点和第1次收到信息的节点向外传播信息的概率为1，而未着色节点向外传播信息的概率为0。

3.1.1 BEBG的信息发送过程

第1轮，只有根节点有新的更新信息，根节点随机选择一个其他节点以概率p=1向其传播更新信息。第1轮结束时，网络中一共有两个已着色节点。第2轮，这两个已着色节点各自先根据自己向外传播信息的概率p决定是否向外发送更新信息，如果是，随机选择一个除自己以外的节点向其传播更新信息。以此类推，若干轮后，网络中所有节点可能都被着色了。节点发送信息的过程是严格全局时钟同步的，每个周期节点只随机选择1个节点向其传播1次更新信息。表1为BEBG的信息发送过程，节点向外传播信息的概率p由节点接收更新信息的情况决定，初始化时，根节点的p值为1，其他节点的p值为0。

表1 BEBG算法的信息发送过程(算法1)

3.1.2 BEBG的信息接收过程

算法的接收过程比发送过程复杂，见表2。如果本轮中收到了更新信息，第1次收到信息的节点将自己的p值由0变为1，而其他收到信息的节点(已着色节点)将自己的p值调为原来的1/2，即下一轮向外传播信息的概率变为原来的1/2。例如，如果节点A在第4轮中收到更新信息，并且它在第1和第3轮中也曾收到过相同的信息，即收到相同信息的轮次一共为3轮，则节点A在第5轮中向外传播信息的概率p为1/4，节点A在第1-第5轮的p分别为0,1, 1, 1/2, 1/4。以此类推，如果某节点收到相同信息的轮次一共为4轮，那么在下一个轮次该节点的p为1/8。为了避免算法后期无节点发送信息导致出现边缘节点(算法结束后还是未着色节点)的情况，本文给已着色节点传播信息的概率p设置了一个下限值：1/32。

每一轮中，节点传播信息的概率只有两种可能，不变或变为原来的1/2。如表2，设置一个节点接收超时时间，超过一定时间节点未收到信息，表示本轮该节点的接收过程已经结束，然后线程根据本轮是否收到信息、是否是第1次收到、p有无达到下限来将p减半或维持不变。

表2 BEBG算法的信息接收过程(算法2)

每一轮BEBG先执行信息发送过程(算法1)再执行信息接收过程(算法2)。在接收过程中，当节点发现本轮重复收到之前轮次收到过的信息时，除非p已达到下限，否则p减半，这里改变的是节点下一轮传播信息的概率。每一轮一个节点收到信息的次数是不确定的，可能零次、一次或多次，但是每轮至多只改变一次p的值。

3.1.3 BEBG算法理论分析

本小节分析采用BEBG传播信息，每一轮所有节点发送的总信息量以及信息传播规律。设未着色节点为0类节点，C0(T)为在T轮次初始尚未着色的节点总数，它们向外传播信息的概率p0= 0；一个节点若在T轮次之前累计在i个轮次中都接收到了信息，则为i类节点，Ci(T)表示在T轮次i类节点总数，i类节点向外传播信息的概率Pi= 1/2i-1；其中i=1,2,3,4,5；一个节点若在T轮次之前累计在大于等于6个轮次中都接收到了信息，则为6类节点，C6(T)表示在T轮次6类节点总数，6类节点向外传播信息的概率P6=1/32。C(T)为在T轮次初始已着色节点的总数，等于1到6类节点的总和。C(1)=1,C1(1)=1, C2(1)=C3(1)=C4(1)=C5(1)=C6(1)=0。

设当前轮次为T，在T轮次向外传播信息的节点数S(T)预期为

显然，S(1)=1。

设网络中共有N个节点，假设节点A是一个将向外发送信息的已着色节点，节点B是网络中的任意一个节点，节点B是否着色是未知的。节点A随机选择一个除自己之外的节点发送信息，所以网络中任意节点B在当前轮次收到节点A发送的信息的概率为1/(N-1)。

任意节点B在当前轮次收不到节点A发送的信息的概率为

任意节点B在当前轮次收不到来自任何将向外传播信息的已着色节点的信息的概率Pf为

任意节点B在当前轮次至少收到一条来自将向外传播信息的已着色节点的信息的概率Ps为

又由于当前网络中未着色节点个数C0(T)即为N-C(T)，所以未着色节点在当前轮次被着色(至少收到一条信息)的预期个数为

下一轮次的Ci(T+1)，其中i=1, 2, 3, 4, 5，由两部分组成，当前轮次i类节点的个数减去i类节点在本轮收到信息而转变为i+1类节点的个数，以及当前i-1类节点在本轮收到信息而转变为i类节点的个数。即在本轮未收到信息的i类节点的个数，加上i-1类节点在本轮收到信息的个数。其计算公式为

S(T)是在T轮次向外传播信息的节点数，也是在T轮次发送的总信息量，显然BEBG能够有效降低网络负载，但是BEBG降低信息量是以增加周期为代价的。在算法的后期，大量节点对外传播信息的概率为1/32，这可能导致有极个别未着色节点长期收不到更新信息。很多周期后，某些未着色节点可能还是没有收到信息，本文称这些仿佛被隔绝了的，一直(或长期)收不到信息的节点为边缘节点。为了解决BEBG存在的边缘节点问题，3.2节和3.3节对BEBG进行了改进。

3.2 PBEBG算法

Gossip信息交换的方式有3种：Pull, Push,Push&Pull。BEBG实质上是对Push模式的GA的改进。在Pull模式的GA中，未着色节点会一直向其他节点发送更新请求消息，直到找到一个已着色节点，基于Pull的方法理论上不会出现边缘节点。因此，本文将Pull与BEBG相结合来解决BEBG存在的边缘节点问题，此BEBG改进算法称为PBEBG(Binary Exponential Backoff Gossip with Pull)。如图1所示，在算法的后期，边缘节点随机选择一个节点向其发送请求消息，接收到请求消息的节点将更新信息(如果有)发送给该边缘节点。图1中灰色节点为已着色节点，白色节点为未着色节点。假设节点5随机选择向节点9发送更新请求消息，节点9收到后响应请求，将更新信息发送给节点5。

图1 PBEBG算法中的“拉”

3.2.1 PBEBG的发送过程

PBEBG的发送过程比较复杂。初始化时，根节点的p值为1，其他节点的p值为0。发送信息之前节点要先确定是否在上一个轮次收到其他节点的更新请求。如果节点是已着色的且在上一个轮次收到了请求消息，那么本轮中节点将直接把自己的更新信息发送给请求节点，如果请求节点不止一个，节点将会从请求节点中选取一个节点向其发送更新信息。

如果节点没有收到更新请求，那么信息发送过程与BEBG的相似，先根据节点向外传播信息的概率p决定是否向外发送更新信息，如果是，则随机选取一个除自己以外的节点向其发送更新信息。PBEBG的发送过程见表3。

PBEBG算法还引入了一个新的变量“Pull”。这里的“Pull”不是GA算法信息交换的一种方式，而是代表未着色节点向外发送更新请求的时机。设网络中一共有N个节点，刚开始网络中有N-1个未着色节点，不可能第1轮就让N-1个节点向外发送请求，这会导致第1轮时未着色节点发出N-1条请求消息，然而只有一条请求能得到根节点的回复，这会造成网络资源的极大浪费。因此，从哪一个轮次开始发送更新请求就至关重要了。节点决定发送更新请求的前提是：(1)当前节点未被着色；(2)当前的轮次T大于等于“Pull”值(见表4)，表3中，request为真时发送更新请求，随机选取一个除自己以外的节点向其发送更新请求。

表3 PBEBG算法的发送过程(算法3)

3.2.2 PBEBG的接收过程

PBEBG的接收过程比BEBG的接收过程多一个判断，因为这时网络中有两种消息，一种是来自已着色节点的传播感兴趣信息的更新消息，一种是来自未着色节点的更新请求消息。

每1轮，1个节点v可能既接收到网络中未着色节点发来的更新请求，也接收到已着色节点传播的更新信息。节点v有可能收到多条更新请求消息，这时，线程只会存储最后一条请求消息的来源，记为s，在下一轮如果节点v是已着色节点则会将更新消息发给节点s。如果节点v收到了多条包含相同信息的更新消息，这时的处理方法与BEBG算法的一样，每1轮只改变1次p的值。PBEBG的接收过程见表4。

表4 PBEBG算法的接收过程(算法4)

PBEBG算法有效减少了网络负载，并解决了边缘节点问题，但是该算法需要未着色节点在一定时间(轮次)后，向网络中的其他节点发送更新请求消息。然而，除非有约定或每个节点定期地去询问，否则未着色节点不知道网络中什么时候会有新的信息，也就无法估计当前处于什么轮次了。另外，Pull参数的设置需要事先做约定。这些因素减少了该算法的适用场景。因此本文又提出了一种不需要Pull的BEBG改进算法。

3.3 NBEBG算法

本节提出一个基于邻居节点的二进制指数退避Gossip算法(Neighbor-based Binary Exponential Backoff Gossip, NBEBG)，该算法增加了一个定向“推送”。与BEBG算法不同的是，BEBG算法随机选择网络中的节点向其传播信息，而NBEBG算法则是先判断本节点是否为第1次接收到更新信息，如果是，则将信息传播给前1个邻居节点，如果不是第1次，则将信息传播给从网络中随机选择的一个节点。算法运行到最后，其实相当于每一个着色节点都向前一个节点发送了一次更新信息，如果没有丢包，理论上是不会存在边缘节点的。

如图2所示，给网络中的节点编号，灰色节点为已着色节点，白色节点为未着色节点。满足条件的已着色节点将更新信息发送给前一个节点，是否传播信息与前一个节点是否着色无关。

图2 NBEBG中向前1个邻居节点推送信息

3.3.1 NBEBG的发送过程

NBEBG的发送过程比BEBG的多了一个判断。每个已着色节点每轮至多只传播一次信息，如果它向前一个邻居节点发送更新信息则不会再向网络中的其他节点发送更新信息。根据之前的经验，从哪一个轮次开始可能对总信息量产生影响，因此NBEBG算法引入了一个新的变量“Push”，代表已着色节点向邻居节点发送信息的时机，也就是说，已着色节点向前一个节点发送更新信息是在到达规定的轮次之后才会发送。算法会记录已着色节点是否已经向前一个节点发送过更新信息。只有当前轮次已达到规定轮次，且还没有向前一个节点发送过更新信息，已着色节点才会向前一个节点发送。NBEBG的信息发送的具体过程如表5所示。初始化时，根节点的p值为1，其他节点的p值为0，所有节点的hasPush标志为false。

表5 NBEBG算法的信息发送过程(算法5)

3.3.2 NBEBG的接收过程

NBEBG算法接收过程与BEBG算法接收过程完全一样，未做任何修改。

4 实验

第3节提出了两个BEBG改进算法：引入Pull的PBEBG和向前一个邻居节点Push的NBEBG。为了做对比实验，本文也将这两种改进方法引入经典Gossip算法。将引入Pull的GA称为PGA，将向前一个邻居节点Push的GA称为NGA。本文研究并实现了6种Gossip算法，如图3所示。PGA与NGA是GA的变种，PBEBG和NBEBG是BEBG的变种。

图3 6种算法名称

本文实现的程序是基于JAVA的高并发程序，通过使用JAVA的一些同步机制来模拟大规模分布式网络的环境，程序中实现了10000个高并发线程模拟10000个节点。实验结果表明，通过改变传播信息的概率，能够有效地降低Gossip算法的网络开销。Gossip算法的性能一般由算法的收敛速度和网络负载两个方面来衡量。算法的收敛速度是指算法将信息传播到网络上所有节点所需的周期数。网络负载又称为信息量，在本文中指信息传播时所发送的UDP数据包个数。本文中所有数据都是程序运行30次取的平均值。

图4为“Pull”取不同值时，PBEBG与PGA总信息量随时间变化的示意图，即累计发送的UDP数据包个数随着轮次(周期)的变化图。由图可见，边缘节点开始向网络中其他节点发送请求消息的起始轮次对算法的信息量是有影响的；“Pull”取值为12时，PGA的信息量最少，“Pull”为14时，PBEBG的信息量最少。网络中有104个节点时，PBEBG比引入Pull的GA可减少约34%的网络负载。

图4 不同“Pull”值时，算法PGA和PBEBG随时间变化的总信息量

图5为“Push”取不同值时，NBEBG与NGA总信息量随时间变化的示意图。由图可见，节点向前一个邻居节点发送信息的具体轮次对算法的信息量是有影响的；“Push”取值为14时，NGA的信息量最少，“Push”为15时，NBEBG的信息量最少。网络中有104个节点时，NBEBG比引入向邻居节点Push的GA减少了约37%的网络负载。

图5 不同“Push”值时，算法NGA和NBEBG随时间变化的总信息量

图6是6种算法将信息传遍整个网络所需的周期数。实验表明，除了BEBG，其余Gossip算法基本都能在30个周期以内将信息传遍网络，GA需要24个周期，但24周期时BEBG只能将信息传到网络中97.5%的节点，图中的28是虚值，代表很大的值。而加入“Pull”方式或者加入“向邻居Push”的4个算法，NGA-14(参数Push =14)，PGA-12(参数Pull=12)，NBEBG-15(参数Push =15)，PBEBG-14(参数Pull=14)，只需要19到21个周期就能将信息传遍网络，收敛速度相差不大，都有效解决了边缘节点问题。

图6 6种算法将信息传遍整个网络所需周期对比

图7为6种算法总信息量对比图。GA(24个周期)，NGA-14，PGA-12这3种算法的总信息量依次递减。而包含指数退避的算法中，BEBG(24个周期)，NBEBG-15，PBEBG-14这3种算法的总信息量依次递增。BEBG(24个周期)总信息量最少，但并不能将信息传遍整个网络，存在边缘节点问题；网络有104个节点时它比GA(24个周期)减少了约61%的网络负载。

图7 6种算法总信息量对比

实验结果显示，PBEBG与NBEBG均改进了BEBG存在边缘节点的不足，同时具有BEBG的网络负载低的优点。PBEBG与NBEBG的收敛速度和产生的网络负载相差无几，两算法应用条件不同，各有各的优势，PBEBG不需要知道自己的前一个节点是谁，而NBEBG不需要其他节点的响应。实际应用中，可以根据实际情况选择具体算法，比如基于DHT(分布式哈希表)的对等网络中的信息传播可以使用NBEBG，因为每个节点知道自己的前继，而对于信息更新周期比较长，节点之间基本同步，一轮时长可以估计的应用场景可以使用PBEBG。

5 结束语

为减少Gossip算法的网络负载，本文提出了一个将二进制指数退避算法与经典Gossip算法相结合的改进算法BEBG，它使用指数退避的信息传播策略，使一个节点收到同一更新信息的次数越多，继续传播更新信息的概率越低。仿真实验表明，该算法能够有效地减少网络负载，网络包含104个节点时BEBG比经典Gossip算法降低了约61%的网络负载。为解决BEBG的边缘节点问题，对BEBG算法作改进，提出了引入Pull的BEBG改进算法PBEBG，在若干轮次后让未收到更新信息的节点主动询问其他节点，网络包含104个节点时，PBEBG比引入Pull的经典Gossip算法减少约34%的网络负载。为解决边缘节点问题，对BEBG另作改进，提出了一种向邻居节点Push的BEBG改进算法NBEBG，除了常规Push，还让收到更新信息的节点向其前一个邻居节点发送更新信息以达到加快收敛速度的目的，网络包含104个节点时，NBEBG比引入向邻居节点Push的经典Gossip算法减少了约37%的网络负载。