Vector Clock

The Fidge/Mattern's Vector Clock makes it possible to imply the happened-before relation by comparing the timestamps of the events and vice versa.

e → f ⇔ C(e) < C(f)

Where C(i) is the vector clock timestamp of event i.

V = V' iff <∀i: V[i] = V'[i]> V < V' iff <∀i: V[i] ≤ V'[i]> ∧ <∃i: V[i] < V'[i]>


To implement vector clock, each process has to have its own vector clock. The protocol for process Pi is as follows:
* On executing an interval event:     Ci[i] := Ci[i] + 1 * On sending a message m:     Ci[i] := Ci[i] + 1     piggyback Ci on m *On receiving a message m:     let tm be the timestaqmp piggybacked on m     ∀k Ci[k] := max{Ci[k], tm[k]}     Ci[i] := Ci[i] + 1

Comparison complexity is order of n where n is the number of processes.

The following is a property of vector clock where e and f are events on processes pi and pj, respectively.
e → f iff (i = j) ∧ (C(e)[i] < C(f)[i]) ∨ (i ≠ j) ∧ (C(e)[i] ≤ C(f)[i])