Distributed Foundations: Time & Ordering

Why time is hard

In a distributed system there is no single, perfect clock. Messages are delayed, reordered, or lost. We still need a way to reason about order so we can build correct protocols.

Key idea: focus on causality, not wall time.

Lamport clocks (logical time)

Each node keeps an integer clock.

Rules:

• Local / Send: clock = clock + 1
• Receive: clock = max(clock, msgTimestamp) + 1

Guarantee: if event A happened-before event B, then L(A) < L(B).

What it does not tell you: whether two events are concurrent.

When Lamport is not enough

Lamport timestamps cannot detect concurrency. Two events can have different timestamps and still be concurrent.

This is why we need vector clocks and causal delivery checks.

Hybrid Logical Clocks (HLC)

HLC combines physical time with a logical counter to preserve causality while keeping timestamps close to wall time.

What you will build

• Compute Lamport timestamps for a stream of events.
• Compare vector clocks to classify ordering.
• Update a hybrid logical clock across events.
• Decide when a message is causally deliverable.
• Deliver buffered messages in causal order.
• Check whether a global cut is causally consistent.

Start with the first problem: Lamport Clock Ticks.