Distributed Foundations: Time & Ordering

Implementation-first module for reconstructing causality in distributed incidents.

Learning outcomes

• Implement Lamport, vector clock, and HLC updates exactly.
• Separate happened-before from concurrency.
• Gate and drain causal buffers deterministically.
• Verify global cuts against causal dependencies.

Golden invariants

1. Local logical state never decreases.
2. Receives absorb remote context.
3. Sender order is strict (== +1).
4. Non-sender dependencies are non-strict (<=).
5. Tie-breaking policy is part of correctness.

Problem 1: Lamport clock ticks

Rules:

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

Guarantee:

• A -> B implies L(A) < L(B)

Lamport pitfalls

• Ignoring remote timestamp on recv.
• Forgetting +1 after max.
• Treating send as non-event.

Problem 2: Vector clock comparison

Classify a vs b as:

• equal
• before
• after
• concurrent

Pack rule:

• missing entries are 0

Dominance trick

Track booleans while scanning:

• aLEb
• aGEb

Map booleans:

• both true -> equal
• only aLEb -> before
• only aGEb -> after
• neither -> concurrent

Problem 3: HLC updates

State (H, L):

• H: physical component
• L: logical tie-breaker

Local/send:

• Now > H -> (Now,0)
• else -> (H,L+1)

HLC receive branches

Compute H' = max(H, Hr, Now) first.

Then:

1. H'==H==Hr -> max(L,Lr)+1
2. H'==H -> L+1
3. H'==Hr -> Lr+1
4. H'==Now -> 0

Problem 4: Causal delivery check

Deliverable iff:

• msg[s] == local[s] + 1
• for all i != s: msg[i] <= local[i]

Interpretation:

• exact next sender message
• all dependencies already seen

Problem 5: Causal broadcast delivery

Messages arrive out of order.

Algorithm:

1. find first deliverable message
2. deliver lowest index among deliverables
3. merge local by element-wise max
4. restart scan
5. stop when no progress

Causal broadcast failure modes

• wrong sender comparison (>= instead of ==)
• no deterministic tie-break
• updating only sender component
• infinite loop with stuck messages

Problem 6: Consistent cut check

Cut is consistent iff for all i,j:

• clocks[i][j] <= cuts[j]
• missing entries treated as 0

Why:

• included events cannot depend on excluded predecessors

Debug order that works

1. boundary conditions
2. strict vs non-strict comparisons
3. tie-break behavior
4. update timing
5. monotonicity assertions

Build order

1. lamport-clock
2. vector-clock-compare
3. hlc-timestamps
4. causal-delivery-check
5. causal-broadcast-delivery
6. consistent-cut-check

Each step reuses invariants from earlier ones.