Distributed systems: partial orders and Lamport 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

• A synchronous network is one where message delivery time is bounded. An asynchronous network is one where it is not.
• A "happens before" relation describes the order of events in a distributed system:
  • If $A$ appears before $B$ in the same process, then $A \to B$;
  • If $A$ is a send and $B$ is the corresponding receive, then $A \to B$;
  • If $A \to B$ and $B \to C$, then $A \to C$.
• A partial order is a set $S$ with a binary relation $\le$ with the following properties:
  • Reflexive: $a \le a$;
  • Antisymmetric: if $a \le b$ and $b \le a$, then $a = b$;
  • Transitive: if $a \le b$ and $b \le c$, then $a \le c$.
• The " $\to$ " relation is a partial order without reflexivity.
• Lamport clocks:
  • To assign Lamport clocks to events:
    • Initialize counter to 0 for all processes.
    • Increment the counter on each event.
    • Send the counter with every message.
    • When receiving a message, set counter to $1+\max(\text{own counter},\text{received counter})$.
  • If $A \to B$, then $\operatorname{LC}(A) \le \operatorname{LC}(B)$.

References

1. UCSC CSE138 spring 2020 lecture 3: Lamport diagrams, causality, network models, partial orders [video]
2. UCSC CSE138 spring 2020 lecture 4: Lamport clocks [video]