FIFO Broadcast

 

FIFO broadcast is a strengthening of Reliable broadcast.  It guarantees FIFO ordering, which stands for ÒFirst In, First OutÓ.

 

To do this, we make use of the sequence number of the message, and only deliver messages after we have already received and delivered all messages from that process with a lower sequence number.

 

Note on terminology:  The terms receive and deliver can be confusing.  A message has been received when the process has first gotten the message, but the system cannot act on that message until it has been delivered.  (In the example code, a message is delivered when it has been printed out to the screen).  A more precise way to say this is that a message is received by the communication layer, and the communication layer can then deliver that to the application layer.

 
 

 

 

 

 

 

 

 


The class FifoBroadcastProcess extends ReliableBroadcastProcess.  It maintains a ÒbagÓ of messages for every process.  Whenever a new message is received from another process, it goes through all messages for that process and looks for those that it can now deliver.  To demonstrate this, you can run this process with the DelayedMessageProcess from the last page.  Now, the messages will be delivered in the intended order.

 

Of course, this example is a little contrived.  It is much more likely that the message would just be lost altogether.  If that happened, no further messages could be sent between these 2 processes.  This hardly seems to be fault tolerant.

 

But since we have these sequence numbers, it gives us an easy way to detect that a message is missing.  RecoveringFifoBP extends FifoBroadcastProcess and uses its FIFO properties to do just that.  If a message is missing, this process will broadcast a request for that message to be resent.

 

 

At this point, we can guarantee that all messages from a given process are received in order.  However, we have no guarantee that all processes are seeing the same ordering of all messages.  For example, if one process runs and broadcasts ÒAÓ and ÒBÓ, and a second broadcasts Ò1Ó and Ò2Ó, there are 6 possible legal FIFO orderings:

 

            A         B         1          2

            A         1          B         2

            A         1          2          B

            1          A         B         2

            1          A         2          B

            1          2          A         B

 

Again, this might be OK, but then again, it might not.  If  Ò2Ó was a reply to ÒAÓ, the last sequence would not work.  So how do we capture this ordering between processes?  The answer is to use Causal broadcast instead.