Lamports

Lamport timestamps, commonly referred to as Lamport clocks, are a method for assigning a scalar logical time to events in a distributed system, without relying on synchronized physical clocks. They are named after computer scientist Leslie Lamport, who introduced the concept in the late 1970s. The purpose is to capture a partial ordering of events based on causality rather than wall-clock time and to enable systems to reason about the sequence of events across processes.

Operation: Each process maintains a counter. On each local event, the counter increments by one and the event gets that value. When sending a message, the process includes its current counter value. Upon receiving a message, the receiving process updates its own counter to max(received timestamp, its own counter) and then increments it by one. The resulting timestamps impose a happens-before relation: if event A happens before event B, then timestamp(A) < timestamp(B).

Limitations and extensions: Lamport timestamps preserve causality but do not detect concurrent events, since distinct but concurrent events can receive ordered timestamps. They are not actual time. To capture more causality information, vector clocks are used, which track the state of each process. Lamport clocks are often used as a lightweight ordering mechanism in distributed databases and algorithms that need a basic ordering without heavy metadata.

History and impact: Introduced in 1978-79, Lamport's work on time and clocks is foundational in distributed computing. The concept underpins many synchronization and replication strategies and informs modern distributed system design, where understanding event ordering is essential.