If a has a smaller Lamport timestamp than b, did a happen before b?

Not necessarily—a smaller timestamp is consistent with happened-before but does not imply it, because concurrent events can receive ordered timestamps. To decide causality precisely you need vector clocks, not scalar logical clocks.

Logical and Physical Clocks

Logical clocks order events by causality without reference to real time, while physical clock synchronization keeps separate machines' real-time clocks close together despite drift.

Definition

A logical clock assigns to each event an integer timestamp that is monotonic along each process and increases across communication, capturing causal order; physical clock synchronization is the process of adjusting machines' hardware clocks so that they read approximately the same real time.

Scope

This topic covers Lamport's logical (scalar) clocks and the happened-before relation they respect, the construction of a total order from logical timestamps, and physical clock synchronization—bounding drift, exchanging timestamps to estimate offset, and the algorithms (Cristian's method, Berkeley algorithm, NTP) used in practice. It contrasts when causal logical time suffices and when real time is genuinely required.

Core questions

How can timestamps be assigned so that they respect the causal happened-before relation?
How is a consistent total order on events built from logical clocks?
How closely can physical clocks be synchronized given variable network delay and drift?

Key theories

Lamport logical clocks: Each process keeps a counter incremented on every event and carried on messages; the resulting timestamps respect happened-before, and ties broken by process identifier yield a total order consistent with causality.
Probabilistic and round-trip synchronization: Cristian's method estimates a remote clock by measuring round-trip time and assuming symmetric delay, providing probabilistic bounds on the synchronization error achievable over a network.
Network Time Protocol: NTP organizes time servers into a stratified hierarchy and uses statistical filtering of repeated offset measurements to discipline clocks across the internet to within milliseconds.

Clinical relevance

Logical clocks order operations in replicated stores and message queues without trusting wall-clock time, while physical synchronization underlies timestamp-ordered databases, distributed tracing, and security protocols that depend on bounded clock error.

History

Lamport's 1978 logical-clock paper recast time in distributed systems as a causal rather than physical notion; in parallel, Cristian and others developed probabilistic synchronization, and Mills's NTP became the standard mechanism for keeping internet clocks aligned.

Debates

Logical versus physical time for ordering operations: Logical clocks guarantee causal correctness without trusting hardware clocks, but cannot relate events to real time; physical clocks enable real-time reasoning at the risk of incorrect ordering when drift exceeds message delay, motivating hybrid approaches.

Key figures

Leslie Lamport
Flaviu Cristian
David Mills

Seminal works

lamport1978
mills1991
cristian1989

Frequently asked questions

If a has a smaller Lamport timestamp than b, did a happen before b?: Not necessarily—a smaller timestamp is consistent with happened-before but does not imply it, because concurrent events can receive ordered timestamps. To decide causality precisely you need vector clocks, not scalar logical clocks.