Distributed systems: delivery guarantees

These are my notes for Lindsey Kupuer's spring 2020 distributed systems course.

1. Lecture 3/4 - partial orders and Lamport clocks
2. Lecture 5 - vector clocks
3. Lecture 6 - delivery guarantees
4. Lecture 7 - causal broadcast

A channel is the connection between two processes. A message can be queued when it is received on a channel and later delivered to a process.

An example is FIFO delivery, where a message is queued until all messages that were sent before it (with respect to the sender's local clock) have been received. A FIFO anomaly is when message $A$ is sent before $B$, but $B$ is received first. This is also a causal anomaly. FIFO delivery can be implemented by tagging messages with a sender ID and a sequence number that is locally incremented on each send. If we receive a message with sender ID and sequence number $(p,s)$, we queue it until $(p,s-1)$ is delivered. This algorithm assumes reliable delivery: it fails if messages can be lost. FIFO delivery can also be implemented using acknowledgements. If $A$ sends a message to $B$, it waits for an acknowledgement from $B$ before sending its next message. In practice, many protocols use TCP to implement FIFO delivery.

Another example of a delivery guarantee is causal delivery: if $m_1$'s send happens before (see lectures 3/4 for definition) $m_2$'s send, then $m_1$'s delivery happens before $m_2$'s delivery. It can be implemented by attaching vector clocks to each message sent; this will be discussed in the next lecture.

In totally-ordered delivery, if a process delivers $m_1$ before $m_2$, then all processes deliver $m_1$ before $m_2$. This ensures messages appear in the same order on all processes. A FIFO anomaly isn't a total order violation. This gives us a hierarchy of delivery guarantees:

$$\text{causal} \implies \text{FIFO} \implies \emptyset$$

$$\text{totally-ordered} \implies \emptyset$$

References

1. UCSC CSE138 spring 2020 lecture 6: delivery guarantees [video]