Gossip Protocal
什么是Gossip协议
Gossip Protocol利用一种随机的方式将信息散播到整个网络中。正如Gossip本身的含义一样，Gossip协议的工作流程即类似于绯闻的传播，或者流行病的传播。
Epidemiology
流行病传染最基本的模型仅作如下几个假设：
- (n+1)个人均匀的分布在一起
- 每一对人群之间的传染概率是$\beta$，显然$0<\beta<1$.
- 任意时刻，某个人要么处于infected的状态要么处于uninfected的状态.
- 一旦某个人从uninfected状态转变成为infected状态，其一直停留在infected状态。
有了以上假设，我们可以进一步分析流行病的传染情况。我们记t时刻处于infected状态的人数为$y_t$，处于uninfected状态的人为$x_t$，那么初始状态 $y_0=1$, $x_0=n$，并且在任何时候$x_t+y_t=n+1$.
考虑连续的时间，可知：
$\frac{dx}{dt}=−βxy$
解为：
$x=\frac{n(n+1)}{n+e^{β(n+1)t}}$ $y=\frac{n+1}{1+ne^{−β(n+1)t}}$
明显，当$t→∞$时，$x→0,y→(n+1)x→0,y→(n+1)$，即经过足够的时间，所有的人都将被传染。
如果每个人每次传染的人数是b,那么
$\beta=\frac{b}{n}$
令 t=$clog(n)$,可以得到 $y\approx(n+1)-\frac{1}{n^{cb-2}}$
这表明，仅需要$O(log(n))$个回合，gossip协议即可将信息传递到所有的节点。 根据分析可得，Gossip协议具有以下的特点:
- 低延迟。仅仅需要$O(log(n))$个回合的传递时间。
- 非常可靠。仅有$\frac{1}{n^{cb-2}}$个节点不会收到信息。
- 轻量级。每个节点传送了$cblog(n)$次信息。
于此同时，Gossip协议的容错性比较高，例如，50的丢包率等价于使用b/2b带代替b进行分析；50的节点错误等价于使用n/2来代替nn，同时使用b/2来代替b进行分析，其分析结果不用带来数量级上的变化。
Gossip节点的通信方式
根据原论文，两个节点（A、B）之间存在三种通信方式:
- push: A节点将数据(key,value,version)及对应的版本号推送给B节点，B节点更新A中比自己新的数据
- pull：A仅将数据key,version推送给B，B将本地比A新的数据（Key,value,version）推送给A，A更新本地
- push/pull：与pull类似，只是多了一步，A再将本地比B新的数据推送给B，B更新本地
如果把两个节点数据同步一次定义为一个周期，则在一个周期内，push需通信1次，pull需2次，push/pull则需3次，从效果上来讲，push/pull最好，理论上一个周期内可以使两个节点完全一致。直观上也感觉，push/pull的收敛速度是最快的。
假设每个节点通信周期都能选择（感染）一个新节点，则Gossip算法退化为一个二分查找过程，每个周期构成一个平衡二叉树，收敛速度为$O(n^2)$，对应的时间开销则为$O(log(n))$。这也是Gossip理论上最优的收敛速度。但在实际情况中最优收敛速度是很难达到的，假设某个节点在第$i$个周期被感染的概率为$P_i$ ,第$i+1$个周期被感染的概率为$P^{i+1}$ ，则pull的方式:
$P_{i+1}=P_i^{b+1}$
而push为：
$P_{i+1}=P_i(1-\frac{1}{n})^{n(1-P_i)}$
显然pull的收敛速度大于push，而每个节点在每个周期被感染的概率都是固定的p(0<p<1)，因此Gossip算法是基于p的平方收敛，也成为概率收敛，这在众多的一致性算法中是非常独特的。