Skip to content

Lamport Clocks

1. What is it? (2-3 lines)

A Lamport Clock (Lamport Timestamps) is a simple distributed logical clock algorithm proposed by Leslie Lamport in 1978. It assigns a single monotonically increasing integer counter to every event in a distributed system to establish a strict partial ordering of events based on causality.

2. Why does it exist?

Physical clocks (wall-clock time) drift across independent servers. In a distributed network, determining which event happened first (Happened-Before relationship \(\to\)) cannot rely on physical timestamps. Lamport Clocks provide a lightweight logical timestamp mechanism to order distributed events deterministically without physical clock synchronization.

3. Where is it used?

  • Distributed Mutual Exclusion Algorithms: Lamport's Mutual Exclusion Algorithm, Ricart-Agrawala Algorithm.
  • Distributed Database Transaction Ordering: Total order broadcast in consensus systems, event-sourcing sequencers.
  • Distributed Tracing / Logging: Establishing causal sequence across microservice log spans.

4. How does it work? (simple flow)

  1. Initial State: Each process \(P_i\) maintains a local integer counter \(C_i\), initialized to \(0\).
  2. Local Event Rule: Before a process executes an internal event or sends a message, it increments its counter: \(C_i = C_i + 1\).
  3. Send Message: Process \(P_i\) attaches its updated timestamp \(C_i\) to the message payload (\(M, C_i\)).
  4. Receive Message Rule: When process \(P_j\) receives message (\(M, C_i\)), it updates its clock to: \(C_j = \max(C_j, C_i) + 1\) before processing the message.
  5. Happened-Before Relation (\(\to\)): If event \(a\) happened before \(b\), then \(C(a) < C(b)\).

5. Advantages

  • Extremely simple: Memory footprint is a single integer per node.
  • Guarantees that causally related events obey \(a \to b \implies C(a) < C(b)\).
  • Enables deterministic total ordering by appending node IDs as tie-breakers: \((C_i, i)\).

6. Limitations

  • Cannot Detect Concurrency: If \(C(a) < C(b)\), you CANNOT infer that \(a \to b\)! Events \(a\) and \(b\) might be completely concurrent.
  • Unlike Vector Clocks, Lamport Clocks cannot distinguish between causally dependent events and independent concurrent events.

7. Common interview questions (10)

  1. What is Leslie Lamport's "Happened-Before" relationship (\(\to\))?
  2. How does a Lamport Clock update its counter upon receiving a message with a higher timestamp?
  3. What is the fundamental limitation of Lamport Clocks compared to Vector Clocks?
  4. How do you create a Total Order from Lamport Clocks using Node ID tie-breakers?
  5. Given \(C(a) = 3\) and \(C(b) = 5\), can we conclude that event \(a\) caused event \(b\)? Why or why not?
  6. How does Ricart-Agrawala's distributed mutual exclusion algorithm utilize Lamport Timestamps?
  7. How do Lamport Clocks handle physical clock drift?
  8. How are Lamport Clocks used in distributed event logging and distributed tracing?
  9. What happens to a process's Lamport Clock if it receives a message from a node with a timestamp 10,000 values ahead?
  10. Why are TrueTime atomic clocks (Spanner) preferred over Lamport Clocks in modern distributed SQL databases?

8. Common misconceptions

  • Misconception: If \(C(a) < C(b)\), then \(a\) caused \(b\). Fact: The implication works in ONLY ONE direction: \(a \to b \implies C(a) < C(b)\). \(C(a) < C(b)\) does NOT imply \(a \to b\) (they could be concurrent).
  • Misconception: Lamport Clocks require network time protocol (NTP). Fact: Lamport Clocks ignore physical time entirely; they increment strictly based on event occurrences.

10. 30-second cheat sheet

  • Formula: Send: \(C = C + 1\); Receive: \(C_{recv} = \max(C_{local}, C_{msg}) + 1\).
  • Causality Rule: \(a \to b \implies C(a) < C(b)\).
  • Critical Flaw: \(C(a) < C(b) \not\implies a \to b\) (cannot detect concurrency).
  • Tie-Breaker: Combine \((C_i, \text{NodeID}_i)\) to force a deterministic Total Order across all nodes.