Multicast and the Gossip protocol
Gossip protocols solve a common problem in distributed systems called multicasting. So what is multicast, and why is it required? It is common in distributed systems to have processes running on different nodes. These processes typically need to communicate by sending and receiving messages. For example, one of these nodes might have updated information it needs to propagate to other nodes in the group. This information propagation to other nodes in a group is a multicast problem. The multicast protocols we discuss here live at the application level. There are network-level protocols like IP multicasting. However, these are generally not enabled on most switches and routers.
There are a few key characteristics we require from a multicast protocol.
- Resilience - Since failures are the norm in distributed systems, we want to ensure that all healthy nodes within the group receive the messages despite nodes being down or due to transmission delays and packet loss.
- Scalable - There can be hundreds or even thousands of nodes that are part of a group; hence we want the overhead associated per node of a multicast protocol to be as low as possible.
- Low Latency - The time it takes for the information to disseminate to all the nodes should be small.
Multicast Approaches
There are a variety of approaches to achieving multicasting. We’ll discuss a few over here, along with the tradeoffs associated with each of them.
Centralized
One of the most straightforward approaches would be to use a centralized server. This server maintains a list of recipients. Then, whenever it receives some update, it goes through the list of recipients and sends them the update.
However, this approach does not satisfy the three criteria for multicast.
- It is not resilient. The sender is a single point of failure. In addition, if the sender fails midway through the list, half the recipients would not receive the multicast.
- If there are thousands or tens of thousands of recipients, there is a substantial overhead associated with sending messages.
- There can be a substantial delay in recipients receiving messages, especially if there are many recipients.
Tree-Based
Tree-based Multicast Protocols build a spanning tree among the nodes or the processes in the group. The root node sends messages to its children, which sends the multicast to its children, and so on. Tree-based protocols overcome some of the issues associated with the centralized approach.
- Resilience is better. Node failures at leaf nodes affect a single node. However, failures near the root might affect a large number of nodes.
- The overhead at each node is constant since the number of children for each node is constant. Essentially, each node gets one message and sends out messages equal to its child nodes.
- If the tree is balanced, the latency associated with each message would be logarithmic; since for N nodes, the height of a balanced tree is log(N).
Tree-Based multicast protocols use either acknowledgment (ACK) or negative acknowledgments (NAK) to handle missed messages. Failures can lead to an implosion in the number of the ACK/NAK messages. For instance, if the initial dissemination was not very successful and was received at very few nodes in the group. Common ways to avoid implosion is to employ random delays with exponential backoffs while sending ACK’s/NAK’s.
The overhead associated with ACK’s and NAK’s grows linearly with the number of members of the group. Hence Tree-Based multicast protocols are not as performant.
Gossip
Gossip was developed in order to address the performance and resiliency shortcomings of centralized and tree-based multicast protocols. Gossip can use UDP as the underlying network protocol since Gossip is very reliable. Gossip belongs to a class of algorithms called epidemic algorithms.
In Gossip, each node is in either of two states.
- Infected - A node that has received a gossip message
- Uninfected - A node that has not yet received a gossip message.
Once a node is infected, it stays infected. Each infected node periodically picks a small number of random nodes to multicast the message in the gossip protocol. The period is typically called the gossip period. The number of nodes chosen is called the gossip fan-out; the gossip fan-out is a small number, typically 2. After a certain number of gossip cycles, all nodes would be infected.
A key factor with Gossip is that there is no synchronization required between the nodes. Each node works only according to its local clock and maintains its gossip period.
The algorithm described above is a push model. There are variants of the gossip protocol, which can be pull-based or even hybrid, that employ both push-based and pull-based mechanisms.
Gossip protocols are
- Highly resilient. Messages are guaranteed to reach all healthy nodes, even in the case of node outages, transmission delays, or packet losses.
- Lightweight even in large groups, typically O(log(N), where N is the size of the group.
- Low latency- Also logarithmic in propagation to all the nodes.
