0

I've heard about vector clocks and how to test if a message was sent before another message.

E.g. Message A was sent before message B if every element of the vector of message A is smaller or equal then the belonging element of the vector of message B.

Also, there needs to be at least one element in the vector of message A that is smaller (and not equal) than the belonging element of message B.

As I see, the second parts just tests if there are elements that differ.

Is there a possibility where all elements of the vector of message A are the same as the belonging element of the vector of message B or is the second check unnecessary?

I mean, each element can only be incremented by the belonging process only and there if e.g. process X sends a message to process Y and a message gets back, the element of process Y will be changed in process Y only and the element of process X will be changed in process X only. So, there would be an update from the own element and the foreign element in any case. This means, there could not possibly be a case where all elements of the vector of message A and all elements of the vector of message B are completely the same, right?

Could the performance of the vector clock be increased if the test for equality is removed?

Improve this question
6
  • These are arrays. 2 belonging elements are elements with the same index.
    – dan1st
    Commented Jan 13, 2020 at 11:57
  • Every message sends a vector(array) of "timestamps". But these timestamps are only logical timestamp. Every process increments it's own timestamp on each action/transmission and it doesn't have to do anything with real timestamps.
    – dan1st
    Commented Jan 13, 2020 at 11:59
  • trivally they are equal if you are comparing the same timestamp
    – Ewan
    Commented Jan 13, 2020 at 12:03
  • @Ewan These are logical timestamps. Every process in a distributed system has it's own logical timestamp that is just a number. It increments only it's own logical timestamp on every process.
    – dan1st
    Commented Jan 13, 2020 at 12:05
  • @dan1st I understand that, what im sayign is that if you take two arbitrary messages, you might have chosen the exact same one twice, in which case the timestamps would be exactly the same
    – Ewan
    Commented Jan 13, 2020 at 12:08

1 Answer 1

Reset to default
1

Given that the algorithm for vector clocks is defined such that any process increases one of the values in the vector it should be impossible for any two distinct VC to have the same value.

However, there is obviously the trival case of comparing a message with itself, when you would of course expect the VC to be equal as they are duplicates of each other.

Less trivially, although the algorithmic definition should never produce a duplicate value, it's easy to see that in practice each line of code in a process might not update the VC, if you use the VC out side of the processes, perhaps for logging, or your messages run on an underlying transport mechanism such as a queuing software which doesn't implement the VC itself; that you could end up with the same VC being used in more than one place.

Skipping the equality step doesn't seem advisable

Improve this answer
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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