Lamporttider

Lamporttider, or Lamport timestamps, are a method for assigning a logical time to events in a distributed system without relying on synchronized physical clocks. Introduced by Leslie Lamport in 1978, they provide a way to establish a causal order of events that occur across processes communicating by message passing.

How they work: each process maintains a local counter. The counter is incremented for every local event. When a process sends a message, it attaches the current counter value as the event’s timestamp. Upon receiving a message with timestamp t, the receiving process updates its own counter to max(local counter, t) + 1, and treats the receipt as an event with that new timestamp. The resulting timestamps are monotonically increasing and respect the happens-before relation: if event A happened before event B, then the timestamp of A is less than the timestamp of B.

Properties and limitations: Lamport timestamps provide a partial order of events that is consistent with causality but do not capture the full concurrency structure. If two events are independent, their timestamps may not reveal this independence, and total ordering cannot be inferred solely from the timestamps. To fully characterize causality, vector clocks are used as a more precise alternative, at the cost of greater storage and communication overhead.

Applications: they are used to order events in distributed databases, debugging and monitoring distributed systems, coordinating actions in distributed algorithms, and implementing simplified mutual exclusion and commit protocols where a lightweight causal order suffices.

History and relation: Lamport clocks influenced later work on distributed causality, including vector clocks by Fidge and Mattern. Lamporttider remain a foundational concept for understanding time and ordering in distributed computing.