Skip to content

Introduction to gossip

homepage-banner

A gossip protocol is a procedure or process of computer peer-to-peer communication that is based on the way epidemics spread. Some distributed systems use peer-to-peer gossip to ensure that data is disseminated to all members of a group. Some ad-hoc networks have no central registry and the only way to spread common data is to rely on each member to pass it along to their neighbours.

The origin of GOSSIP protocol

The term gossip protocol was originally coined in 1987 by Alan Demers, a researcher at Xerox’s Palo Alto Research Center, who was studying ways to route information through unreliable networks.

The term “gossip protocol” was first used in 1987 by Alan Demers, a researcher at Xerox’s Palo Alto Research Center. Demers was studying ways to route information through unreliable networks.

The Gossip protocol was proposed by Demers in August 1987 in a paper titled “Epidemic Algorithms for Replicated Database Maintenance”, which was published in ACM.

Fundamental

Gossip is a decentralized distributed protocol, and data spreads from node to node like a virus.

gossip.gif

  1. Gossip spreads messages periodically, with a period limit of 1 second.
  2. Infected nodes randomly select k adjacent nodes (fan-out) to spread messages. The fan-out is set to 3, and messages are spread to a maximum of 3 nodes at a time.
  3. Each time a message is spread, select nodes that have not yet received it.
  4. Nodes that receive messages will not spread them back to the sending node. For example, if A sends a message to B, when B spreads the message, it will not send it back to A.

Note: The Gossip process is asynchronous, which means that the sending node does not care whether the other party has received it, that is, it does not wait for a response; it sends messages to surrounding nodes every 1 second regardless of whether the other party has received it.

Here is how the gossiper works
  1. Once per second, the gossiper will choose a random node in the cluster and initialize a gossip session with it. Each round of gossip requires three messages.
  2. The gossip initiator sends its chosen friend a GossipDigestSyn message.
  3. When the friend receives this message, it returns a GossipDigestAck message.
  4. When the initiator receives the ack message from the friend, it sends the friend a GossipDigestAck2 message to complete the round of gossip.

Advantages

  • Scalability: Allows for arbitrary increases and decreases in the number of nodes, and the state of new nodes will eventually be consistent with other nodes.
  • Fault-tolerance: Restart or downtime of any node in the network does not affect the operation of the gossip protocol, which has a natural fault-tolerant feature of distributed systems.
  • Robustness: The gossip protocol is a decentralized protocol, so all nodes in the cluster are equal, without any special nodes. Therefore, any node problem will not prevent other nodes from continuing to send messages. Any node can join or leave at any time without affecting the overall service quality of the system.
  • Convergent Consistency: Rumor propagation can be exponentially fast, so when new information is propagated, messages can quickly be sent to all global nodes, and all nodes can have the latest data within a limited time.

Disadvantages

  • Message delay: Nodes randomly send messages to a few nodes, and the message eventually reaches the entire network through multiple rounds of dissemination, inevitably causing message delay.
  • Message redundancy: Nodes periodically randomly select surrounding nodes to send messages, and nodes that receive messages will repeat this step, inevitably causing the same node to receive the same message multiple times, increasing the pressure on message processing. A single communication will cause a lot of load on network bandwidth and CPU resources, and these loads are limited by the communication frequency, which affects the speed of algorithm convergence.
  • Byzantine problem: If there is a malicious node spreading messages, the Gossip protocol’s distributed system will have problems.

System with gossip

Common distributed systems that use the gossip protocol are:

  • Redis Cluster
  • Elasticsearch
  • Cassandra
  • Consul
  • Bitcoin also uses the Gossip protocol to propagate transaction and block information.

Reference

  • https://en.wikipedia.org/wiki/Gossip_protocol
Small world. Big idea!
  • Welcome to visit the knowledge base of SRE and DevOps!
  • License under CC BY-NC 4.0
  • No personal information is collected
  • Made with Material for MkDocs and generative AI tools
  • Copyright issue feedback me#imzye.com, replace # with @
  • Get latest SRE news and discuss on Discord Channel