Notesdistributed🌱 seedling

Lamport Clock

Also: Lamport Timestamp · Logical Clock · Logical Timestamp

One integer counter per process, incremented before each event and carried on every message; a receiver jumps to max(own, received) + 1. If a happened before b then L(a) < L(b), but not the reverse.

Why it exists

To order events consistently with causality using no synchronized time at all.

How it works

  • Rule 1: increment the counter before every event and stamp the event with it.
  • Rule 2: send the counter with each message; on receipt set counter = max(own, received) + 1.
  • Clock condition: a → b ⇒ L(a) < L(b).
  • Total order: sort by (counter, process ID). Every node computes the same order, consistent with causality.
  • Limits: L(a) < L(b) is compatible with a ∥ b, so it can't detect concurrency. And the total order is only known after collecting timestamps from everyone, which is too late for decisions like "who claimed this username first".

Trade-offs

Gains Costs
tiny: one integer per message can't tell causal order from concurrency
no clock synchronization numbers unrelated to wall time; can't query "as of 10:00"
total order for free that order is only final after hearing from every node

In practice

  • The original use (1978) was a distributed mutual-exclusion algorithm: every process orders lock requests by timestamp.
  • Raft terms and Kafka epochs are Lamport-style counters: monotonic numbers that let nodes recognize stale messages.

Pitfalls

  • Reading L(a) < L(b) as "a caused b".
  • Using it where real-time order matters (two users with no shared channel); see TrueTime.

Recall

These cards are also in your review deck, scheduled with spaced repetition.