Memory Version Vector

A Memory Version Vector's primary function is to track the causal history of updates. Each node in the system maintains a vector—a set of counters, one per node. When a node updates a data item, it increments its own counter in the vector. By comparing vectors from different replicas, the system can determine if one update happened-before another, if they are concurrent, or if they are identical.

• Example: If Vector A = {Node1:3, Node2:1} and Vector B = {Node1:3, Node2:2}, then B's version is causally newer than A's (it includes A's updates plus one more from Node2).
• If vectors are incomparable (e.g., A = {N1:2, N2:1} and B = {N1:1, N2:2}), the updates are concurrent and require conflict resolution.

Version vectors enable automatic detection of write-write conflicts. When two nodes independently modify the same data item without communicating (a concurrent write), their version vectors become incomparable. Neither is strictly greater than the other; they have diverged.

• This detection is crucial for systems like collaborative document editors, distributed databases (e.g., Dynamo, Riak), and multi-agent memory systems.
• Upon detecting concurrent versions, the system must employ a conflict resolution strategy, such as last-write-wins (LWW) with tie-breaking, application-specific merging, or preserving both as sibling versions.

Version vectors create a partial order over events, not a total order. This is a key distinction from simple timestamps or sequence numbers. They are an implementation of the broader vector clock concept, specifically applied to tracking versions of data objects.

• Logical, Not Physical: Ordering is based on causal relationships, not wall-clock time, which is unreliable in distributed systems.
• Mechanism: A vector V for a data item is a map {node_id: counter}. The comparison rules are:
  • V1 = V2 if all counters are equal.
  • V1 < V2 if for all nodes, V1[node] <= V2[node] and for at least one node, V1[node] < V2[node].
  • V1 is concurrent with V2 if neither V1 <= V2 nor V2 <= V1.

In long-running systems, version vectors can grow unbounded as the number of nodes changes (e.g., nodes joining/leaving). Vector pruning is necessary to remove obsolete entries and prevent metadata bloat.

• Dotted Version Vectors: An advanced variant (used in Riak) attaches each increment to a specific client ID or node ID and a unique dot (e.g., (Actor, Counter)). This allows for more precise garbage collection of old causal history once it is known to be reflected in all relevant replicas.
• Without pruning, vectors consume increasing memory and make comparison operations slower.

When replicas synchronize, they exchange data items along with their version vectors. The receiving replica uses the vector to decide how to integrate the update.

• Newer Version: If the incoming vector is strictly greater, the incoming data replaces the local copy.
• Concurrent Version: If vectors are concurrent, a merge is required. The system may:
  1. Call a Conflict-Free Replicated Data Type (CRDT) merge function.
  2. Invoke application-specific logic.
  3. Store both values and present them for manual resolution.
• The merged result receives a new version vector that is the element-wise maximum of the two input vectors.

Understanding version vectors requires distinguishing them from related concepts:

• vs. Timestamps: Wall-clock timestamps are prone to clock skew and cannot reliably detect causality. Version vectors provide logical causality.
• vs. Sequence Numbers: A single global sequence number cannot distinguish between concurrent updates from different nodes. Version vectors track per-node sequences.
• vs. Gossip Protocols: Gossip is a dissemination mechanism. Version vectors are a metadata structure often carried within gossip messages to track state.
• vs. Distributed Transactions: Version vectors are used in eventually consistent models. Strong consistency models (e.g., using Paxos or Raft) typically use a single, totally-ordered log and do not need version vectors for conflict detection.

A consistency model that guarantees causally related operations are seen by all processes in the same order, while allowing concurrent operations to be seen in different orders. It is stronger than eventual consistency but weaker than strong consistency.

• Key Mechanism: Uses vector clocks or version vectors to track causality.
• Use Case: Ideal for collaborative applications (like Google Docs) where user edits must be ordered correctly, but global serialization is too costly.
• Contrast with: Strong Consistency requires a single, total order; Eventual Consistency provides no ordering guarantees.

A data structure designed for distributed systems that can be updated concurrently by multiple agents without coordination, and whose state can always be merged deterministically. CRDTs guarantee strong eventual consistency.

• Two Main Types: Operation-based (CmRDT) requires reliable broadcast; State-based (CvRDT) merges states via a commutative, associative, and idempotent join function.
• Examples: Counters (G-Counter, PN-Counter), Registers (LWW-Register), Sets (G-Set, 2P-Set, OR-Set).
• Relation to Version Vectors: Often use vector-like structures (like dot clocks) to track the origin of operations for merging.

A logical timestamping mechanism used to track causality between events in a distributed system. Each node maintains a vector of counters, one for every node in the system.

• How it works: On an event, a node increments its own counter in the vector. Vectors are attached to messages. Receivers merge vectors by taking the element-wise maximum.
• Causality Check: Event A causally precedes B if every element in A's vector is ≤ the corresponding element in B's vector, and at least one is strictly less.
• Difference from Version Vector: Vector Clocks track partial order of events. Version Vectors (often a specialization) track the history of data replicas.

A consistency model guarantee that if no new updates are made to a data item, all reads to that item will eventually return the last updated value. It does not guarantee immediate synchronization or ordering.

• Trade-off: Prioritizes high availability and low latency over strict consistency, as formalized by the CAP theorem.
• Mechanism: Updates are asynchronously propagated using anti-entropy protocols like gossip.
• Challenge: Requires conflict resolution strategies (like last-write-wins or application-specific merge) to handle concurrent updates. Version vectors help identify which updates are concurrent.

A replication strategy where multiple nodes (leaders) can independently accept write operations. This improves write availability and reduces latency but introduces the complexity of handling write-write conflicts.

• Architecture: Each leader has a follower set. Leaders asynchronously replicate changes to each other.
• Conflict Detection: Version vectors are a primary tool for detecting concurrent, conflicting writes across different leaders.
• Conflict Resolution: Can be automatic (using predefined rules, LWW) or require application logic. Systems like Apache Cassandra and CouchDB use this model.

The property of a distributed system to reach consensus and function correctly even when some components fail or behave arbitrarily (maliciously). This is a stricter requirement than crash-fault tolerance.

• Context for Memory: In a BFT system, memory state replication must tolerate Byzantine replicas that may send incorrect or conflicting version vectors.
• Algorithms: Practical BFT (pBFT) and newer protocols like Tendermint or HotStuff are used in blockchain and critical systems.
• Relation: While version vectors manage causality in benign environments, BFT protocols ensure the integrity of the consensus on state despite malicious actors.