12
$\begingroup$

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?

$\endgroup$

2 Answers 2

14
$\begingroup$

Summary:

  • Lamport timestamps and vector clocks are both logical clocks, and both provide a total ordering of events consistent with causality.
  • 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.

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. 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.

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.