Drawing a vector clock timeline

Question

I have a question which is asking to draw a vector clock timeline diagram to illustrate the partial order happened-before relation on events.

Here are the vector clocks:

V(a) = (4,4,2)
V(b) = (4,2,2)
V(c) = (2,2,3)
V(d) = (4,3,2)
V(e) = (4,4,4)
V(f) = (3,2,2)

I am not sure how to determine which process each event belongs to. All the examples that I have use vector clocks which have values which begin at 0 e.g. V(a)=(1,0,0) so I would assume that event a is the first event to occur or that it is concurrent with other processes but I am not sure how to do this particular question.

Can anyone help?

Thanks

Answer 1

What you are looking for is the following diagram :

p1 ------- f(3,2,2) ----------- b(4,2,2) ------------------------------------

p2 --------------------------------- d(4,3,2) -------- a(4,4,2)--------------

p3 -------- c(2,2,3) ------------------------------------------- e(4,4,4) ---

where there is also interprocess communication between b -> d and a -> e

Why is that?

You see that the process that have something common are on the same line and then you can logically order them on the process line considering nothing had changed on that processe's line. If you do this for each one of them then it will be easy to sketch the whole interaction.

Hope this is what you were looking for, although i see this is quite an old question. :D

Answer 2

Assuming the original vector clock algorithm, as described by Fidge, this set of vector clock readings in impossible.

First, observe that there is a chain of linearly ordered events: f < b < d < a < e. Each element in this chain differs from the next only in one clock component and only by 1. This means that all these events happen on the same process, because otherwise a pair of events from the chain must be connected by a path of messages (because they are ordered and, hence, causally connected), but each message send and receipt change 2 components of vector clock (once for sending and once for receiving).

Hence, all events from the chain happen on the same process, but then the clock component, corresponding to this process must increase monotonically along the chain. Contradiction.