Overview

Timestamps from physical clocks can be inconsistent with causality, even if those clocks are synchronized using NTP

In contrast, logical clocks are designed to capture causal dependencies by counting the number of events occurred

Lamport Timestamps

Each node maintains a timestamp (counter): $t$
On any event occurring at the node: $t = t + 1$
On sending the message $m$ : $t = t + 1$ ; $se n d (t, m)$
On receiving $(t^{'}, m)$ : $t = ma x (t, t^{'}) + 1$

The algorithm assumes a crash-stop model (or a crash-recovery model if the timestamp is maintained in a permanent storage)

Let $L (e)$ be the value of $t$ after the event $e$

If $a \to b$ then $L (a) < L (b)$
However, $L (a) < L (b)$ does not imply $a \to b$ ; Possible that $L (a) = L (b)$ for $a \neq = b$

Ordering

Using Lamport timestamps we can extend the happens-before partial order into a total order

We use the lexicographic order over (timestamp, node name) pairs: that is, we first compare the timestamps, and if they are the same, we break ties by comparing the node names:

Let $N (e)$ be the name of the node at which event $e$ occurred. Then the pair $(L (e), N (e))$ uniquely identifies event $e$
Define a total order $≺$ using Lamport timestamps: $(a ≺ b) ⟺ (L (a) < L (b) \lor (L (a) = L (b) \land N (a) < N (b)))$

Properties:

This relation $≺$ puts all events into a linear order: for any two events $a \neq = b$ we have either $a ≺ b$ or $b ≺ a$
It is a causal order: $(a \to b) ⟹ (a ≺ b)$
Given Lamport timestamps $L (a)$ and $L (b)$ with $L (A) < L (b)$ we can’t tell whether $a \to b$ or $a ∥ b$ ; That is, we can’t tell whether two events are concurrent

Vector Clocks

Vector clocks allow us to detect when events are concurrent. While Lamport timestamps are just a single integer (possibly with a node name attached), vector timestamps are a list of integers, one for each node in the system

Assume $n$ nodes in the system: $N = ⟨ N_{1}, N_{2}, \dots, N_{n} ⟩$
Each node $N_{i}$ maintains a vector timestamp $T$ of size $n$ ; Initially all zeros: $T = ⟨ 0, 0, \dots, 0 ⟩$
On any event occurring at node $N_{i}$ : $T [i] = T [i] + 1$
On sending the message $m$ at node $N_{i}$ : $T [i] = T [i] + 1$ ; $se n d (T, m)$
On receiving $(T^{'}, m)$ at node $N_{i}$ : $T [j] = ma x (T [j], T^{'} [j])$ for every $j \in {1, \dots, n}$ ; $T [i] = T [i] + 1$

Ordering

Define the following order on vector timestamps in the system with $n$ nodes:

$T = T^{'}$ iff $T [i] = T^{'} [i]$ for all $i \in {1, \dots n}$
$T \leq T^{'}$ iff $T [i] \leq T^{'} [i]$ for all $i \in {1, \dots n}$
$T < T^{'}$ iff $T \leq T^{'}$ and $T \neq = T^{'}$
$T ∥ T^{'}$ iff $T ≰ T^{'}$ and $T^{'} ≰ T$

Define vector timestamp of event $a$ as $V (a) = ⟨ t_{1}, \dots, t_{n} ⟩$

$V (a) \leq V (b)$ iff $({a} \cup {e ∣ e \to a}) \subseteq ({b} \cup {e ∣ e \to b})$

$(V (a) < V (b)) ⟺ (a \to b)$
$(V (a) = V (b)) ⟺ (a = b)$
$(V (a) ∥ V (b)) ⟺ (a ∥ b)$

The partial order over vector timestamps corresponds exactly to the partial order defined by the happens-before relation

Dotted Version Vectors

TODO

🪴 Quartz 4.0

Explorer

Logical Clocks

Overview

Lamport Timestamps

Ordering

Vector Clocks

Ordering

Dotted Version Vectors

References

Graph View

Table of Contents

Backlinks