BiteSizedChunks.comLearn one small thing at a time.
Course contentsShow
← Databases & SQL
Lesson 1676 of 1,95316. Distributed Data ArchitecturesFree lesson

Logical Clocks and Lamport Timestamps

Assign unique sequence numbers to events to establish total order within a distributed process.

In this lesson, you will learn how Lamport Timestamps enable us to derive a total ordering of events across distributed nodes without relying on synchronized physical clocks.

The Problem with Physical Time

In distributed systems, physical clocks are notoriously unreliable due to "clock drift." Even with protocols like NTP, you can never guarantee that two nodes see the exact same time. If Node A and Node B log events based on their local wall-clock time, you cannot reliably determine which event happened "first" if they occur in quick succession.

The Lamport Mechanism

A Lamport timestamp is a simple counter that provides a partial ordering of events based on causality. Each process maintains a local counter, C, following these two simple rules:

  1. Increment on Event: Before a process performs an event (local action, send message, or receive message), it increments its counter: C = C + 1.
  2. Synchronize on Receive: If a process receives a message with a timestamp Tm, it updates its local counter to C = max(C, Tm) + 1.

Concrete Illustration

Imagine two nodes, A and B:

  • Node A performs an event: C_a becomes 1. It sends a message to Node B with the value 1.
  • Node B receives the message. Its current counter C_b was 0. Using the rule max(0, 1) + 1, its counter becomes 2.

Because Node B’s counter is higher, we know that Node A's event "happened before" Node B's reception of that message. This establishes a causal ordering.

Achieving Total Order

To achieve a total order—where every event is uniquely identified and sortable—we augment the Lamport timestamp with the unique ID of the process (Node ID). A timestamp is defined as the tuple (Counter, NodeID). We compare these tuples lexicographically:

  • If C_a < C_b, then event A happens before B.
  • If C_a == C_b, then we compare NodeID. The node with the lower (or higher, by convention) ID "wins," ensuring a unique, deterministic sequence even if the counters match.

Key Takeaway: Lamport Timestamps transform logical causality into a total order by combining an incrementing counter with a tie-breaking unique node identifier, effectively sidestepping the limitations of physical clock drift.