Vector Clock
Subject: Computer and Technology noun /ˈvɛk.tər klɑːk/ 1 definition
- distributed-systems
- concurrency-control
- data-consistency
- computer-science
-
Definition (noun)
Entry #359 · UpdatedA Vector Clock is a logical timekeeping mechanism used in distributed systems to determine the partial causal ordering of events without relying on synchronized physical clocks. Every participating process maintains a vector of integer counters—one slot per process—incrementing its own entry on local and send events, attaching a copy of its vector to outgoing messages, and updating each entry to the element-wise maximum upon receiving a message before incrementing its local counter. Comparing two vector timestamps reveals whether one event causally precedes another—when every counter in the first is less than or equal to its counterpart in the second and at least one is strictly smaller—or whether the two events occurred concurrently because each vector holds at least one entry strictly greater than the other's. Unlike scalar Lamport timestamps, which cannot distinguish independent concurrent actions from causally dependent chains, vector clocks provide exact causality tracking for optimistic replication and conflict detection, though their metadata overhead grows linearly with the number of distinct writers or nodes.
Common Forms
Fixed-Array Vector Clocks: Maintains a static integer array indexed by known process IDs, delivering compact storage and fast element-wise comparisons in closed, fixed-membership clusters.
Sparse Map Vector Clocks: Stores counters as dynamic
(actor_id, counter)key-value maps rather than positional arrays, accommodating fluctuating cluster membership and omitting inactive nodes whose implicit counts remain zero.Version Vectors: Applies vector-clock causality tracking exclusively to replicated data mutations rather than all process events, enabling leaderless key-value stores to identify stale overwrites and flag conflicting object siblings.
Dotted Version Vectors (DVV): Pairs a shared server-side version vector with a single
(node_id, counter)dot for each write, preventing metadata explosion when transient clients submit concurrent updates in systems like Riak.
Example
In a Dynamo-style distributed key-value store, node
N1handles aPUT /cart/42write with vector{N1: 1, N2: 0}and replicates it toN2, after which a network partition causesN1to accept a follow-up update stamped{N1: 2, N2: 0}whileN2concurrently processes a separate client write stamped{N1: 1, N2: 1}. When the partition heals and a coordinator executes a quorumGET /cart/42, comparing the two vectors reveals that neither dominates the other (N1: 2 > 1whileN2: 0 < 1), prompting the database to return both sibling states for conflict resolution rather than silently overwriting either update.