Delivery guarantee(3) - Causal Broadcast

From the last post, we learned how to prevent causal anomaly using vector clock:

So, here the message with vector clock [1,1,0] received on Carl's side gets queues up because it's too big to be delivered. This is just one example. What would be the general rule for doing this?

Causal broadcast algorithm

1) If a message sent by P1 is delivered to P2, increment P2's local clock in the P1 position.

2) If a message is sent by a process, first increment its own position in its local clock and include the local clock along with the message.

3) A message sent by P1 is only delivered to P2 if the followings are met:

• T[P1] on P1 == VC[P1] +1 on P2
  AND
• T[Pk] on P1 <= VC[Pk] on P2 for all K != 1.

Note that we only consider send as an event. It's worth also noting that this is broadcast. All messages are sent to all processes.

Let's look at a different example.

You can see how we detect the causal anomaly using vector clock.

The question is, don't we have problem when two processes send at the same time and messages pass each other? This is essentially asking if this vector clock establishes total-order delivery.

You cannot preventing total order anomaly using vector clock

Let's look back on our total order anomally example and try to apply vector clock.

Remember the third rule,

T[Pk] on P1 <= VC[Pk] on P2 for all K != 1.

This was to rule out the messages that are coming from the future from receiving end's perspective. Now, P1 receives a message from client2 and it is NOT comming from the future, so is a message coming to P2 from client2. So the situation above is FINE under causal broadcast algorithm.

We can therefore confirm that causal delivery doesn't rule out total order anomalies. And it also suggests that if we want to rule out total order anomaly we need something more than vector clock.