How Version Vectors Resolve Conflicts in Multi‑Leader and Leaderless Replication

Why Version Vectors Are Needed

In multi‑leader or leaderless replication models, global ordering cannot be guaranteed, making Versioned Value unsuitable for conflict resolution. Version Vectors provide a way to detect concurrent updates by maintaining a vector of version counters for each node.

Version Vector Implementation Principle and Limitations

A Version Vector is essentially an array of version counters, one per node. Each node increments its counter when it processes a write. The vector is compared across nodes to detect conflicts.

vectors = [node1: 21, node2: 34, node3: 23, node4: 32]

When a node receives a write, its counter is incremented:

vectors = [node1: 22, node2: 34, node3: 23, node4: 32]

Nodes exchange their vectors to detect concurrent updates.

Version Vector Comparison Rules

A vector A is considered higher than vector B if:

Both vectors contain the same set of nodes.

Every node’s version in A is greater than the corresponding version in B.

Vectors are concurrent if either:

No vector dominates the other (some nodes higher, some lower).

The sets of nodes differ.

Pseudocode for Version Vector

public enum Ordering { Before, After, Concurrent }</code><code>public class VersionVector { private final TreeMap<String, Long> versions; public VersionVector increment(String nodeId) { TreeMap<String, Long> versions = new TreeMap<>(); versions.putAll(this.versions); Long version = versions.get(nodeId); if (version == null) { version = 1L; } else { version = version + 1L; } versions.put(nodeId, version); return new VersionVector(versions); }</code><code>public Ordering compareTo(VersionVector v2) { Set<String> v1Nodes = this.getVersions().keySet(); Set<String> v2Nodes = v2.getVersions().keySet(); Set<String> commonNodes = retainNodes(v1Nodes, v2Nodes); boolean v1Bigger = v1Nodes.size() > commonNodes.size(); boolean v2Bigger = v2Nodes.size() > commonNodes.size(); for (String nodeId : commonNodes) { if (v1Bigger && v2Bigger) { break; } long v1Version = v1.getVersions().get(nodeId); long v2Version = v2.getVersions().get(nodeId); if (v1Version > v2Version) { v1Bigger = true; } else if (v1Version < v2Version) { v2Bigger = true; } } return determineOrdering(v1Bigger, v2Bigger); }</code><code>private Ordering determineOrdering(boolean v1Bigger, boolean v2Bigger) { if (!v1Bigger && !v2Bigger) { return Ordering.Before; } else if (v1Bigger && !v2Bigger) { return Ordering.After; } else if (!v1Bigger && v2Bigger) { return Ordering.Before; } return Ordering.Concurrent; }</code><code>}

Write Flow with Version Vectors

In a multi‑leader setup, each replica increments its vector when handling a write. The coordinator selects a primary for a key, obtains the current vector, and performs a putAsPrimary operation. After the primary write succeeds, the updated vector is replicated to other replicas without further version changes.

Conflict Resolution Strategies

When a conflict is detected, several approaches can be used:

Custom Conflict Resolver : Implement an interface to resolve conflicts based on business logic.

public interface ConflictResolver { VersionedValue resolve(List<VersionedValue> values); }</code><code>public class ClusterClient { public VersionedValue getResolvedValue(String key, ConflictResolver resolver) { List<VersionedValue> versionedValues = get(key); return resolver.resolve(versionedValues); } }

Last Write Wins (LWW) : Choose the version with the highest timestamp.

public Optional<TimestampedVersionedValue> getWithLWW(List<TimestampedVersionedValue> values) { return values.stream().max(Comparator.comparingLong(v -> v.timestamp)); }

Read Repair : After resolving a conflict, push the latest version to replicas that still hold stale data.

Reject Stale Requests : Discard writes whose vector is older than the current one.

Summary

Version Vectors enable detection of concurrent updates in multi‑leader and leaderless replication, and together with custom resolvers, LWW, read‑repair, or request rejection, they provide a comprehensive toolkit for conflict management in distributed databases.