Reliable Broadcast

 

The first type of broadcast is Reliable Broadcast.  This type of broadcast guarantees agreement (all processes agree on the correct set of messages), validity (all messages sent by a process will eventually be delivered), and integrity (no spurious messages will be delivered).  The needed files for this program are ReliableBroadcastProcess.java, RBListenerThread.java, and Message.java.

 

To run this demo, compile these three classes and then run java ReliableBroadcastProcess <name>, where <name> is some unique name for the process.  This process will listen for messages broadcast by other processes, and will itself broadcast any messages typed in.  Here is the result for a sample run:

 

$ java ReliableBroadcastProcess Alpha

Hi.

  Delivered: Hi.

 

This is not terribly interesting by itself, so run 3 or 4 instances, and all messages will be broadcast back and forth.

 

Note that each message is tagged with a sequence number and the ID of the sender.  Together these fields uniquely identify it.

 

When a process receives a message from another algorithm, it relays it on to all other processes if it has not already seen that message.  This is called message diffusion.  In these examples, it is hard to appreciate how this works, since every process is able to connect directly to every other process.  However, in a more complex implementation, the message would be passed from node to node until it had been sent to every node running everywhere on the network.  (You can think of this as something akin to a bad smell expanding throughout the room).

 

 

But, while every RB process agrees on the set of messages, there are no guarantees on the ordering of those messages.  To demonstrate this, we can extend the ReliableBroadcastProcess class to create a DelayedMessageProcess class.  This process works the same, but it deliberately swaps the order of every 2 messages.  So, if it ran and broadcast two messages, like so:

 

$ java DelayedMessageProcess Slowpoke

One

Two

 

Then a ReliableBroadcastProcess running would deliver messages in the incorrect order, like so:

 

$ java ReliableBroadcastProcess Alpha

  Delivered: Two

  Delivered: One

 

In some cases, this would be entirely acceptable, or at least bearable.  In many others, it would not be.

 

So, if we need to guarantee the ordering, what can we do?  We can use FIFO broadcast instead.