ConvergeLedger.Integrity.LamportClock (Converge Ledger v0.1.2)

Lamport logical clock for causal ordering of events.

Lamport clocks provide a partial ordering of events in a distributed system without requiring synchronized wall clocks. The key property is: if event A happened-before event B, then clock(A) < clock(B).

Usage

iex> clock = LamportClock.new()
iex> {clock, t1} = LamportClock.tick(clock)
iex> t1
1
iex> {clock, t2} = LamportClock.tick(clock)
iex> t2
2
iex> {clock, t3} = LamportClock.update(clock, 10)
iex> t3
11

Properties

Monotonic: Clock value never decreases
Consistent: Same input → same output
Causal: happened_before?(a, b) implies clock(a) < clock(b)

Summary

Types

t()

Functions

compare(a, b)

Compares two clock values.

happened_before?(a, b)

Returns true if clock value a is causally before b.

merge(lamport_clock1, lamport_clock2)

Merges two clocks, returning the maximum of both.

new()

Creates a new Lamport clock initialized to 0.

new(initial_time)

Creates a Lamport clock with a specific initial time.

tick(clock)

Increments the clock and returns {new_clock, new_time}.

time(lamport_clock)

Returns the current logical time.

update(clock, received_time)

Updates the clock based on a received timestamp.

Types

t()

@type t() :: %ConvergeLedger.Integrity.LamportClock{time: non_neg_integer()}

Functions

compare(a, b)

@spec compare(non_neg_integer(), non_neg_integer()) :: :lt | :gt | :eq

Compares two clock values.

Returns:

:lt if a < b (a happened before b, or b is causally later)
:gt if a > b (b happened before a, or a is causally later)
:eq if a == b (concurrent events, or same event)

happened_before?(a, b)

@spec happened_before?(non_neg_integer(), non_neg_integer()) :: boolean()

Returns true if clock value a is causally before b.

Note: a < b implies a may have happened before b, but the converse is not guaranteed (concurrent events may have any ordering).

merge(lamport_clock1, lamport_clock2)

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

Merges two clocks, returning the maximum of both.

Useful when combining state from multiple sources.

new()

@spec new() :: t()

Creates a new Lamport clock initialized to 0.

new(initial_time)

@spec new(non_neg_integer()) :: t()

Creates a Lamport clock with a specific initial time.

tick(clock)

@spec tick(t()) :: {t(), non_neg_integer()}

Increments the clock and returns {new_clock, new_time}.

Called before any local event (e.g., appending an entry).

time(lamport_clock)

@spec time(t()) :: non_neg_integer()

Returns the current logical time.

update(clock, received_time)

@spec update(t(), non_neg_integer()) :: {t(), non_neg_integer()}

Updates the clock based on a received timestamp.

Sets clock to max(local, received) + 1. Called when receiving entries from another source.

Returns {new_clock, new_time}.