Lamport Timestamps and Vector Clocks

Goal: Order events across different processes in a distributed system setting.
Clock synchronization is a hard problem (network latencies matter). What if we assign timestamp to events that are not absolute time? As long as these timestamps obey causality, this method should work. That is, if an event A causally happens before another event A, then $timestamp(A) < timestamp(B)$.

Lamport timestamps were proposed by Leslie Lamport in 1970s. Lamport timestamps defines a logical relation Happens-Before (denoted as $\rightarrow$) among a pair of events.

Happens-Before obeys three rules:

1. 1. On the same process, $a \rightarrow b$, if $time(a) < time(b)$, using a local clock.
2. 2. If p1 sends a message m to p2, $send(m) \rightarrow receive(m)$.
3. 3. Transitivity: if $a \rightarrow b, b \rightarrow c$ then $a \rightarrow c$.

Not all events are ordered by $\rightarrow$, in other words, Happens-Before defines a partial order on the event ordering. Consider the example in Figure 1 below.

Figure 1

How do we assign Local timestamps?

• 1. Each process has a local counter which is an integer initialized to $0$
• 2. A process increments this counter when
  • a) An instruction happens in it.
  • b) Sends a message to other process.
• 3. The send message event carries this timestamp.
• 4. For a receive message event, the counter is updated by $max(local clock, message timestamp) + 1$.

Figure 2

Following the above rules, we get the following log:

• Each process starts from $0$.
• $P1$ executes an instruction and increments its timestamp to $1$.
• Similarly, $P3$ also increments its timestamp to $1$ and sends a message to $P2$ with this timestamp.
• When $P2$ receives this message, it does $max(0,1) + 1 = 2$.
• $P1$ then sends a message with timestamp $2$.
• $P2$ receives this message, it does $max(2,2) + 1 = 3$.
• $P2$ sends a message to $P1$, $P1$ does $max(4,3) + 1 = 5$.
• Similarly, $P3$ will do $max(2,6) + 1 = 7$.

These timestamps follow the causal ordering depicted in Figure 1. At the same time, $A$ and $I$ which have the same timestamp are not causally related, these are concurrent events. Similarly, $I$ and $C$ are not causally related, but $timestamp(I) < timestamp(C)$. In other words, we have

$E1 \rightarrow E2 \implies timestamp(E1) < timestamp(E2)$

$timestamp(E1) < timestamp(E2) \implies {E1 \rightarrow E2}$  or ($E1$ and $E2$ are concurrent)}

Can we do better and get a stronger condition ? This leads us to Vector clocks which are very commonly used in distributed systems like Amazon Dynamo.

Instead of maintaining a single number, each process now maintains a vector of integers.
If there are N process 1..N , each vector has N elements.
That is a process $P_i$ , maintains a vector $V_i[1..N]$
$V_i{[j]}$ denotes process $i$'s knowledge of latest events at process $j$.

Rules for incrementing vector clocks:

• 1. When an instruction executes or a message is sent at process $i$, increment $i^{th}$ element of its vector clock.
• 2. Each message carries the sends events timestamp V[1.....N]
• 3. On receiving a message at process $i$:
  • $V_i{[i]}$ = $V_i{[i]}$+ 1 (local increment)
  • $V_i{[j]}$ = max($V_{message}{[j]}$, $V_i{[j]}$)   for j != i (update the knowledge about the other processes

For the example above, the vector clocks look like:

Figure 3

Log:

• $A$: $P1$ increments the first value in the vector (first value represents $P1$)
• $H$: $P3$ increments the third value in its vector(third value represents $P3$)
• $E$: $P2$ increments the second value in its vector, and does a max for all indices.
• $D$: $P1$ receives $(2,3,1)$ from $P2$. It increments its own counter value in its vector from $3$ to $4$, and then its takes the max value for the other indices making its vector $(4,3,1)$

Rules for causality:

• Two vectors $V1$ and $V2$ are equal iff $V_1[i]$ == $V_2[i]$ for all i = 1....N
• Two events are causally related iff
  • $V1 < V2$ iff $V1<= V2$ and there exists $j$ such that $1 <= j <= N$ and $V_1{[j]}$ < $V_2{[j]}$
• Two events $V1$ and $V2$ are concurrent iff
  • NOT($V1 <= V2$) and NOT($V2 <= V1$) denoted as $V1$ ||| $V2$

In the above event log,

• $B \rightarrow F$ :: $(2,0,0) < (2,2,1)$
• $A \rightarrow F$ :: $(1,0,0) < (2,2,1)$
• $F \rightarrow J$ :: $(2,2,1) <( 5,3,3)$
• $C$ and $F$ :: $(3,0,0) ||| (2,2,1)$
• $H$ and $C$ :: $(0,0,1) ||| (3,0,0)$

References:
https://www.coursera.org/learn/cloud-computing/