Gossip Protocol: An Introduction

Gossip Protocol is a type of communication protocol used mostly in large scale distributed systems. It is based upon gossip conversations which is common in many social circles. Gossip Protocols are becoming increasingly popular in distributed application due to its simplicity, scalability and high reliability even in constantly changing environments. Gossip Protocol involves periodic message exchanges between node pairs, which eventually results in information being spread throughout the system which is similar to human gossiping. It is sometimes referred to as epidemic protocols because the information spread is similar to the spread of a virus.

The operation of a gossip protocol is as follows.

• Each node has some data associated with it and periodically gossips that data with another node
• Node A randomly selects a node B from a list of nodes known to it
• A sends a message to B containing the data from A
• B sends back a response containing its data
• A and B update their data set by merging it with the received data

Yes, it's all about that. The core of the protocol is really simple.

If we start with a single node having a specific data item, it will first gossip with another node. Then periodically each node will gossip that data with one more node creating a doubling effect which will cause the data to be distributed throughout the system fairly quickly.

Scalability is a huge strength of gossip protocols. As each node knows only about a limited number of other nodes and as each node communicates only with one other randomly selected node at a time and sends only a fixed number of messages, independent of the number of nodes in the network, it provides good stable performance even when the system keeps on growing in size.

Gossip protocols also cope very well with node churning. i.e. In rapidly changing networks, when continuous node arrival and departure occurs and even when nodes crash abruptly, gossip protocols perform well due to the randomized and periodic information exchange. Loss of messages will also be tolerated due to the fact that copies of same data item will be received from multiple nodes. Also none of the nodes have specific roles assigned to them. So a failed node will not prevent other nodes from continuing sending messages and hence there will be no single point of failure and there is no need for failure detection or specific recovery actions.

Other strength is the simplicity of the protocol. It is really easy implement and maintain a gossip based solution.

Shortcomings of gossip protocols involve the built in redundancy of the protocol. The same redundancy which makes gossip inherently fault-tolerant and robust also leads to unnecessary transmission overhead in the network.

Another problem is high latency of message delivery. Message exchange is done periodically. Also nodes may choose other nodes with which it may have already communicated and it will take a long time for the message to reach the desired destination as it has to go through several other nodes to reach there. So gossip is necessarily slow and is unsuitable for real-time systems where speed is the goal.



References:

• Bakhshi, R., Cloth, L., Fokkink, W., & Haverkort, B. (2009). Mean-field analysis for the evaluation of gossip protocols. Quantitative Evaluation of Systems, 2009. QEST’09. Sixth International Conference on the (pp. 247–256). IEEE. 
• Birman, K. (2007). The Promise , and Limitations , of Gossip Protocols. ACM SIGOPS Operating Systems Review, 41(5), 8-13. 
• Several other online resources