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:
![]() 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.
|
Foundations > Distributed Computing >