C - Implementing Vector Clocks

tntcoder · 1 Nov 2009 at 10:48

Hey,

http://en.wikipedia.org/wiki/Vector_clock

I need to implement vector clocks and was wondering if someone can give me some ideas on how to solve the following issues in C.

According to the algorithm, each process has a local integer clock, thats cool and ive done that.

Each time a process receives a message, it increments its own logical clock in the vector by one and updates each element in its vector by taking the maximum of the value in its own vector clock and the value in the vector in the received message (for every element).

Now say I have N processes running, how does process 3 know which vector element belongs to Process 6?

What happens if a new process starts say 5 minutes after all the others?

Basically, I'm not quite sure I can work out how it can be implemented with a) a variable number of processes and b) processes which don't know about other processes or where they maybe in the vector list.

Any ideas?

dangerstat · 1 Nov 2009 at 11:14

tntcoder said:
Hey,

http://en.wikipedia.org/wiki/Vector_clock

I need to implement vector clocks and was wondering if someone can give me some ideas on how to solve the following issues in C.

According to the algorithm, each process has a local integer clock, thats cool and ive done that.

Now say I have N processes running, how does process 3 know which vector element belongs to Process 6?

What happens if a new process starts say 5 minutes after all the others?

Basically, I'm not quite sure I can work out how it can be implemented with a) a variable number of processes and b) processes which don't know about other processes or where they maybe in the vector list.

Any ideas?

Can you post the code you have so far? I've not played about with Vector Clocks before but wouldn't mind giving it a shot.

tntcoder · 1 Nov 2009 at 11:26

I would, but currently its still in conceptual stage im afriad

Basically though each process has a logical clock.

Code:

int lClock = 0;
...
void eventOccurring()
{
     // Event about to happen -> update local clock
     lClock++;
}

So lClock is essentially element Pi of the vector, where i is the process ID. When I work out how to solve the problem that Px may not know Pn exists (and hence manipulate the vector without getting confused) I will build the vector.

I was thinking about having a local integer array to represent the vector, then serialize it to a delimited string before it hits the network (eg "V1:V2:...:Vi") because it will have the problem that it's size will grow in a linear pattern with the process count and possibly take up a lot of space/bandwidth.

sniffy · 1 Nov 2009 at 17:59

That looks like a real head-****. Do you mind if I ask what you use vector clocks for? Sorry I can't help, just curious

BullBoyShoes · 2 Nov 2009 at 10:12

do you 'need' to implement vector clocks?

Looks like you need some sort of task scheduling or an RTOS, most of which you can buy OTS

Caustic · 2 Nov 2009 at 22:52

Just reading the link. Seems like an interesting problem. I have to confess I have never heard of the concept before, but if I have understood it right:

"Now say I have N processes running, how does process 3 know which vector element belongs to Process 6?"

It doesn't. That doesn't appear to be the idea at all. Each process is working alone and with just the infomation it receives in each message. The clocks are used to purely keep track of when each event happened.

"What happens if a new process starts say 5 minutes after all the others?"

If I get the idea, then nothing special. It sets its counter to 0 and waits to get a message, just like the others.

Interesting concept, I'll have to do some more reading! It got my attention because you wanted to implement it in C, and I do like plain old C!

(Please note, I might be completely wrong about everything!)