Skip to main content
Definition Website Computer and Technology

Vector Clock

Subject: Computer and Technology noun /ˈvɛk.tər klɑːk/ 1 definition

  1. Definition (noun)

    Entry #359 · Updated

    A 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 N1 handles a PUT /cart/42 write with vector {N1: 1, N2: 0} and replicates it to N2, after which a network partition causes N1 to accept a follow-up update stamped {N1: 2, N2: 0} while N2 concurrently processes a separate client write stamped {N1: 1, N2: 1}. When the partition heals and a coordinator executes a quorum GET /cart/42, comparing the two vectors reveals that neither dominates the other (N1: 2 > 1 while N2: 0 < 1), prompting the database to return both sibling states for conflict resolution rather than silently overwriting either update.