Vector Clocks

The Lamport clock does not ensure that if C(a) < C(b) it will be a cause-effect of a over b (a -> b).

Event a: m1 is received at T=16.

Event b: m2 is sent at T=20.

Therefore we cannot conclude that a causes b.

Before it executes an event Pi it executes VCi[i] = VCi[i] + 1

When the process Pi sends the message m to Pj, it places in the timestamp ts(m) the value VCi right after the execution of the previous step.

After receiving the message m, Pj saves for each k the VCj[k] = max(VCj[k], ts(m)[k]), executes the initial step, and then delivers it to the application.

It is necessary to ensure that m is only delivered after all casuistic messages have been delivered.

Pi increments VCi[i] only when it sends a message, and Pj adjusts VCj when receiving a message.

• ts(m)[i] = VCj[i] + 1

• ts(m)[k] <- VCj[k] for every k != i