Distributed systems: causal broadcast

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

Causal broadcast is an algorithm for implementing causal delivery. Recall that if $m_1$'s send happens before $m_2$'s send, then under causal delivery $m_1$ must be delivered before $m_2$ (with respect to the happens before relation). Here is the causal broadcast algorithm:

1. Initialize a local clock to $[0,0,...,0]$ for each process.
2. If a message from $P_1$ is delivered at $P_2$ (recall that this is different from it being received), then increment $P_2$'s local clock in the $P_1$ position.
3. If a message is to be sent from $P_1$, increment its own position in its local clock, then include the local clock when sending the message.
4. A message from $P_1$ is only delivered at $P_2$ if: a. The $P_1$ position in the message's timestamp must be one greater than the $P_1$ position in $P_2$'s local clock. That is is, this must be the next expected messages from $P_1$. b. All other positions of the message's timestamp must be less than or equal to the corresponding positions in $P_2$'s local clock. That is, there must be no missing messages from other processes.

Causal ordering can also be used to find a consistent global snapshot of a system. One algorithm to do this is the Chandy-Lamport algorithm. This will be discussed in the next lecture.

References

1. UCSC CSE138 spring 2020 lecture 7: causal broadcast [video]