0
$\begingroup$

Singhal–Kshemkalyani’s differential technique is based on the observation that between successive message sends to the same process, only a few entries of the vector clock at the sender process are likely to change. This is more likely when the number of processes is large because only a few of them will interact frequently by passing messages. In this technique, when a process Pi sends a message to a process Pj , it piggybacks only those entries of its vector clock that differ since the last message sent to Pj.

I am understanding above but not the following statement

this technique requires that the communication channels follow FIFO discipline for message delivery. link

Chapter 3 -Logical clock from above book and sub topic is Efficient implementations of vector clocks

Thanks lot.

$\endgroup$
  • 2
    $\begingroup$ Welcome to the site! Could you cite the source of the text you quote? $\endgroup$ – David Richerby Sep 8 '18 at 18:45
3
$\begingroup$

All it's saying is that the messages between two processes need to be received in the order they are sent. If I'm going to send only differences between the previous message, we both better agree on what "the previous message" is.

For example, if I send "increment the first and second component" and then "increment the first and third component" but you receive them in the opposite order, you are likely to make form incorrect assumptions about how these messages relate to messages you're receiving from other processes. The correct intermediate state will have a vector clock that looks like $(1,1,0)$ but the one you'd reconstruct from the out of order messages is $(1,0,1)$. A message from another process with vector clock $(2,0,1)$ might then look like its strictly after the out-of-order message when, in fact, it is concurrent with it.

$\endgroup$

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.