3.4 Distributed Consensus Algorithm: Gossip

1. What Is Gossip?

• An algorithm proposed by Xerox for replicating data among multiple nodes in a distributed database.
• Nodes continuously exchange information, and after a period of time all nodes in the cluster will know the complete information.

2. Why Is Gossip Needed?

3. Gossip Algorithm Process

• Each node periodically and randomly selects a connected node to spread messages.
• After other nodes receive messages they have not seen before, they spread those messages to other connected nodes.

4. Problems with Gossip

4.1. Message Redundancy

• Because nodes are selected randomly, the same message may be sent to the same node multiple times.

4.2. Consistency Problems

• Messages spread to the entire network little by little, so consistency problems necessarily exist during this period.

5. References

• Gossip Protocol | The Fenix Project