Crypto Intro: Gossip Protocol
This article was produced for Radix DLT and the original can be found here.
Distributed systems need to communicate and synchronize information between its component nodes. This is performed using what is known as a “gossip protocol”. This idea of gossip as a communication protocol plays an important role in a variety of types of networks, including those that are decentralized. Because of the way they work, gossip protocols are often compared to how a contagious virus spreads across populations.
How do gossip protocols work?
Gossip protocol implementations on a decentralized network work by empowering all nodes to share information. Within the network, nodes are randomly connected to each other. A node, N1, has new information to send to the network, and sends it to nodes N2 and N8. N2 then sends this information received from N1 to N5 and N6, while N8 forwards the information on the N9. This continues until all nodes in the network have received the new information.
This information exchange can either be on an immediate (i.e. as the node becomes aware of an event it immediately transmits this new knowledge to other nodes) or periodical (i.e. every 10 seconds nodes exchange what they currently believe the status of the ledger to be).
This allows information to proliferate across a network quickly, without relying on centralized parties to spread it. The information exchange continues until all nodes are made aware of what has happened, although the nature of gossip protocols means that all nodes will be aware of different events at any given time. It is only over time that they converge on the same set of accepted events.
For gossip protocols to work, nodes must connect in a random fashion with other nodes and must do so with enough other nodes. If a node was to connect with only one other node, then information transmission across the network would be slow and limited. If nodes can choose what nodes they connect to, it means that information transmission could be compromised. Furthermore, nodes must be able to act without needing to know the state of the entire ledger because, as previously noted, nodes will only have access to a limited amount of the ledger at any given time.
Why are gossip protocols important?
Gossip protocols are important because they enable a number of different attributes for a decentralized network – namely, decentralization itself, reliability, speed and scalability.
Gossip protocols are by their nature a decentralized means of communication. They remove the need for a single party to tell others information and allow for nodes to fail or be unreliable without the network collapsing or grinding to a halt. This is crucial to allowing a network to be fault tolerant. Because there are many nodes sharing information (and each node has multiple connections), if one node refuses to share information then it will find another route instead. This increases redundancy.
This need not be as a result of malicious activity. Nodes will routinely fail or leave the network, and gossip protocols are a means to for the network as a whole to cope such activity. If a node leaves, then that is fine – because nodes can then rejoin, connect to a new set of peers and be told by other nodes enough about local information to enable them to function.
Furthermore, gossip protocols allow networks to scale. The larger a network gets, the harder it becomes for all nodes to be aware of all activity. Consider a top down hierarchy for example. The more layers that are added, the more time it takes for all parties to receive information. Furthermore, it concentrates power to those at the top of the structure. Gossip protocols, however, mean all nodes will have received the information about a given event after a certain number of transmission rounds. The number of rounds required to arrive at this depends on how many nodes are on the network, and is typically logarithmic in the number of nodes in the system for a well designed and implemented gossip protocol.