Gossip协议

Gossip是分布式系统中被广泛使用的协议，其主要用于实现分布式节点或者进程之间的信息交换。Gossip协议同时满足应用层多播协议所要求的低负载，高可靠和可扩展性的要求。由于其简单而易于实现，当前很多系统（例如Amazon S3，Usenet NNTP等）选择基于Gossip协议以实现应用层多播的功能。

什么是Gossip协议

Gossip Protocol利用一种随机的方式将信息散播到整个网络中。正如Gossip本身的含义一样，Gossip协议的工作流程即类似于绯闻的传播，或者流行病的传播。具体而言Gossip Protocol可以分为Push-based和Pull-based两种。Push-based Gossip Protocol的具体工作流程如下：

• 网络中的某个节点随机的选择其他b个节点作为传输对象。
• 该节点向其选中的b个节点传输相应的信息
• 接收到信息的节点重复完成相同的工作

Pull-based Gossip Protol的协议过程刚好相反：

• 某个节点v随机的选择b个节点询问有没有最新的信息
• 收到请求的节点回复节点v其最近未收到的信息

当然，为了提高Gossip协议的性能，还有基于Push-Pull的混合协议。同时需要注意的是Gossip协议并不对网络的质量做出任何要求，也不需要loss-free的网络协议。Gossip协议一般基于UDP实现，其自身即在应用层保证了协议的robustness。

Gossip协议的性能

Gossip协议的分析是基于流行病学（Epidemiology）研究的。因此在分析Gossip的性能之前，需要首先介绍一下流行病学中基本的模型。

Epidemiology

流行病传染最基本的模型仅作如下几个假设：

• (n+1)个人均匀的分布在一起
• 每一对人群之间的传染概率是β，显然0<β<1.
• 任意时刻，某个人要么处于infected的状态要么处于uninfected的状态.
  一旦某个人从uninfected状态转变成为infected状态，其一直停留在infected状态。

有了以上假设，我们可以进一步分析流行病的传染情况。我们记t时刻处于infected状态的人数为yt，处于uninfected状态的人为xt，那么初始状态 y0=1, x0=n，并且在任何时候xt+yt=n+1.

考虑连续的时间，可知：

dx/dt=−βxy

解的：

x=n(n+1)/n+eβ(n+1)t
y=n+1/1+ne−β(n+1)t

明显，当t→∞时，x→0,y→(n+1)，即经过足够的时间，所有的人都将被传染。

Gossip的性能

上述流行病传染模型为分析Gossip的性能提供了基础。在Gossip性能中，我们可以认为: β=b/n（因为对每个节点而言，被其他节点选中的概率就是b/n)。我们令t=clog(n)，可以得到:

y≈(n+1)−1/ncb−2

这表明，仅需要O(log(n))个回合，gossip协议即可将信息传递到所有的节点。 根据分析可得，Gossip协议具有以下的特点:

• 低延迟。仅仅需要O(log(n))个回合的传递时间。
• 非常可靠。仅有1/ncb−2个节点不会收到信息。
• 轻量级。每个节点传送了cblog(n)次信息。

于此同时，Gossip协议的容错性比较高，例如，50的丢包率等价于使用b/2带代替b进行分析；50的节点错误等价于使用n/2来代替n，同时使用b/2来代替b进行分析，其分析结果不用带来数量级上的变化。