Gossip protocols

In short: In gossip protocols nodes regularly exchange information with randomly chosen neighbours, like rumours. Knowledge spreads quickly and robustly across the whole cluster.

In more detail: At fixed intervals each node picks a few random partners and reconciles its state with them. After about O(log n) rounds almost all nodes know the information. There is no central coordinator.

In Depth

• Use: Membership lists (who is still alive?), failure detection, spreading metrics.
• Examples: Cassandra, Consul (Serf), Redis Cluster.
• Advantages: Scales, fault tolerant, simple.
• Disadvantages: Only eventually consistent, message overhead, convergence time fuzzy.
• Anti-entropy: Reconciliation to find and fix divergences.
• SWIM protocol: Gossip-based failure detection with indirect ping.

See also: Consistent hashing, Consistency models and eventual consistency