Gossip is a common strategy for sharing information in dynamic networks. It is a type of self-organising network topology that helps nodes share information efficiently and quickly. It is the most efficient way to exchange information among multiple nodes in the same network. A Gossip protocol is an algorithm that enables multiple nodes to maintain consistent information while remaining decentralised and operationally independent. The properties and principles of gossip algorithms give us insight into optimal strategies for sharing data between computing nodes. In this blog post, we will learn about Gossip Protocol and its application in Distributed Systems.
Gossip in Computer Networks
Gossip is the general act of sharing information. In computer science, gossip is a model of asynchronous distributed computation in which a task is performed by a network of independent entities, each of which may be interrupted at any time and can at its discretion temporarily transfer the task to other entities. Gossip is appropriate for situations where a central control mechanism is either unavailable or too expensive to be practical. Gossip is such a widespread phenomenon among human beings that it has its own word, but it is not restricted to humans. Gossip has been observed in animals such as birds, insects, and a number of mammals. Gossip is a great example of the fact that small-world networks are not just a human phenomenon.
What is a Gossip Protocol?
A gossip protocol is an algorithm that allows multiple nodes to maintain consistent information while remaining decentralised and independently operated. Each node in a gossip protocol maintains a gossip graph, which is a type of data structure. The root of each gossip graph is the node’s identifier, and links to neighbouring nodes are also present. A gossip protocol uses this gossip graph to transfer and update the state of each node. Gossip protocols are categorised according to how the gossip graph is updated. Let’s suppose N is the number of nodes in the system and let’s assume that each node has a list of neighbouring nodes. Now, what happens when one of the nodes changes its state? Gossip protocols can be generalised as follows:
- Each node will maintain a data structure called the gossip graph.
- Each gossip graph has the node’s identifier as the root and has links to neighbouring nodes.
- A gossip protocol uses this gossip graph to transfer and update the state of each node.
- Gossip protocols can be categorised according to how the gossip graph is updated.
Types of Gossip Protocols
Uniform Random Gossip
Uniform random gossip is a gossip protocol in which each node i of the network chooses another node j uniformly at random and then forwards the message m that it has received thus far. This protocol has been considered as a uniform model for gossip, where the network is assumed to have uniform density and the message is forwarded with the same probability among nodes in all directions. This simple model is expected to have the same properties as more sophisticated but also more complicated models.
Echoing Gossip
Echoing gossip is a gossip protocol where two nodes i and j exchange the messages that they have received from other nodes.
Synchronous Gossip
Synchronous gossip is a type of gossip protocol where the message is forwarded by a node only after its receipt. The advantage of Synchronous gossip is that it doesn’t have any network communication delay but it is highly susceptible to network failure.
Gossip Protocol in a Distributed System
A gossip protocol can be used to create a distributed algorithm using a network of independent nodes. In a gossip protocol, nodes can be considered as agents that pass messages to one another. Each node has a set of neighbours with which it exchanges messages. You can use a gossip protocol to implement a distributed algorithm that maintains a consistent state across the nodes.
Distributed Coordination Using Gossip protocol
One of the properties of gossip protocols is that they are self-stabilising and fault-tolerant. They do not require any periodic communication between nodes to synchronise the states. Any node can send a message to any other node at any time. A node that receives a message forwards it to all the nodes that it is connected to. This continues until all the nodes receive the message. The nodes that receive the message keep a copy of the message for some time and send a reply to the node that sent the message. The nodes that receive the reply keep a copy of the message for some time and pass the message to their neighbours. This continues until all the nodes have received the message forwarded by themselves. For the nodes that have received the message forwarded by themselves, it means that the message is consistent and correct. They discard the message and are updated with the correct values.
Leader Election
In the absence of a leader, any node can become a leader by sending a message to the nodes that it is connected. The nodes that receive the first message are called peers and pass the message to their neighbours. The message is passed from one node to another until it reaches all the nodes in the network. The entire system is asynchronously managed. The nodes continue to pass messages to neighbouring nodes until they have received the message forwarded by the same node multiple times.
Properties of Gossip Protocols
Uniform random gossip has the following properties
- The state of each node in the network is consistent with that of every other node.
- The order in which messages are received at each node is consistent with the order in which the messages are sent.
- The number of messages that are passed in the network is equal to the number of messages that are sent.
- The number of messages that each node receives is equal to the number of messages that each node sends.
- The number of processors that each processor receives is equal to the number of processors that each processor sends.
- The variable delay in receiving messages from neighbouring processors is the same for all processors.
- Gossip protocols are fault-tolerant in that a network failure does not cause any inconsistency in the data held by the processors.
Advantages of Gossip Protocols
Gossip protocol and has the following advantages
- Gossip protocol is self-stabilising.
- Gossip has a high completion probability.
- Gossip protocol is fault tolerant.
Conclusion
In this article, we have explored the concept of Gossip Protocols and their use in Distributed Systems. Gossip protocols are self-stabilising, fault-tolerant schemes that use the dynamics of information diffusion to maintain data integrity. A gossip protocol is a simple algorithm that enables multiple nodes to maintain consistent information while remaining decentralised and operationally independent. We have also highlighted the different types of Gossip Protocols such as Uniform Random Gossip, Unequal Random Gossip, Echoing Gossip, Synchronous Gossip, etc. Gossip protocols are simple algorithms that enable multiple nodes to maintain consistent information while remaining decentralised and operationally independent.
