lattice/version_vector

A version vector for tracking causal ordering between replicas.

Each replica has a logical clock (monotonically increasing integer). Version vectors enable detecting whether two states are causally ordered (one happened before the other) or concurrent (neither dominates). Merge takes the pairwise maximum of all clocks.

Example

import lattice/version_vector

let a = version_vector.new()
  |> version_vector.increment("node-a")
  |> version_vector.increment("node-a")
let b = version_vector.new()
  |> version_vector.increment("node-b")
version_vector.compare(a, b)  // -> Concurrent

Types

Order

</>

The causal ordering relationship between two version vectors.

Before: the first vector happened before the second (all clocks <=, at least one strictly <)
After: the first vector happened after the second (all clocks >=, at least one strictly >)
Concurrent: neither dominates — the states diverged; at least one clock is strictly greater in each direction
Equal: both vectors have identical clocks for all replicas

pub type Order {
  Before
  After
  Concurrent
  Equal
}

Constructors

```
Before
```
```
After
```
```
Concurrent
```
```
Equal
```

VersionVector

opaque </>

A version vector tracking logical clocks for each replica.

Internally holds a dictionary from replica ID to clock value. The type is opaque: use new, increment, get, compare, and merge to interact with it. Serialization helpers to_dict and from_dict are provided for JSON encoding and decoding.

pub opaque type VersionVector

Values

compare

</>

pub fn compare(a: VersionVector, b: VersionVector) -> Order

Compare two version vectors and return their causal ordering.

Returns Equal if all clocks match, Before if a is strictly dominated by b, After if a strictly dominates b, or Concurrent if neither dominates the other.

from_dict

</>

pub fn from_dict(d: dict.Dict(String, Int)) -> VersionVector

Construct a VersionVector from a raw clock dictionary.

Intended for use by deserialization code in sibling modules (e.g., mv_register). Prefer new and increment for all other use cases.

from_json

</>

pub fn from_json(
  json_string: String,
) -> Result(VersionVector, json.DecodeError)

Decode a VersionVector from a JSON string produced by to_json.

Returns Ok(VersionVector) on success, or Error(json.DecodeError) if the input is not a valid version-vector JSON envelope.

get

</>

pub fn get(vv: VersionVector, replica_id: String) -> Int

Get the clock value for a specific replica.

Returns 0 if replica_id has not been seen (missing entries default to zero, consistent with the version vector semantics).

increment

</>

pub fn increment(
  vv: VersionVector,
  replica_id: String,
) -> VersionVector

Increment the clock for a specific replica.

Returns a new version vector with replica_id’s clock increased by one. This is the standard way to record a new event at replica_id.

merge

</>

pub fn merge(a: VersionVector, b: VersionVector) -> VersionVector

Merge two version vectors using pairwise maximum.

For each replica, the merged clock is the maximum of the two inputs. This operation is commutative, associative, and idempotent.

new

</>

pub fn new() -> VersionVector

Create a new empty version vector.

All replica clocks start at zero (missing entries are treated as zero).

to_dict

</>

pub fn to_dict(vv: VersionVector) -> dict.Dict(String, Int)

Extract the internal clock dictionary from a VersionVector.

Intended for use by serialization code in sibling modules (e.g., mv_register). Prefer the higher-level API (get, compare, merge) for all other use cases.

to_json

</>

pub fn to_json(vv: VersionVector) -> json.Json

Encode a VersionVector as a self-describing JSON value.

Produces an envelope with type, v (schema version), and state. Format: {"type": "version_vector", "v": 1, "state": {"clocks": {...}}}

Use from_json to decode the result back into a VersionVector.