Lamport Clocks and Vector Clocks

In a distributed system, physical "wall clocks" cannot be perfectly synchronized. Network delay and hardware variability mean that two nodes may disagree on which of two events happened first. To solve this, distributed systems use **Logical Clocks** to capture the **Happens-Before** relationship ($\rightarrow$).

1. Lamport Clocks: Partial Ordering

Introduced by Leslie Lamport in 1978, the Lamport Clock is a simple monotonic counter maintained by each process.

The Algorithm

1. **Local Event:** Each process increments its local counter: $C_i = C_i + 1$.

2. **Send Message:** The process attaches its counter $T = C_i$ to the message.

3. **Receive Message:** The receiver updates its counter: $C_j = \max(C_j, T) + 1$.

Limitation: Causality Loss

If $a \rightarrow b$, then $C(a) < C(b)$. However, the reverse is **not** true: if $C(a) < C(b)$, we cannot conclude that $a$ caused $b$. They might be concurrent events that just happened to receive those numbers.

2. Vector Clocks: Tracking Causality

**Vector Clocks** extend Lamport clocks to provide a full causal history. Instead of a single number, each node maintains a vector (an array) of counters, one for every node in the system.

The Algorithm

A cluster of $N$ nodes maintains a vector $V[1..N]$.

1. **Local Event:** Node $i$ increments its own index: $V[i] = V[i] + 1$.

2. **Send Message:** Node $i$ sends its entire vector $V$ with the message.

3. **Receive Message:** The receiver $j$ updates every element: $V_j[k] = \max(V_j[k], V_{msg}[k])$ for all $k$.

Conflict Detection

Vector clocks allow us to determine if two events are:

* **Causally Related:** $V(a) < V(b)$ if every element of $V(a) \le V(b)$ and at least one element is strictly smaller.

* **Concurrent (Conflict):** Neither $V(a) < V(b)$ nor $V(b) < V(a)$. This indicates that the events happened independently and their states must be merged.

3. Comparison and Utility

| Feature | Lamport Clock | Vector Clock |

| :--- | :--- | :--- |

| **Size** | $O(1)$ (Scales perfectly) | $O(N)$ (Grows with node count) |

| **Causality** | No (Partial ordering only) | **Yes** (Identifies concurrency) |

| **Primary Use** | Total ordering of events. | Conflict resolution (e.g., Dynamo). |

4. Modern Evolution: Dotted Version Vectors (DVV)

In 2026, systems like **Riak** use an optimized version called **Dotted Version Vectors**. DVVs prevent "sibling explosion" by distinguishing between the *causal past* and the *current event* (the "dot"). This allows for more precise conflict resolution with less metadata overhead than classic vector clocks.