patternMinor
Vector clocks: Why is it necessary to increment my clock on receiving a message?
Viewed 0 times
whynecessaryincrementmessagereceivingclockclocksvector
Problem
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?
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?
Solution
Look at the definition of $
-
$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).
-
$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).
Context
StackExchange Computer Science Q#55209, answer score: 4
Revisions (0)
No revisions yet.