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.


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


To implement vector clock, each process has to have its own vector clock. The protocol for process P_i 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 p_i and p_j, respectively.

e → f iff (i = j) ∧ (C(e)[i] < C(f)[i]) ∨ (i ≠ j) ∧ (C(e)[i] ≤ C(f)[i])