Martin Sandiford

Primer on Gossip Protocol

Radix
November 15, 2018

As a distributed system, the Radix Ledger needs 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.


Figure 1 - Example gossip structure within a network


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.

How does Radix use gossip protocols?

Radix uses gossip protocols for many different types of network communications. Some of the key system processes that Radix uses gossip protocols for include two key components of the Radix DLT:

Atom data distribution

When a client submits an ledger entry (known as an “atom”) to a node in a Radix universe, that atom is checked for validity.  Assuming that the validity checks pass, the atom is then gossiped around the network, together with its temporal proof, to ensure that other nodes have a consistent view of the ledger.  The gossip process permits the atom data to be distributed in an efficient, yet decentralised manner.  Note that in the Radix ledger, the path the gossip took through the network forms the structure of the temporal proof.

Conflict resolution

As the network distributes atom data, conflicts can be discovered as nodes receive new atoms and these new atoms conflict with data the node already has. These conflicts are resolved using the gossip protocol built in to the Radix nodes.  More detail on how this process works is available in the Radix Tempo whitepaper.


Become a Radix Insider

subscribe

Related articles