Delivery guarantees(1) - definition

FIFO delivery

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

Violation of FIFO delivery(FIFO anomaly)

Realife FIFO implementation

As a distributed system implementor, you won't actually have to implement FIFO delivery semantics yourself because. This is already a part of TCP and most distributed systems communicate over TCP.

Causal delivery

If m1's send happens before m2's send, then m1's delivery happens before m2's delivery.

The definition above sounds the same as FIFO delivery. In fact, if FIFO anomaly happens, it is also a violation of causal delivery.

Then what makes them different?
Let's look at the following example:

Now, this is NOT FIFO violation because from the definition of FIFO delivery, we learned that the same process has to be sending at least two messages to the same receiving process. In this case, there is no in the picture that receives two messages from the same originating process. So, FIFO delivery byitself will not prevent the multiple processes making causality issues.

Yet, this is causal delivery violation. When one process broadcast messages to multiple destinations, this kind of anomaly WILL happen and it involves at least 3 nodes.

Totally-ordered delivery

If a process delivers message m1 then m2, then ALL processes deliverying both m1 and m2 deliver m1 first.

Let's look at the following example where two clients are setting the values to distributed storage(you can think of key value store and the like.)

Here, two client try to set each different value to the same key and the messages are delivered in opposite orders. So, on the P1, the result will be x=2 and x=1 for the P2. - this is what's called total order anomaly.

Prevention of total over anomaly

Use of coordinator

Any time a client wants to send a message, what if we have yet another process called coordinator and the client has to check in with that process and then the process tells the other processes the order in which to deliver the messages so they all agree.

This is obviosly one way of enforcing totally-ordered delivery but it is slow as the coordinator is a bottleneck. I will come back to this topic in differnt post.

Hierarch of delivery guarantees

Now we have defined different kind of delivery guarantees, we can try to put these delivery protocols in a hierarchy.

We learned that violation of FIFO delivery is also a violation of causal delivery. And there was a case where causal anomaly happens but it wasn't FIFO delivery violation. What it means is, if we ensure of causal delivery, there won't be FIFO violation.

The same thing happens between causal delivery and totally-ordered delivery? Unfortunately NOT.

Totally-ordered delivery is defined only from the delivery perspective, not considering send order, by definition. So it has its own branch in hierarchy as follows:

Next...

In the next post, I'll be covering actual implementation of each guarantees.