Grove.VectorClock (Grove v0.1.1)

View Source

Vector clock implementation for causality tracking.

A vector clock is a mechanism for tracking the causal ordering of events in a distributed system. Each replica maintains a counter, and the vector of all counters can be compared to determine if one event happened before another, or if they are concurrent.

Example

iex> vc = Grove.VectorClock.new()
iex> vc = Grove.VectorClock.increment(vc, :node_a)
iex> vc = Grove.VectorClock.increment(vc, :node_a)
iex> Grove.VectorClock.get(vc, :node_a)
2

Summary

Types

actor()
t()

Functions

actors(vc)

Returns the list of actors in the vector clock.

compare(vc1, vc2)

Compares two vector clocks.

concurrent?(vc1, vc2)

Checks if two vector clocks are concurrent (neither happened before the other).

descends?(vc1, vc2)

Checks if vc1 descends from (happened after or equal to) vc2.

dominates?(vc1, vc2)

Dominates check - returns true if vc1 dominates vc2.

get(vc, actor)

Gets the counter value for the given actor.

increment(vc, actor)

Increments the counter for the given actor.

merge(vc1, vc2)

Merges two vector clocks by taking the pointwise maximum.

new()

Creates a new empty vector clock.

strictly_descends?(vc1, vc2)

Checks if vc1 strictly descends from (happened after) vc2.

Types

actor()

@type actor() :: term()

t()

@type t() :: %{required(actor()) => non_neg_integer()}

Functions

actors(vc)

@spec actors(t()) :: [actor()]

Returns the list of actors in the vector clock.

compare(vc1, vc2)

@spec compare(t(), t()) :: :before | :after | :equal | :concurrent

Compares two vector clocks.

Returns:

  • :before if vc1 happened before vc2 (vc1 < vc2)
  • :after if vc1 happened after vc2 (vc1 > vc2)
  • :equal if vc1 equals vc2
  • :concurrent if vc1 and vc2 are concurrent (neither happened before the other)

concurrent?(vc1, vc2)

@spec concurrent?(t(), t()) :: boolean()

Checks if two vector clocks are concurrent (neither happened before the other).

descends?(vc1, vc2)

@spec descends?(t(), t()) :: boolean()

Checks if vc1 descends from (happened after or equal to) vc2.

Returns true if every counter in vc2 is less than or equal to the corresponding counter in vc1.

dominates?(vc1, vc2)

@spec dominates?(t(), t()) :: boolean()

Dominates check - returns true if vc1 dominates vc2.

vc1 dominates vc2 if all counters in vc1 are >= counters in vc2, and at least one counter is strictly greater.

get(vc, actor)

@spec get(t(), actor()) :: non_neg_integer()

Gets the counter value for the given actor.

Returns 0 if the actor is not present.

increment(vc, actor)

@spec increment(t(), actor()) :: t()

Increments the counter for the given actor.

merge(vc1, vc2)

@spec merge(t(), t()) :: t()

Merges two vector clocks by taking the pointwise maximum.

new()

@spec new() :: t()

Creates a new empty vector clock.

strictly_descends?(vc1, vc2)

@spec strictly_descends?(t(), t()) :: boolean()

Checks if vc1 strictly descends from (happened after) vc2.