Difference between Lamport timestamps and Vector clocks

Question

Lamport timestamps and vector clocks sound like almost the same thing. Both are used to determine the order of events in a distributed system. What are their key differences?

Answer 1

Summary:

• Lamport timestamps and vector clocks are both logical clocks, and both provide a total ordering of events consistent with causality. Linearizability is not guaranteed.
• Vector clocks allow you to determine if any two arbitrarily selected events are causally dependent or concurrent. Lamport timestamps cannot do this.
• Lamport timestamps are more compact. Vector clocks require overhead proportional to the number of nodes.

Detail:

Both logical clocks allow one to totally order events in a way that is consistent with causality; this is true because every causal dependency results in an increased timestamp and because the clock value can be arbitrarily ordered by node ID when ties occur (i.e. for concurrent events). For both clocks, you can assert that if A "happens before" B, then Clock(A) < Clock(B).

Vector clocks take this a step further by allowing one to compare any two events and check to see if they are causally dependent or concurrent. Put another way, not only can you show that if A "happens before" B, then VectorClock(A) < VectorClock(B), you can also assert the converse: if VectorClock(A) < VectorClock(B) then A "happened before" B.

EDIT: an important caveat is that events are only arbitrarily totally ordered (i.e. by using the node ID to break ties for "concurrent" events). Linearizability is a stronger guarantee that neither logical clock can provide on its own.

Lamport timestamps employ a per-node counter to provide a causal ordering of events and an unique node ID to break ties and provide a total ordering, so the overhead of a Lamport timestamp does not vary with the number of nodes. Vector clocks employ per-node counters of every node, so the size of a vector clock is proportional to the number of nodes.

A great resource I found that more formally summarizes these concepts is a paper about Hybrid Logical Clocks, which can be found here: https://cse.buffalo.edu/tech-reports/2014-04.pdf Hybrid Logical Clocks are similar to Lamport timestamps, but they also provide a few other benefits.

Answer 2

Although similar they have different purposes: version vectors can distinguish whether two operations are concurrent or one is causally dependent on the other; Lamport timestamps enforces total ordering. Total ordering although more compact cannot tell whether two operations are concurrent or causally dependent.