Reliable Broadcast 101

Building a distributed system requires reliable message passing between parties, and "Reliable Broadcast" helps us do exactly that.

Definition

Reliable broadcast is an important core part of the architecture of distributed systems. It has a simple purpose: to guarantee reliable “message passing” (broadcast) from one node to many nodes in a node cluster. “Reliable” means the message is still delivered even if the connections between nodes break.

Building a distributed system requires reliable message passing between parties, and “Reliable Broadcast” helps us do exactly that.

Simple broadcast

A broadcasted message m is replicated at the sender node and then sent to all other nodes in a cluster.

The figure below shows a node (in red) in the cluster that can’t receive the broadcast message m sent by the sender node (because the network connection between that node and the sender is broken).

If we want to guarantee that the red node still receives the broadcast message in the case above, the simple broadcast algorithm isn’t good enough.

Reliable broadcast naive algorithm

The reliable broadcast algorithm extends the Simple broadcast algorithm so that message passing keeps working even when some (network) links between nodes fail. There are many ways to implement it, for example:

  • Node p sends m to all other nodes, including itself
  • Each node that receives m for the first time forwards m to all other nodes in the cluster (except the sender node)
func Broadcast(m Message) {
	SendToAllNodes(m);
}

func Receive(m Message) {
	if !previouslyProcessed(m) {
		// First time receiving this message
		// Broadcast it again
		Broadcast(m);
		// Process the message
		Process(m);
	}
}

The figure below shows how reliable broadcast works. As long as there is a network link from one node to another, the message will still be broadcast.

The only case where reliable broadcast can’t deliver the message to all nodes is when some nodes are completely disconnected from the rest of the cluster (nothing can be done in this case).

Implement: previouslyProcessed()?

To check whether a received message has already been processed (at a node), we can assign each message an ID, or a hash, and save the processed IDs or hashes into Storage (DB, cache). This costs extra memory after every processed message, so there should be a mechanism to periodically reset the DB that stores these IDs/hashes.

func previouslyProcessed(m String) bool {
	hash := generateHashFromString(m)
	if isExistedInStorage(hash) {
		return true
	}

	addMessageHashToStorage(hash)
	return false
}

Atomic Broadcast

Atomic broadcast is an extension of the reliable broadcast protocol to satisfy the “total order property”, which means all participating nodes receive the messages and receive them in the same order. The “total order property” is quite useful for building replicated state machines, because each message can represent some kind of state transition. Since all messages are broadcast reliably and in order, all nodes receive the same state transitions and therefore reach the same state.

Atomic Broadcast == Consensus

It has been shown that atomic broadcast and consensus (consensus algorithms) are pretty much equivalent. And since the hard problems of consensus have been solved by Paxos and Raft (and many other algorithms), atomic broadcast can in turn be explained and implemented more simply.

(So the Atomic Broadcast section will be updated after I finish researching consensus) 😃

Referrences