Version Vectors and Causality
What you'll learn: How version vectors track event relationships across replicas to identify which updates genuinely conflict versus those that happened sequentially.
The Problem with Timestamps Alone
Imagine three people editing a shared document from different locations. Alice makes a change, Bob sees it and adds more, while Carol—offline—edits the original. When Carol reconnects, how do you know her edit conflicts with Bob's work but not necessarily with Alice's?
Simple timestamps fail here because clocks drift. Enter version vectors.
What Are Version Vectors?
A version vector is a data structure where each replica maintains a counter for every replica in the system. When replica A makes a change, it increments only its own counter. The vector travels with the data.
Replica A: [A:3, B:1, C:2] // A has seen 3 of its own ops, 1 from B, 2 from C
Replica B: [A:2, B:4, C:2] // B has seen 2 from A, 4 of its own, 2 from C
Detecting Causality
Version vectors answer: "Did update X happen before, after, or concurrently with update Y?"
- X happened before Y if every counter in X's vector ≤ Y's vector (and at least one is strictly less)
- Concurrent if neither vector dominates the other—these are true conflicts needing resolution
Example:
[A:3, B:1]happened before[A:5, B:2](causal, no conflict)[A:3, B:1]and[A:2, B:2]are concurrent (conflict!)
Unlike Last-Write-Wins which loses data silently, version vectors preserve both concurrent updates, letting the application or user resolve them meaningfully.
Key Takeaway: Version vectors track causality by recording each replica's logical clock, enabling systems to distinguish between sequential updates (no conflict) and truly concurrent ones (actual conflict requiring resolution).