Lamport timestamp

Definition
A Lamport timestamp is a scalar logical clock value assigned to events in a distributed system to provide a partial ordering of those events. It enables processes to determine the causal relationship between events without relying on synchronized physical clocks.

Overview
The concept was introduced by computer scientist Leslie Lamport in his 1978 paper “Time, Clocks, and the Ordering of Events in a Distributed System.” In the Lamport logical clock algorithm, each process maintains a counter that it increments before each event it generates. When a process sends a message, it includes its current counter value; the receiving process updates its own counter to be greater than both its current value and the received timestamp before processing the message. This mechanism ensures that if event a causally precedes event b (denoted a → b), then the timestamp of a is less than the timestamp of b. However, the converse does not necessarily hold: equal or ordered timestamps do not guarantee causality, only a necessary condition.

Lamport timestamps are widely employed in distributed algorithms such as mutual exclusion, snapshot recording, and replicated state machine protocols. They are valued for their simplicity and low overhead compared to vector clocks, which provide a stronger guarantee of capturing causality.

Etymology/Origin
The term combines the surname of Leslie Lamport, the inventor of the logical clock, with “timestamp,” a common computing term referring to a record of the time at which an event occurs. The name reflects the method’s purpose: assigning a logical time indicator to events.

Characteristics

• Scalar Value: Each event is associated with a single integer, simplifying storage and comparison.
• Partial Ordering: Provides a “happens‑before” relation that is a strict partial order; not all events are comparable.
• Causality Condition: If a → b, then TS(a) < TS(b), where TS denotes the Lamport timestamp.
• Clock Update Rules:
  1. Local Event: Increment local counter before timestamping the event.
  2. Send Event: Increment counter, attach it to the outgoing message.
  3. Receive Event: Set counter to max(local_counter, received_timestamp) + 1.
• Non‑uniqueness: Different events may share the same timestamp if they are concurrent (neither causally influences the other).
• Low Overhead: Requires only a single integer per process, making it efficient for systems with many nodes.

Related Topics

• Vector Clocks: An extension of logical clocks using a vector of counters to capture a stronger causality relationship.
• Distributed Systems: The broader field in which logical time mechanisms are applied.
• Causal Ordering: The concept of preserving the cause‑effect relationship among messages.
• Mutual Exclusion Algorithms: Protocols such as Ricart‑Agrawala that use Lamport timestamps to order requests.
• Snapshot Algorithms: Techniques like Chandy‑Lamport snapshot that employ logical timestamps to record consistent global states.