漫谈Gossip协议与其在Redis Cluster中的实现( 二 )

2022-04-23 Gossip协议

每一轮周期每个节点都只随机选择一个其他节点进行通信；
起始时，只有一个节点处于I状态，其他节点都处于S状态。

令s(t)表示在时刻t时，S状态的节点占总节点数n的比例（注意是比例），那么显然有s(0) = 1 - 1/n，可以计算出s(t)的期望为：

推模式

漫谈Gossip协议与其在Redis Cluster中的实现

文章插图
【漫谈Gossip协议与其在Redis Cluster中的实现】

拉模式

漫谈Gossip协议与其在Redis Cluster中的实现

文章插图

由下图可见，拉模式的信息传播效率比推模式高，达到了真正的指数级收敛速度。综合了两者的推-拉模式效率则比拉模式更高。

漫谈Gossip协议与其在Redis Cluster中的实现

文章插图

但是，推模式每轮只需要1次信息交换，拉模式需要2次，推-拉模式需要3次。由于反熵Gossip协议每次都交换全量消息，数据量可能会比较大，因此具体选择哪种模式，还是需要考虑网络资源的开销再决定。
谣言传播（Rumor-mongering）
谣言传播与反熵不同的一点是，它采用完整的SIR模型。处于R状态的结点表示已经获取到了信息，但是不会将这个信息分享给其他节点，就像“谣言止于智者”一样。另一个不同点是，谣言传播机制每次只会交换发生变化的信息，而不是全量信息，所以它对网络资源的开销会比反熵机制要小很多。
下图示出在有界集群P中，以周期Δ执行谣言传播Gossip协议的伪代码描述。

漫谈Gossip协议与其在Redis Cluster中的实现

文章插图

图中的blind/feedback和coin/counter是怎么一回事呢？它们表示节点从I状态转移到R状态的条件。

coin：在每轮传播中，节点以1/k的概率从I转移到R状态。
counter：在参与k轮传播之后（即发送k次信息）之后，节点从I状态转移到R状态。
feedback：在发出信息后，对位节点有反馈才可以进入R状态。
blind：在发出信息后，不必等待对位节点有反馈，随时都可以进入R状态。

由上可见，谣言传播模式的结束条件是所有节点都对谣言“免疫”，但是又有可能造成部分节点始终无法对消息有感知（即保持S状态）。以coin条件为例，可以写出如下的微分方程组。其中s和i仍然表示S状态和I状态的节点占总节点数的比例。

漫谈Gossip协议与其在Redis Cluster中的实现

文章插图

消去t，可得：

漫谈Gossip协议与其在Redis Cluster中的实现

文章插图

根据初始条件：i(1 - 1/n) = 1，可以推导出：

漫谈Gossip协议与其在Redis Cluster中的实现

文章插图

如果我们要让i(s*) = 0的话：

漫谈Gossip协议与其在Redis Cluster中的实现

文章插图

可见，s

推荐阅读

上一篇：吴三桂在哪里起兵反清谁平定吴三桂叛乱

下一篇：世界上最毒的五种动物最毒的十种动物