> For the complete documentation index, see [llms.txt](https://dianadarie.gitbook.io/system-design-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dianadarie.gitbook.io/system-design-notes/system-design-patterns/vector-clocks.md).

# Vector Clocks

### Motivation

When a distributed system allows concurrent writes, it can result in multiple versions of an object. Different replicas of an object can end up with different versions of the data.

On a single machine, all we need to know about is the absolute or **wall clock** time: suppose we perform a write to key `k` with timestamp `t1`, and then perform another write to `k` with timestamp `t2`. Since `t2 > t1`, the second write must have been newer than the first write, and therefore, the database can safely overwrite the original value.

In a distributed system, this assumption does not hold true. The problem is **clock skew** – different clocks tend to run at different rates

### Solution

Use Vector clocks to keep track of value history and reconcile divergent histories at read time. 

A vector clock is effectively a `(node, counter)` pair. One vector clock is associated with every version of every object. 

* If the counters on the first object’s clock are less-than-or-equal to all of the nodes in the second clock, then the first is an ancestor of the second and can be forgotten. 
* Otherwise, the two changes are considered to be in conflict and require reconciliation. 
  * Such conflicts are resolved at read-time, and if the system is not able to reconcile an object’s state from its vector clocks, it sends it to the client application for reconciliation

### Applications

Amazon’s **Dynamo** uses Vector Clocks to reconcile concurrent updates.