Lamport Clock | Concepts

TL;DR

Lamport clocks are logical timestamps that order events in distributed systems without relying on synchronized physical clocks. Each process maintains an integer counter, incremented on every event. Messages carry their send timestamp; receivers advance their clock to max(local, received) + 1. This ensures causally related events are properly ordered—if A causes B, clock(A) < clock(B).

Visual Overview

Lamport Clock

Core Explanation

What is a Lamport Clock?

Real-World Analogy: Imagine you’re at a party where people are passing notes. Each person has a notepad where they write down a number for each action they take (read a note, write a note, say something). When you pass a note, you write your current number on it.

When someone receives your note, they look at the number on it. If their notepad number is lower, they update it to be higher than the note’s number. This way, anyone can look at the numbers and know: “This action happened in response to that action” based on the numbers alone—no wall clock needed.

Why Not Physical Clocks?

Physical Clock Problem

The Happens-Before Relation

Happens-Before Relation

The Algorithm Visualized

Lamport Clock Example

The Algorithm

# Lamport Clock Rules

# Rule 1: Local event
def local_event():
    clock += 1

# Rule 2: Send message
def send_message(message, destination):
    clock += 1
    message.timestamp = clock
    transmit(message, destination)

# Rule 3: Receive message
def receive_message(message):
    clock = max(clock, message.timestamp) + 1
    process(message)

Key Properties

Property	Value	Notes
Space Complexity	O(1) per process	Single integer counter
Time Complexity	O(1) per event	Simple arithmetic
Causality	If A → B then L(A) < L(B)	Guaranteed
Concurrency Detection	No	Cannot distinguish concurrent events

The Limitation: Can’t Detect Concurrency

Lamport Clock Limitation

Real Systems Using Lamport Clocks

System	Use Case	Notes
Total Order Broadcast	Ordering messages	Tie-breaking with process ID
Distributed Debugging	Log correlation	Sort logs by logical time
Mutual Exclusion	Lock ordering	Lamport’s original paper use case
Distributed Transactions	Serialization	Order operations across nodes
Simple Event Logs	Causal ordering	When concurrency detection not needed

Note: Many production systems upgrade to vector clocks when concurrency detection is required.

Lamport Clocks vs Vector Clocks

Lamport vs Vector Clocks

When to Use Lamport Clocks

✓ Perfect Use Cases

Lamport Clock Use Cases

✕ When NOT to Use

When Lamport Clocks May Not Fit

Interview Application

Common Interview Question

Q: “Explain Lamport clocks. What problem do they solve and what are their limitations?”

Strong Answer:

“Lamport clocks solve the event ordering problem in distributed systems without requiring synchronized physical clocks.

The Problem: Physical clocks on different machines drift. Even with NTP, they can differ by milliseconds—enough to mis-order events. If Machine A’s clock says 10:00:01 and Machine B’s says 10:00:02, which event actually happened first?

The Solution: Instead of measuring real time, Lamport clocks capture causality—the happens-before relationship:

Three rules:

Local event: counter++

Send message: counter++, attach timestamp

Receive message: counter = max(local, received) + 1

The Guarantee: If event A causally precedes event B (A → B), then clock(A) < clock(B).

The Limitation: The converse is NOT guaranteed. If clock(A) < clock(B), it could mean:

A → B (A caused B), OR

A ∥ B (A and B are concurrent, neither caused the other)

Lamport clocks cannot distinguish these cases.

When to use:

Total order broadcast (tie-break with node ID)

Distributed logging/debugging

Simple causality checks

When to use Vector Clocks instead:

Conflict detection

Optimistic replication

CRDTs”

Follow-up: Walk me through an example execution.

“Let’s trace through three processes:
Initial state: A=0, B=0, C=0

1. A does local event: A=1
2. A sends message to B (ts=1)
3. B receives message: B = max(0, 1) + 1 = 2
4. B does local event: B=3
5. B sends message to C (ts=3)
6. C receives message: C = max(0, 3) + 1 = 4
7. A sends message to C (ts=1) [this was sent earlier]
8. C receives message: C = max(4, 1) + 1 = 5
Notice in step 8: C’s clock was already at 4 from receiving B’s message. Even though A’s message had timestamp 1, C advances to 5, not 2. This ensures C’s clock reflects that it has seen both A’s and B’s messages.”

Follow-up: How would you handle tie-breaking when timestamps are equal?

“When two events have the same Lamport timestamp, they’re either concurrent or from the same process. For total ordering, we break ties using process ID (or node ID):
total_order(event1, event2):
  if event1.timestamp != event2.timestamp:
    return event1.timestamp < event2.timestamp
  else:
    return event1.process_id < event2.process_id
This gives a deterministic total order. All nodes that see both events will order them consistently.

Important: This tie-breaking is arbitrary—it doesn’t reflect actual causality. If two events have the same timestamp and different process IDs, they might be concurrent, and we’re just picking an arbitrary order for consistency.”

Code Example

Lamport Clock Implementation (Python)

from dataclasses import dataclass, field
from typing import Optional
import threading

@dataclass
class Message:
    """A message carrying Lamport timestamp."""
    content: str
    timestamp: int
    sender: str

class LamportClock:
    """
    Lamport logical clock implementation.

    Thread-safe for concurrent events.
    """

    def __init__(self, process_id: str):
        self.process_id = process_id
        self._counter = 0
        self._lock = threading.Lock()

    @property
    def time(self) -> int:
        """Current logical time."""
        with self._lock:
            return self._counter

    def local_event(self, description: str = "") -> int:
        """
        Record a local event.

        Returns the timestamp of the event.
        """
        with self._lock:
            self._counter += 1
            timestamp = self._counter

        if description:
            print(f"[{self.process_id}] t={timestamp}: {description}")

        return timestamp

    def send(self, content: str, destination: str) -> Message:
        """
        Create a message to send.

        Increments clock and returns message with timestamp.
        """
        with self._lock:
            self._counter += 1
            timestamp = self._counter

        print(f"[{self.process_id}] t={timestamp}: send to {destination}")

        return Message(
            content=content,
            timestamp=timestamp,
            sender=self.process_id
        )

    def receive(self, message: Message) -> int:
        """
        Process a received message.

        Updates clock to max(local, received) + 1.
        Returns the new timestamp.
        """
        with self._lock:
            self._counter = max(self._counter, message.timestamp) + 1
            timestamp = self._counter

        print(f"[{self.process_id}] t={timestamp}: recv from {message.sender} "
              f"(msg_ts={message.timestamp})")

        return timestamp

    def compare(self, other_timestamp: int) -> str:
        """
        Compare local time with another timestamp.

        Note: This only tells us about potential causality,
        not actual causality.
        """
        with self._lock:
            local = self._counter

        if local < other_timestamp:
            return "local happened before (or concurrent)"
        elif local > other_timestamp:
            return "local happened after (or concurrent)"
        else:
            return "same timestamp (concurrent or same event)"


# Usage example
if __name__ == "__main__":
    print("=== Lamport Clock Demo ===\n")

    # Create three processes
    alice = LamportClock("Alice")
    bob = LamportClock("Bob")
    charlie = LamportClock("Charlie")

    # Scenario: Alice sends to Bob, Bob processes and sends to Charlie

    # Alice does some work
    alice.local_event("start processing")
    alice.local_event("compute result")

    # Alice sends to Bob
    msg1 = alice.send("Hello Bob", "Bob")

    # Bob receives (his clock jumps)
    bob.receive(msg1)

    # Bob does local work
    bob.local_event("process Alice's message")

    # Bob sends to Charlie
    msg2 = bob.send("Hello Charlie", "Charlie")

    # Charlie receives
    charlie.receive(msg2)

    # Meanwhile, Alice sends directly to Charlie
    msg3 = alice.send("Direct to Charlie", "Charlie")

    # Charlie receives Alice's message (clock already advanced)
    charlie.receive(msg3)

    print("\n=== Final Clock Values ===")
    print(f"Alice: {alice.time}")
    print(f"Bob: {bob.time}")
    print(f"Charlie: {charlie.time}")

Total Order Broadcast with Lamport Clocks

from dataclasses import dataclass
from typing import List
import heapq

@dataclass(order=True)
class OrderedEvent:
    """Event that can be totally ordered."""
    timestamp: int
    process_id: str  # Tie-breaker
    content: str = field(compare=False)

class TotalOrderBroadcast:
    """
    Total order broadcast using Lamport clocks.

    All processes see events in the same order.
    """

    def __init__(self, process_id: str):
        self.clock = LamportClock(process_id)
        self.process_id = process_id
        self.pending: List[OrderedEvent] = []  # Min-heap
        self.delivered: List[OrderedEvent] = []

    def broadcast(self, content: str) -> OrderedEvent:
        """Broadcast an event to all processes."""
        timestamp = self.clock.local_event(f"broadcast: {content}")
        event = OrderedEvent(
            timestamp=timestamp,
            process_id=self.process_id,
            content=content
        )
        self._add_to_pending(event)
        return event

    def receive(self, event: OrderedEvent) -> None:
        """Receive a broadcast event from another process."""
        # Update clock based on received timestamp
        fake_message = Message(
            content=event.content,
            timestamp=event.timestamp,
            sender=event.process_id
        )
        self.clock.receive(fake_message)
        self._add_to_pending(event)

    def _add_to_pending(self, event: OrderedEvent) -> None:
        """Add event to pending queue."""
        heapq.heappush(self.pending, event)

    def deliver_ready(self) -> List[OrderedEvent]:
        """
        Deliver events that are ready.

        In a real system, you'd wait for acknowledgments from all
        processes before delivering. This simplified version just
        delivers in order.
        """
        delivered = []
        while self.pending:
            event = heapq.heappop(self.pending)
            self.delivered.append(event)
            delivered.append(event)
            print(f"[{self.process_id}] DELIVER: ({event.timestamp}, "
                  f"{event.process_id}) {event.content}")
        return delivered


# Demo
if __name__ == "__main__":
    print("\n=== Total Order Broadcast Demo ===\n")

    # Two processes
    p1 = TotalOrderBroadcast("P1")
    p2 = TotalOrderBroadcast("P2")

    # P1 broadcasts
    e1 = p1.broadcast("Event from P1")

    # P2 broadcasts (concurrent with P1)
    e2 = p2.broadcast("Event from P2")

    # Both receive each other's events
    p1.receive(e2)
    p2.receive(e1)

    # Both deliver in same order
    print("P1 delivers:")
    p1.deliver_ready()

    print("\nP2 delivers:")
    p2.deliver_ready()

    # Both see: (1, P1) then (1, P2) - tie broken by process ID

See It In Action:

Lamport Clock Explainer - Visual walkthrough with message passing

Related Concepts:

Logical Clocks - The broader concept
Eventual Consistency - Uses logical ordering

Quick Self-Check

Can explain the three Lamport clock rules in 30 seconds?
Understand why physical clocks are unreliable for ordering?
Know the key guarantee: A → B implies clock(A) < clock(B)?
Understand the limitation: clock(A) < clock(B) does NOT imply A → B?
Know when to use Lamport clocks vs vector clocks?
Can implement the receive rule: max(local, received) + 1?