shreyansh

Version Vector →

30-Second Glance

  • A version vector is one counter per node tracking how many updates from each node a replica has seen.
  • Compare slot-wise: equal means same history; A ≤ B with one slot strictly less means A happened-before B; otherwise concurrent.
  • Concurrency (e.g. [3,1,0] vs [2,2,1]) is the conflict signal — merge, pick, or escalate per application policy.
  • The note's worked trio ([2,1,0] → [2,2,0] → [2,2,1]) shows clean causal succession; the divergent pair shows the fork.
  • Used wherever replicas diverge: distributed DBs, version control, any multi-writer reconciliation path.

Introduction

Version vectors are a mechanism used in distributed systems to track the version history of replicated data across multiple nodes. They help in determining the causality relationship between different versions of data, allowing systems to resolve conflicts and ensure consistency.

Screenshots/9fc374821a5c5a6e872d1cfa0d55394d_MD5.jpeg
  1. Vector of Timestamps:
    1. A version vector is essentially an array (or vector) of counters, with each counter representing a node in the distributed system.
    2. Each counter tracks the number of updates (or events) that have been processed by that particular node.
  2. Causal Relationships:
    1. Version vectors help in determining the causal relationship between different versions of the same data on different nodes.
    2. For example, if the version vector of one node is [3, 2, 1] and another is [2, 2, 1], it can be inferred that the first node has seen one more update on the first counter (first node) than the second.
  3. Comparison of Version Vectors:
    1. Equal: Two version vectors are equal if all their counters are identical, indicating that the two nodes have seen the exact same set of updates.
    2. Happened-Before: A version vector A is said to have “happened before” version vector B if all counters in A are less than or equal to their corresponding counters in B, and at least one counter is strictly less. This indicates that A’s state is an earlier version of B’s state.
    3. Concurrent: If neither vector A happened before vector B nor B happened before A, they are considered concurrent. This means the two nodes have seen different sets of updates, and neither is strictly more recent than the other.
  4. Conflict Detection:
    1. Version vectors are used to detect conflicts when merging data from different nodes.
    2. If two version vectors are concurrent, it indicates that the updates were made independently, and some form of conflict resolution is needed.
  5. Use in Distributed Systems:
    1. Version vectors are commonly used in distributed databases, version control systems, and other distributed environments where data replication and consistency are important.
    2. They allow the system to reconcile differences between replicas, ensuring that no updates are lost and that the data remains consistent across all nodes.

Example: Imagine a distributed system with three nodes A, B, and C. Each node has a version vector representing the number of updates it has seen:

  • Node A’s version vector: [2, 1, 0]

  • Node B’s version vector: [2, 2, 0]

  • Node C’s version vector: [2, 2, 1]

  • B has seen one more update on node B’s counter than A. Hence, B’s state includes all the updates that A has seen, plus more.

  • C has seen an additional update on node C’s counter. Therefore, C’s state is more recent than B’s.

  • If node A had a version vector [3, 1, 0], it would be concurrent with node C’s version vector [2, 2, 1] since neither is strictly “newer” than the other; they have seen different updates. This concurrency would require conflict resolution (merging the states from both nodes, choosing one version over the other, or using a specific conflict resolution strategy depending on the application’s needs).

Trade-offs

Approach Pros Cons Use when
Version vectors Precise causality + concurrency detection; no update loss on detect O(nodes) counters per object; comparison and pruning overhead Multi-leader/leaderless conflict detection
Lamport clock O(1) state, simple ordering Can't prove concurrency Causal ordering without conflict diagnosis
Last Write Wins by wall clock O(1), trivial Skew-driven data loss Caches, disposable data
Central log / sequencer No vectors needed; total order Bottleneck; availability hit Single-writer or consensus-backed logs

Interview One-Liners

Q: What is a version vector? A: An array with one counter per node recording how many updates from each node this replica has observed.

Q: How do you compare two vectors? A: Equal counters = identical history; all-less-or-equal with one strictly less = happened-before; otherwise concurrent.

Q: Walk the note's example. A: [2,1,0] → [2,2,0] → [2,2,1] is causal succession (each sees everything before plus more); [3,1,0] vs [2,2,1] is concurrent — neither dominates.

Q: What does "concurrent" demand? A: Conflict resolution: merge states, choose a winner, or surface siblings to the application.

Q: Where are version vectors used? A: Distributed databases, version control systems, and anywhere replicated data must reconcile without losing updates.

Q: What do they cost? A: A counter per node per tracked object — precise but heavier than a single Lamport clock or wall-clock stamp.