Distributed Foundations: Time & Ordering

This module is the "incident timeline" toolkit for distributed systems. When production breaks, you usually have partial logs from many nodes, delayed messages, and no trustworthy global clock. The job is to reconstruct what could have happened and what could not.

You will solve six problems that progressively build that skill:

• lamport-clock
• vector-clock-compare
• hlc-timestamps
• causal-delivery-check
• causal-broadcast-delivery
• consistent-cut-check

Learning goals

• Implement logical time updates exactly, including branch-heavy HLC receives.
• Distinguish happened-before from concurrency with vector clocks.
• Gate and drain causal message buffers deterministically.
• Validate distributed snapshots (cuts) against causal dependencies.
• Build a debugging playbook for common off-by-one and tie-break bugs.

System model and conventions

• Process indices are zero-based.
• Vectors represent observed event counts per process.
• Missing vector entries are treated as 0 where the problem states so.
• Causal delivery uses sender-specific strictness (== +1) and non-sender dependency checks (<=).
• Determinism matters: when multiple outputs are legal in theory, these problems define one canonical result.

Golden invariants for this module

1. Local progress is monotonic. No update may reduce local logical state.
2. Receive must absorb remote context. Otherwise you can violate causality.
3. Sender order is strict. For causal delivery, sender component must be exactly next.
4. Dependencies are non-strict. Non-sender components require "already seen" (<=), not "exactly equal".
5. Tie-breaking is part of correctness. For buffered delivery, lowest index first is mandatory.
6. Snapshot consistency is global. You must check all process-to-process dependencies, not just local diagonals.

1) Lamport clocks (lamport-clock)

Contract

A single node starts with clock = 0.

• local / send: clock = clock + 1
• recv(msgTs): clock = max(clock, msgTs) + 1

Return the clock value after each event.

Why this update is necessary

If receive did not take max(clock, msgTs), the node could produce a timestamp lower than one of its causal predecessors.

If receive took max but forgot +1, local time could stall on repeated receives with the same remote timestamp.

Near-solution implementation

func LamportTimestamps(events []Event) []int {
    out := make([]int, 0, len(events))
    clock := 0

    for _, ev := range events {
        switch ev.Kind {
        case EventRecv:
            if ev.MsgTimestamp > clock {
                clock = ev.MsgTimestamp
            }
            clock++
        case EventLocal, EventSend:
            clock++
        default:
            // Tests treat unknown kinds as local progress.
            clock++
        }
        out = append(out, clock)
    }
    return out
}

Worked trace

Input events:

1. local
2. send
3. recv(5)
4. local

Clock:

1. 1
2. 2
3. max(2,5)+1 = 6
4. 7

Output: [1,2,6,7]

Counterexample that catches bugs

Suppose local clock=3, receive msgTs=10.

• Wrong: clock = clock+1 = 4 (causality broken)
• Correct: clock = max(3,10)+1 = 11

Complexity

• Time: O(n)
• Space: O(n) output only

2) Vector clocks and concurrency (vector-clock-compare)

Lamport detects one direction of causality, but cannot prove concurrency. Vector clocks can.

Classification rules

For vectors a, b:

• equal: all entries equal
• before: all a[i] <= b[i] and at least one strict <
• after: all a[i] >= b[i] and at least one strict >
• concurrent: neither dominates

Pack rule: if lengths differ, missing entries are 0.

Reliable implementation pattern

Track two dominance flags across aligned entries:

• aLEb starts true, clear it on any a[i] > b[i]
• aGEb starts true, clear it on any a[i] < b[i]

Result mapping:

• aLEb && aGEb -> equal
• aLEb only -> before
• aGEb only -> after
• neither -> concurrent

Near-solution implementation

func CompareVectorClocks(a, b []int) string {
    n := len(a)
    if len(b) > n {
        n = len(b)
    }

    aLEb, aGEb := true, true
    for i := 0; i < n; i++ {
        ai, bi := 0, 0
        if i < len(a) {
            ai = a[i]
        }
        if i < len(b) {
            bi = b[i]
        }

        if ai > bi {
            aLEb = false
        }
        if ai < bi {
            aGEb = false
        }
    }

    if aLEb && aGEb {
        return OrderEqual
    }
    if aLEb {
        return OrderBefore
    }
    if aGEb {
        return OrderAfter
    }
    return OrderConcurrent
}

Examples

• a=[1,2,3], b=[1,3,3] -> before
• a=[2,1], b=[1,2] -> concurrent
• a=[1,0], b=[1,0,1] -> before (because a[2]=0 < 1)

Debug rule

If your code uses sums, mins/maxes, or lexicographic compare, it is almost certainly wrong for concurrency.

3) Hybrid Logical Clocks (hlc-timestamps)

HLC combines physical proximity with causal ordering.

Timestamp is (H, L):

• H: physical component
• L: logical tie-break counter

Local/send update

Given Now and local (H, L):

• if Now > H: (H, L) = (Now, 0)
• else: (H, L) = (H, L+1)

Receive update branch matrix

Compute H' = max(H, Hr, Now) first, then choose L by source of H':

Finally set H = H'.

Near-solution implementation skeleton

func HLCUpdates(start HLC, events []Event) []HLC {
    cur := start
    out := make([]HLC, 0, len(events))

    for _, ev := range events {
        if ev.Kind == "recv" {
            hp := cur.H
            if ev.RemoteH > hp {
                hp = ev.RemoteH
            }
            if ev.Now > hp {
                hp = ev.Now
            }

            switch {
            case hp == cur.H && hp == ev.RemoteH:
                if ev.RemoteL > cur.L {
                    cur.L = ev.RemoteL + 1
                } else {
                    cur.L = cur.L + 1
                }
            case hp == cur.H:
                cur.L = cur.L + 1
            case hp == ev.RemoteH:
                cur.L = ev.RemoteL + 1
            default: // hp == ev.Now
                cur.L = 0
            }
            cur.H = hp
        } else {
            if ev.Now > cur.H {
                cur.H = ev.Now
                cur.L = 0
            } else {
                cur.L++
            }
        }

        out = append(out, cur)
    }

    return out
}

Branch-heavy examples

1. Start (10,0), local at Now=10 -> (10,1)
2. From (10,1), recv with Now=12, remote (11,3):
   • H'=12 (Now wins) -> (12,0)
3. From (20,4), recv with Now=19, remote (20,7):
   • H'=20 (local+remote tie) -> L=max(4,7)+1=8 -> (20,8)

Common failure patterns

• Forgetting Now in the max.
• Collapsing receive logic into one formula and losing tie behavior.
• Resetting L=0 on every physical change, including wrong branches.

4) Causal delivery gate (causal-delivery-check)

Message msg from sender s is deliverable against local vector local iff:

1. msg[s] == local[s] + 1
2. For all i != s, msg[i] <= local[i]

Intuition

• Sender rule (== +1): you cannot skip sender sequence numbers.
• Dependency rule (<=): every causal predecessor from other nodes must already be observed.

Near-solution implementation

func IsCausallyDeliverable(local []int, msg []int, sender int) bool {
    if msg[sender] != local[sender]+1 {
        return false
    }
    for i := 0; i < len(local); i++ {
        if i == sender {
            continue
        }
        if msg[i] > local[i] {
            return false
        }
    }
    return true
}

Quick checks

• local=[2,0,1], msg=[2,1,1], sender=1 -> deliverable
• local=[2,0,1], msg=[2,2,1], sender=1 -> not deliverable (sender gap)
• local=[1,1,0], msg=[2,2,0], sender=0 -> not deliverable (missing dep at index 1)

Debug mantra

Sender component must be exactly next. Everyone else must be at most local.

5) Buffered causal broadcast (causal-broadcast-delivery)

Now apply the gate repeatedly to a whole buffer.

Required behavior

• Messages arrive out of order.
• Repeatedly deliver any currently deliverable message.
• If several are deliverable, pick lowest original input index.
• After delivery, merge clock element-wise max.
• Stop when a full pass yields no deliveries.
• Return delivered input indices in order.

Deterministic algorithm (fits constraints)

Given m <= 2000, n <= 50, simple repeated scans are ideal:

1. Keep done[m] bool array.
2. Scan indices 0..m-1 for first deliverable undelivered message.
3. Deliver it, update local vector, append its index to answer.
4. Restart scan from 0.
5. If no progress in a pass, finish.

Near-solution implementation skeleton

func CausalDeliverOrder(local []int, msgs []Message) []int {
    out := make([]int, 0, len(msgs))
    done := make([]bool, len(msgs))

    for {
        progressed := false

        for i, m := range msgs {
            if done[i] {
                continue
            }
            if !IsCausallyDeliverable(local, m.Clock, m.Sender) {
                continue
            }

            done[i] = true
            out = append(out, i)
            for j := 0; j < len(local); j++ {
                if m.Clock[j] > local[j] {
                    local[j] = m.Clock[j]
                }
            }

            progressed = true
            break // restart to enforce lowest-index tie-break under new local state
        }

        if !progressed {
            return out
        }
    }
}

Worked buffer trace

Initial local=[0,0,0]

Messages:

• 0: sender=2, clock=[0,0,1]
• 1: sender=1, clock=[0,1,1]
• 2: sender=0, clock=[1,1,1]

Passes:

• Pass A: deliver 0 -> local [0,0,1]
• Pass B: deliver 1 -> local [0,1,1]
• Pass C: deliver 2 -> local [1,1,1]

Output: [0,1,2]

Common mistakes

• Delivering all currently deliverable messages in same pass without deterministic restart.
• Updating only local[sender] rather than full element-wise max.
• Returning buffered but undeliverable indices.

6) Consistent cuts (consistent-cut-check)

A global cut is consistent if it never includes an event while excluding one of its causal predecessors.

Input:

• cuts[i]: count of included events on process i
• clocks[i]: vector clock of process i's last included event

Condition: for all i, j, clocks[i][j] <= cuts[j] (missing clocks[i][j] treated as 0)

Why this condition is sufficient

clocks[i][j] says how many events from process j are causally required by the included event at i. If the cut includes fewer than that (cuts[j]), the cut is causally broken.

Near-solution implementation

func IsConsistentCut(cuts []int, clocks [][]int) bool {
    n := len(cuts)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            need := 0
            if i < len(clocks) && j < len(clocks[i]) {
                need = clocks[i][j]
            }
            if need > cuts[j] {
                return false
            }
        }
    }
    return true
}

Example

cuts=[1,0], clocks=[[1,1],[]] -> inconsistent because first process requires one event from process 1, but cut includes zero.

Complexity

• Time: O(n^2) where n=len(cuts)
• Space: O(1) extra

Integrated debugging playbook

If one of the six problems fails hidden tests:

1. Boundary checks first

• empty slices
• different vector lengths
• sender index handling

1. Strict vs non-strict comparisons

• sender in causal check is ==
• dependencies are <=
• vector domination requires at least one strict inequality for before/after

1. Tie-break determinism

• causal broadcast must pick lowest index when multiple are deliverable

1. State update timing

• HLC: compute H' first, then choose L branch
• causal broadcast: update local immediately after each delivery

1. Monotonicity assertions (great for local debug prints)

• Lamport clock non-decreasing and increments once per event
• HLC (H,L) lexicographically increases across local sequence
• local vector entries never decrease after deliveries

What you will build (problem map)

• Lamport Clock Ticks: per-event scalar logical time updates.
• Vector Clock Comparison: partial order classification with missing-entry semantics.
• Hybrid Logical Clock Updates: branch-precise causality + physical-time blend.
• Causal Delivery Check: one-message deliverability gate.
• Causal Broadcast Delivery Order: deterministic iterative draining of buffered messages.
• Consistent Cut Check: causal validity of distributed snapshots.

Recommended implementation order is exactly the list above. Each problem reuses invariants from the previous one.