4
$\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$
4
$\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$
2
$\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$
-1
$\begingroup$

Both logical clocks allow one to totally order events in a way that is consistent with causality. this is true because every causal dependency result's in an increased timestamp.

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to COMPUTER SCIENCE @SE. How does this answer What are [the] key differences between Lamport timestamps and vector clocks ? $\endgroup$
    – greybeard
    Dec 22 '21 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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