Delivery guarantees(2) - FIFO and Causal delivery implementation

Read this post first if you haven't already.

FIFO implementation

If a process sends message m2 after message m1, then any process delivering both must deliver m1 first.

Approach1: Sequence numbers

• Messages get tagged with a sequence number and a sender ID.
• Sender increments its sequence number after sending.
• If the sequence number(SN) of the message is the SN+1 of the previously delivered message from that sender, deliver it. Otherwise, queue it up for later.

But what would happen if messages get lost? - This would buffer the message forever as follows.

So you need some reliable mechanism in this case? Well maybe not if you can simply go with any message that's higher than the previous one and drop if any message comes with the SN that's lower than the currently tracked one and don't queue up at all.

However, if it requires reliability, then we need some mechanism.

Approach2: Acknowledgement

Now, in this picture P1 sends second message only if it gets acknowledgement for earlier one.

This implementation eliminates the need to track sequence numbers. However, it comes with a notable downside: a performance hit. While batching can help mitigate this—and indeed, it’s a fundamental concept underpinning TCP—there are inherent limitations to this approach.

Causal delivery implementation - what comes from future?

Remember the causal anomaly example in the previous post:

How can we possibly prevent this? That's where Vector clock comes. If you don't know, then read this post.

How does that help? With Vector clock everything such as send, receive is counted as event. In order to implement causal delivery, however, we should change the way: we only track message send.

Let's replace message we saw above with the Vector clock:

Now you can see, Carl can tell there is something wrong going on. It is NOT okay for Carl to delivery [1,1,0] because the vector clock is too big.

If it is just one higher than what Carl has currently forMigo, then it'd be fine. But Kay's position in [1,1,0] is also higher than one in Carl's vector clock. So it can conclude that it's from the future, so buffer it.

Now, [1,0,0] comes in, can Carl deliver that? Yes because it's just one higher in Kay's place in Carl's vector clock, safe to deliver.

And then, Carl goes back to the buffer and check if it is deliverable.

What if Kay wants to send the message only to Migo and Migo wants to broadcast it to Kay and Carl?

In this case, Carl will not receive the [1,0,0] forever. This is not causal anomaly. This system shouldn't send the message to those not involved.

It means that this system assumes that all sends are broadcast.