Distributed systems: vector clocks

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

Vector clocks are similar to Lamport clocks, but make a stronger guarantee: for events $A$ and $B$, $A \to B$ if and only if $\operatorname{VC}(A) < \operatorname{VC}(B)$. Vector clocks are assigned as follows:

• For each process, initialize a (local) length- $n$ vector to all zero, where $n$ is the number of processes.
• If process $p$ has an event, increment position $p$ of process $p$'s counter by 1.
• If process $p$ sends a message, increment position $p$ of its counter by 1 and send the counter with the message.
• If process $q$ receives a message, increment position $q$ of process $q$'s counter by 1 and take the elementwise maximum with the received counter.

If $\operatorname{VC}(A)$ and $\operatorname{VC}(B)$ are vector clocks, then we define $\operatorname{VC}(A) < \operatorname{VC}(B)$ if and only if $\operatorname{VC}(A)_i \le \operatorname{VC}(B)_i$ for all $i$ and $\operatorname{VC}(A) \ne \operatorname{VC}(B)$.

References

1. UCSC CSE138 spring 2020 lecture 5: vector clocks [video]