4
$\begingroup$

Assume I have a distributed system of entities, each with a replica of the same data object that can be modified by broadcasting the changes and I'm using vector clocks to know how to order changes.

In this scenario, Why would I need to increment my own clock if I receive an update? (I noticed in the original paper on vector clocks, they didn't mention this rule, yet followed it in the examples...) Would it be sufficient if I only incremented my clock when I change the data object?

$\endgroup$
  • 1
    $\begingroup$ Actually my question is about version vectors, which don't require incrementing your own clock upon applying an update. $\endgroup$ – Marcel Klehr Apr 26 '16 at 18:23
3
$\begingroup$

Look at the definition of $<_H$.

We say that $e_1<_H e_2$ (event 1 happened before event 2) if:

  1. $e_1,e_2$ took place in the same process, and $e_1$ happened first (events within the same process are ordered).

  2. $e_1,e_2$ are the sending and receiving of some message $m$, correspondingly.

Finally, we take the transitive closure of the above, and this yield Lamport's happened before relation.

Our objective is to assign time stamps to events, $T_{e_i}$ with a partial order $<_t$, such that $e_1<_H e_2 \iff T_{e_1}<_t T_{e_2}$.

The timestamps suggested here are vectors in $\mathbb{N}^n$, with the ordering $T_{e_p}<_t T_{e_q} \iff T_{e_p}[p]<T_{e_q}[p]$ where $e_p,e_q$ are events in processes $p,q$ correspondingly (assume each time stamp contains the process id).

Back to your question, not updating your clock upon receiving a message would cause your new relation $<_t$ to disagree with $<_H$ in events within the same process. For example, you would have $c\not\rightarrow d$ (figure 3). In addition, this is mentioned in the paper (rule 2, increase the local clock at each atomic event, which is either sending or receiving a message).

$\endgroup$
  • 1
    $\begingroup$ Mh, the paper's definition of the partial ordering is different from the one on wikipedia :/ It appears in the paper only the p component is compared and needs to be strictly less, while on Wikipedia all components must be less or equal and one must be strictly less. $\endgroup$ – Marcel Klehr Apr 1 '16 at 19:28
  • $\begingroup$ I think I found the answer to my problem. It seems my feeling was correct: Version vectors are updated upon local changes (by incrementing the local counter) and upon receiving remote changes by using max() for all values. $\endgroup$ – Marcel Klehr Apr 1 '16 at 19:41
  • $\begingroup$ @MarcelKlehr It seems like you're confusing Version Vectors with Vector Clocks. For more informatio, see haslab.wordpress.com/2011/07/08/…. $\endgroup$ – nubbel Jul 27 '17 at 12:42

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.