Gossip 流言蜚语、小道消息之意。Gossip 协议也叫 Epidemic 协议（流行病协议）。类似现实生活中的绯闻传播、或者流行病传播，最终达到全网同步的状态。

    原本用于分布式数据库中节点同步数据使用，后被广泛用于数据库复制、信息扩散、集群成员身份确认、故障探测等。

    在区块链中用来确保网络中所有的节点数据一样，解决状态在集群中的传播和保证状态一致性问题。最初是由施乐公司帕洛阿尔托研究中心（Palo Alto Research Center）的研究员艾伦·德默斯（Alan Demers）于1987年创造的。

Gossip 协议的优势：

一、可扩展性

    一般需要O(logN)轮消息传播即可达到状态一致性，其中N代表节点的个数。每个节点只发送固定数量的消息，与网络中的节点总数无关。消息传送只负责单向发送，不等待消息的确认。系统可以轻松的扩展到数百万个进程。

二、容错性

    网络中任何节点的重启、宕机都不会影响整个网络的运行。具有天然的分布式系统容错特性。

三、健壮性

    所有网络中的节点都是对等的，没有特殊的节点。任何节点出现问题都不会阻止其他节点继续发送消息。任何节点可以随时加入与退出。

四、最终一致性

    实现信息指数级的快速传播。当有新信息需要传播时，可以快速的发送到全局节点。在有限的时间内做到所有节点都拥有新的数据。

Gossip 协议的缺点：

一、消息延迟

    由于扩展性的需要，节点只向随机的少数几个节点发消息，通过多轮的散播来达到全网一致性，这样不可避免的会造成消息的延迟。

二、消息冗余

    节点定期随机选择周围节点发送消息，而收到消息的节点也会重复该步骤，所以不可避免的引起接收节点多次收到相同的消息，增加消息处理压力。

Gossip协议靠三种类型的消息进行传播，来达到最终的状态一致性。

一、直接邮寄 Direct-Mail

    直接发送更新数据，当数据发送失败时，将数据缓存在失败重试队列，然后重传。

    这种方式虽然存在丢数据问题，但实现简单，数据同步及时，不需要校验数据一致性对比，性能消息低。

二、反熵 Anti-Entropy

    以固定的概率传播所有的数据。性能消耗高。

    每个节点周期性的随机选择其他节点，通过互相交换自己的所有数据来消除两者之间的差异。

    实现反熵时，一般设计一个闭环的流程，一次修复所有节点的副本数据不致，在一个不确定的时间范围内实现数据副本的最终一致性。

    反熵使用『Simple epidemics』方式，其包含两种状态：Susceptible 和 Infective，这种模型称为 SI model。

    处于 infective 状态的节点代表其有数据更新，并且会将这个数据分享给其他节点。

    处于 susceptible 状态的节点代表其并没有收到来自其他节点的更新。

三、谣言传播 Rumor-Mongering

    仅传播新到达的数据。适用于动态变化的分布式，性能消息相对较低。

    当节点有了新信息后，这个节点就变成了『活跃』状态，它将周期性地向其他节点传播新信息，直到所有的节点都知道该新消息。

    谣言传播使用『Complex epidemics』方法，比反熵多一种 removed 状态，这种模型也称为 SIR model。

    处于removed状态的节点，表示已经接收到来自其他节点的更新，但是其并不会将这个更新分享给其他节点。

    因为谣言消息会在某个时间标记为removed，然后不会再被传播给其他节点，所以谣言传播有极小概率使得所有节点数据不一致。

 

Gossip 算法实现

    在实现算法中，主要有Push、Pull 和 PushAndPull 三种方式。

    Push 方式：将自己的所有副本数据，推给对方，修复对方副本中的熵。

    Pull 方式：拉取对方所有的副本数据，修复自己副本中的熵。

    PushAndPull 方式：同时修复自己副本和对方副本中的熵。

反熵 Anti-Entropy SI 模型算法伪代码：

 

谣言传播 Rumor-Mongering SIR 模型算法伪代码：