Skip to content
AfluidityAlgorithm Atlas
Distributed ConsensusAll categories
CoreConcept & Pseudocode Entry

Vector Clocks

Tracks exact causal history across N distributed nodes using an N-element counter vector to detect both causal ordering and concurrent conflicts.

Explore relationshipsOpen 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Distributed Consensus
Difficulty
Intermediate
Family
Distributed Consensus
Tier
Core
Status
Reviewed
Review
AI Reviewed
Sources
1
Formulas
2
Relationships
2
Code example
Not ready
Visualization
Ready
Aliases
Vector Timestamps, Causal Vector Clocks, Version Vectors

Overview

Vector Clocks maintain an array V[1..N] of logical timestamps per node. By merging vectors element-wise on message receipt, any two events can be tested for exact causal precedence (V(a) < V(b)) or concurrency/conflict (neither V(a) <= V(b) nor V(b) <= V(a)).

Core Concepts

causal historyelement-wise maximum mergeconcurrent conflict detectionpartial order

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(N) per message merge/compare

Average

O(N) per message merge/compare

Worst

O(N) per message merge/compare

Space

O(N) per event/version

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Vector Clocks across input scales.

Input Scale N:
JIT-compiled JS/TS (~350M primitive ops/sec)
Est. Average TimeO(N) per message merge/compare

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Worst-Case TimeO(N) per message merge/compare

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops
Est. Working MemoryO(N) per event/version

1.53 MB

Standard Heap FitN=100,000

When to Use

  • Distributed vector logical clock algorithm that tracks causal history across N nodes with an N-element timestamp array to detect both causal ordering and concurrent write conflicts.
  • Use it in leaderless or multi-master replicated storage systems to surface sibling versions for reconciliation.

When Not to Use

  • Avoid Vector Clocks when a simple scalar ordering suffices and O(N) metadata per message is too large; use Lamport Logical Clocks instead.

What It Does

  • Captures exact causal happens-before relationships (a -> b iff V(a) < V(b))
  • Detects concurrent conflicting writes across distributed replicas without a central coordinator

Use Cases

  • Conflict detection in eventually consistent distributed key-value stores (Dynamo, Riak)
  • Causal broadcast and causal consistency in distributed databases
  • Distributed debugging and race detection across message-passing processes

Inputs

  • N distributed nodes, local events, and messages carrying sender vector V_msg[0..N-1]

Outputs

  • Vector timestamp V[0..N-1] per event and causal comparison (before, after, or concurrent)

Key Formulas (2)

Exact causal order

a → b iff V(a) < V(b)
a -> b iff V(a) < V(b)

Vector clocks characterize causal precedence in both directions.

Component-wise merge

Vrecv[k] = max(Vlocal[k], Vmsg[k])
V_recv[k] = max(V_local[k], V_msg[k])

Merges causal knowledge from the sender across all N nodes.

Pseudocode

  1. 1.Initialize V[0..N-1] = 0 on each node i
  2. 2.On local event at node i: V[i] = V[i] + 1
  3. 3.On sending message from node i: V[i] = V[i] + 1; send copy of V
  4. 4.On receiving V_msg at node i: for k in 0..N-1: V[k] = max(V[k], V_msg[k]); then V[i] = V[i] + 1
  5. 5.Compare V1 and V2: V1 < V2 iff all V1[k] <= V2[k] and some V1[k] < V2[k]; otherwise if neither V1 <= V2 nor V2 <= V1, events are concurrent

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

  1. Initialize V[0..N-1] = 0 on each node i
  2. On local event at node i: V[i] = V[i] + 1
  3. On sending message from node i: V[i] = V[i] + 1; send copy of V
  4. On receiving V_msg at node i: for k in 0..N-1: V[k] = max(V[k], V_msg[k]); then V[i] = V[i] + 1
  5. Compare V1 and V2: V1 < V2 iff all V1[k] <= V2[k] and some V1[k] < V2[k]; otherwise if neither V1 <= V2 nor V2 <= V1, events are concurrent

Canonical Example

Input
V(a) = [2, 0, 0] on Node 0; V(b) = [0, 1, 0] on Node 1
Output
Concurrent (V(a) || V(b)) — neither vector dominates the other
Explanation
Because V(a)[0] > V(b)[0] but V(a)[1] < V(b)[1], the two updates happened concurrently without causal knowledge of each other.

Implementation Notes

  • Node i increments V[i] before sending a message and on local events.
  • On receiving V_msg at node i, set V[k] = max(V[k], V_msg[k]) for all k, then increment V[i].

Common Pitfalls

  • Confusing element-wise <= with strict causal precedence: V(a) < V(b) requires V(a)[k] <= V(b)[k] for all k AND V(a)[k] < V(b)[k] for at least one k.
  • Allowing unbounded vector growth when ephemeral client IDs are used instead of bounded server replica IDs.

Interactive Mechanism Walkthrough & State Debugger

Graph Frontier & Edge Relaxation

Shows N-component vector timestamps evolving across message exchanges and highlights concurrent branches.

Vector Clocks mechanism walkthrough step 1 of 5suvwxt
active vertexs
visited set V{ s }
frontier queue[ u ]
edges relaxed0 / 7
Step 1 of 5: Initialize V[0..N-1] = 0 on each node i
timeline

Notes

Independently developed by Colin Fidge (1988) and Friedemann Mattern (1988).

Sources (1)

What each reference supports for this entry.

Mattern (1988) — Virtual Time and Global States of Distributed Systems

Paper

Foundational paper introducing vector time and causal concurrency detection.

Open source

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Variant ofLamport Logical Clocks

Distributed Consensus · Core

Extends scalar Lamport timestamps to an N-vector so causal precedence becomes an if-and-only-if condition.

Compare with this

Relationships

View full relationship page
Variant ofLamport Logical Clocks

Extends scalar Lamport timestamps to an N-vector so causal precedence becomes an if-and-only-if condition.

Related Algorithms

Lamport Logical ClocksRaft Distributed ConsensusPaxos Consensus

Tags

Distributed SystemsConsensusScheduling