← Back to glossary

Vector Clocks — Distributed Causality

architecture Advanced

Also Known As

vector clock Lamport timestamp logical clock causal ordering

TL;DR

A vector clock is a data structure — one counter per node — that tracks causal ordering of events across distributed nodes without a shared clock, enabling detection of concurrent events and causal relationships.

Explanation

Physical clocks on different machines drift and cannot reliably order events. A vector clock assigns each node an integer counter. When a node processes an event it increments its own counter. When it sends a message, it attaches its current vector. On receiving a message, the recipient merges the vectors by taking the maximum of each position, then increments its own. Given two vector clocks VC(A) and VC(B): if every position of VC(A) is ≤ VC(B) and at least one is strictly less, A causally precedes B. If neither dominates the other, the events are concurrent — no causal relationship exists. Amazon Dynamo used vector clocks for conflict detection. DynamoDB, Riak, and many distributed databases use vector clock variants.

Common Misconception

✗ Lamport timestamps are the same as vector clocks. Lamport timestamps are scalar — they provide a total order but cannot detect concurrency. Vector clocks are per-node — they can detect when two events are truly concurrent (neither happened before the other).

Why It Matters

Distributed systems cannot rely on wall-clock time to order events — NTP synchronisation has millisecond-level drift and events that happen 'at the same time' on different nodes cannot be ordered. Vector clocks provide a mathematically correct way to determine 'A happened before B' or 'A and B happened concurrently', which is essential for conflict detection in eventually consistent databases.

Common Mistakes

Using Lamport timestamps when you need concurrency detection — scalar Lamport clocks provide ordering but cannot tell you two events were concurrent.
Not including the vector clock when sending messages — causality is only tracked if the clock travels with the data.
Unbounded vector clock growth — in systems with many nodes, vectors grow indefinitely; use version vectors or bounded variants for production.
Conflating 'concurrent' with 'conflicting' — concurrent events are not necessarily in conflict; application logic determines whether a conflict needs resolution.

Code Examples

✗ Vulnerable

// ❌ Using wall-clock timestamps to order distributed events
$event = [
    'data'      => $payload,
    'timestamp' => microtime(true), // Different servers have different clocks
];
// Events from two nodes with 50ms clock skew cannot be ordered correctly
// 'Last write wins' based on this timestamp loses causally later updates

✓ Fixed

<?php
// ✅ Vector clock implementation
class VectorClock
{
    private array $clock = []; // nodeId => counter

    public function increment(string $nodeId): void
    {
        $this->clock[$nodeId] = ($this->clock[$nodeId] ?? 0) + 1;
    }

    public function merge(VectorClock $other): VectorClock
    {
        $merged = clone $this;
        foreach ($other->clock as $nodeId => $count) {
            $merged->clock[$nodeId] = max($merged->clock[$nodeId] ?? 0, $count);
        }
        return $merged;
    }

    public function isConcurrentWith(VectorClock $other): bool
    {
        $aLessB = false;
        $bLessA = false;
        $allNodes = array_unique(array_merge(array_keys($this->clock), array_keys($other->clock)));
        foreach ($allNodes as $node) {
            $a = $this->clock[$node] ?? 0;
            $b = $other->clock[$node] ?? 0;
            if ($a < $b) $aLessB = true;
            if ($b < $a) $bLessA = true;
        }
        return $aLessB && $bLessA; // Neither dominates → concurrent
    }
}

Vector Clocks — Distributed Causality

Also Known As

TL;DR

Explanation

Common Misconception

Why It Matters

Common Mistakes

Code Examples

References

Tags

Vector Clocks — Distributed Causality

Also Known As

TL;DR

Explanation

Common Misconception

Why It Matters

Common Mistakes

Code Examples

References

Tags

Related Terms