Gossip 算法
在一个有界网络中，每个node传播message给随机的几个节点，经过杂乱无章的通信，最终所有节点都会达成一致。每个节点有可能知道所有的节点，也可能仅仅知道几个邻居节点，最后状态都是一致的，又称为反熵。
优点
- 可扩展性
- 使用$O(\log N)$ rounds 到达所有nodes，N为node的个数。
- 容错
- 从源头节点到目的节点路径不止一条，可以在不规则为止连接性的网络中运行。
- 健壮性
- 故障节点不会阻止其他节点发送消息，每个节点都可以随意加入和退出，不会严重啊影响服务质量
- 但是如果消息有关于故障节点或者恶意节点，那么系统就不健壮
- 收敛速度
- 指数收敛速度
流程
两个概念
- Cycle 传播一个消息的轮数
- Fanout 每轮种node通信的节点数
- 周期性散播消息
- 每轮随机选择fanout个节点散播消息
- 每轮散播消息都选择尚未发送过的节点进行散播
- 收到消息的节点不再往send节点散播
Goosip 和 raft
raft是强一致性的，而gossip是最终一致
例子
- Riak 使用gossip协议分享并通信ring state和bucket properties
- CASSANDRA 分享周围nodes和自己的信息
- serf：go实现的服务发现和治理的框架