30-Second Glance
- Lamport clocks are logical (not wall-clock) timestamps that capture causal order across processes.
- Each process keeps a local counter: +1 on internal events and sends; on receive, take max(local, received) then +1.
- They guarantee the happens-before rule: if A causally precedes B, timestamp(A) < timestamp(B).
- They give only a partial order — equal or unordered timestamps mean "concurrent," not "simultaneous."
- The note's companion ordering ladder: single-leader logs for total order, version vectors/Lamport for causal order.
Introduction
Lamport clocks are a mechanism used in distributed systems to assign a logical timestamp to events in order to capture the order of events across different processes or nodes. Unlike physical clocks, which represent actual time, Lamport clocks are logical clocks that help establish a causal relationship between events.
Key Concepts:
- Logical Clocks: • Lamport clocks assign a numerical value (timestamp) to each event in a distributed system. • These timestamps are used to determine the order of events, rather than their actual physical time of occurrence.
- Partial Ordering: • The main purpose of Lamport clocks is to provide a partial order of events across distributed processes. • If one event causally influences another, Lamport clocks can determine this relationship.
- How Lamport Clocks Work: • Each process in the system maintains its own local counter. • When a process performs an event (e.g., sending a message, performing a computation), it increments its counter. • When a process sends a message, it includes its current counter value (timestamp) with the message. • When a process receives a message, it updates its counter to be the maximum of its current value and the received timestamp, and then increments it.
- Rules for Timestamps: • Internal Events: For any internal event within a process, the Lamport clock is incremented by 1. • Sending a Message: When a process sends a message, it increments its clock by 1 and assigns this value to the message’s timestamp. • Receiving a Message: When a process receives a message, it sets its clock to the maximum of its current clock and the received message’s timestamp, then increments by 1.
- Happens-Before Relationship (→): • Lamport clocks help establish the “happens-before” (→) relationship between events: • If event A happens before event B in the same process, then the timestamp of A is less than the timestamp of B. • If event A sends a message to event B, then the timestamp of A is less than the timestamp of B.
- Limitations: • Lamport clocks can determine the order of events, but they do not capture concurrency. • If two events have the same timestamp (in different processes), Lamport clocks cannot determine which event happened first; they are considered concurrent.
Trade-offs
| Approach | Pros | Cons | Use when |
|---|---|---|---|
| Lamport clock (single counter) | Tiny state; cheap causal ordering | Can't detect concurrency vs causality (a < b doesn't prove a caused b) | Ordering events where causality direction suffices |
| Version vector (per-node counters) | Distinguishes causal from concurrent | O(N) state per value; heavier to store and compare | Conflict detection in multi-leader/leaderless stores |
| Wall-clock timestamps (LWW) | Trivial to compare | Clock skew silently reorders or drops writes | Caches where occasional loss is fine |
| Central sequencer / single-leader log | True total order | Bottleneck and single point of failure | Logs needing one canonical order |
Interview One-Liners
Q: What is a Lamport clock? A: A per-process logical counter attached to events to capture causal order, not physical time.
Q: State the three update rules. A: Internal event: counter +1; send: +1 and stamp the message; receive: counter = max(local, received) + 1.
Q: What guarantee do they give? A: Happens-before: if A causally precedes B (same process order or message chain), then ts(A) < ts(B).
Q: What is their headline limitation? A: They capture only a partial order — they cannot tell whether two unordered events are concurrent; equal timestamps across processes prove nothing about order.
Q: Lamport vs version vector in one line? A: Lamport is one cheap counter for causal direction; version vectors keep per-node counters so they can also prove concurrency.