VectorClock

VectorClock: causal ordering for distributed actors.

A vector clock is a map from actor-id (String) to logical timestamp (Int). Each actor increments only its own slot. Comparing two clocks determines causal order: one event "happened before" another when every slot in the first clock is <= the corresponding slot in the second and at least one is <.

Clocks are immutable values; every update returns a new clock.

Types

typeVectorClockVectorClock = VectorClock(Map(String, Int))#

Map from actor IDs to logical timestamps.

typeClockOrderClockOrder = Before | After | Concurrent | Equal#

Causal ordering relationship between two vector clocks.

Functions

fnadvanceadvance(vc : VectorClock, actor_id : String, ts : Int) : VectorClock#

Raise actor_id's slot to ts when ts is greater than its current value; otherwise return the clock unchanged (it never lowers a slot). Advancing an absent slot to 0 or less leaves it absent.

Examples

march> VectorClock.entries(VectorClock.advance(VectorClock.new(), "a", 5))
[("a", 5)]
march> VectorClock.entries(VectorClock.advance(VectorClock.new(), "a", 0))
[]

fncomparecompare(a : VectorClock, b : VectorClock) : ClockOrder#

The causal relationship of a to b, treating missing slots as 0: Before when every slot of a is <= the one in b and at least one is smaller, After for the mirror case, Equal when all slots agree, and Concurrent when each clock is ahead of the other in some slot. O(n * m) in the number of slots (the key union is built with a list scan).

Examples

march> VectorClock.compare(VectorClock.new(), VectorClock.new())
Equal

With clocks that have real slots:

let a = VectorClock.increment(VectorClock.new(), "a")
let b = VectorClock.increment(VectorClock.new(), "b")
VectorClock.compare(VectorClock.new(), a)        -- Before
VectorClock.compare(a, VectorClock.new())        -- After
VectorClock.compare(a, b)                        -- Concurrent

fnconcurrentconcurrent(a : VectorClock, b : VectorClock) : Bool#

True when the clocks are concurrent: each is ahead of the other in at least one slot (compare(a, b) == Concurrent). Equal clocks are not concurrent.

Examples

march> VectorClock.concurrent(VectorClock.new(), VectorClock.new())
false

let a = VectorClock.increment(VectorClock.new(), "a")
let b = VectorClock.increment(VectorClock.new(), "b")
VectorClock.concurrent(a, b)   -- true

fnentriesentries(vc : VectorClock) : List((String, Int))#

All (actor_id, timestamp) pairs, in the underlying map's hash-traversal order (not sorted, and not guaranteed stable across platforms).

Examples

march> VectorClock.entries(VectorClock.increment(VectorClock.new(), "a"))
[("a", 1)]

fngetget(vc : VectorClock, actor_id : String) : Int#

The logical timestamp recorded for actor_id, or 0 when the clock has no slot for it.

Examples

march> VectorClock.get(VectorClock.new(), "node-a")
0

After two increments of the same slot:

VectorClock.get(VectorClock.increment(VectorClock.increment(VectorClock.new(), "a"), "a"), "a")
-- 2

fnhappens_beforehappens_before(a : VectorClock, b : VectorClock) : Bool#

True when a causally precedes b, i.e. compare(a, b) == Before. Equal clocks do not happen before each other.

Examples

march> VectorClock.happens_before(VectorClock.new(), VectorClock.new())
false

VectorClock.happens_before(VectorClock.new(), VectorClock.increment(VectorClock.new(), "a"))
-- true

fnincrementincrement(vc : VectorClock, actor_id : String) : VectorClock#

Increment actor_id's slot by 1 (creating it at 1 when absent) and return the updated clock. An actor should only ever increment its own slot.

Examples

march> VectorClock.entries(VectorClock.increment(VectorClock.new(), "a"))
[("a", 1)]

fnmergemerge(a : VectorClock, b : VectorClock) : VectorClock#

Component-wise maximum of two clocks: the result has every slot present in either clock, holding the higher of the two timestamps. Commutative, associative and idempotent, so replicas can merge in any order.

Examples

march> VectorClock.sum(VectorClock.merge(VectorClock.advance(VectorClock.new(), "a", 3), VectorClock.advance(VectorClock.new(), "b", 4)))
7

A slot both clocks know takes the larger value:

let x = VectorClock.advance(VectorClock.new(), "a", 3)
let y = VectorClock.advance(VectorClock.new(), "a", 5)
VectorClock.get(VectorClock.merge(x, y), "a")   -- 5

fnnewnew() : VectorClock#

An empty vector clock: every actor's timestamp is implicitly 0.

Examples

march> VectorClock.entries(VectorClock.new())
[]
march> VectorClock.get(VectorClock.new(), "a")
0

fnsumsum(vc : VectorClock) : Int#

Sum of all timestamps. It never decreases under increment, advance or merge, so it is usable as a monotone scalar summary of the clock.

Examples

march> VectorClock.sum(VectorClock.new())
0
march> VectorClock.sum(VectorClock.merge(VectorClock.increment(VectorClock.new(), "a"), VectorClock.increment(VectorClock.new(), "b")))
2