Grove.DottedVersionVector (Grove v0.1.1)
View SourceA Dotted Version Vector (DVV) for precise causality tracking.
DVVs combine a "dot" (a single event identifier) with a version vector (causal context). This provides more precise causality tracking than plain vector clocks, especially for OR-Set semantics.
Structure
- dot:
{actor, counter}- identifies a single event - context:
%{actor => counter}- what events have been observed
Key Operations
event/2- Record a new event, creating a dotsync/2- Merge contexts when receiving remote statedescends?/2- Check if one DVV causally follows anotherdominates?/2- Check strict causal dominance
Example
iex> dvv = Grove.DottedVersionVector.new()
iex> {dvv, dot} = Grove.DottedVersionVector.event(dvv, :node_a)
iex> dot
{:node_a, 1}References
Based on Riak's implementation and the Shapiro et al. papers on CRDTs.
Summary
Functions
Adds a dot to the context without making it the current dot.
Compares two DVVs for causal ordering.
Checks if a dot is included in the DVV's context.
Returns the context as a map.
Checks if dvv1 descends from (causally follows or equals) dvv2.
Checks if dvv1 strictly dominates dvv2.
Returns the current dot, if any.
Records a new event for the given actor.
Merges two DVVs, taking the maximum context and keeping the more recent dot.
Creates a new empty DVV.
Syncs two DVVs by merging their contexts.
Types
Functions
Adds a dot to the context without making it the current dot.
Used when observing a remote event.
Compares two DVVs for causal ordering.
Returns:
:beforeif dvv1 happened before dvv2:afterif dvv1 happened after dvv2:equalif they are identical:concurrentif they are causally independent
Checks if a dot is included in the DVV's context.
Returns the context as a map.
Checks if dvv1 descends from (causally follows or equals) dvv2.
Returns true if dvv1's context includes all events in dvv2's context.
Checks if dvv1 strictly dominates dvv2.
Returns true if dvv1 descends from dvv2 AND dvv1 has additional events.
Returns the current dot, if any.
Records a new event for the given actor.
Returns the updated DVV and the new dot. The dot is added to the context, and becomes the current dot.
Merges two DVVs, taking the maximum context and keeping the more recent dot.
@spec new() :: t()
Creates a new empty DVV.
Syncs two DVVs by merging their contexts.
Takes the pointwise maximum of all counters. The dot from the first DVV is preserved.