Vector Clock Algorithm Assignment Help

Generalize logical clocks to offer non-causality information along with causality information.
Implement along with values drawn from the partially ordered set rather than an entirely ordered set.
Assign the value V( e ) in order to every computation event e in an execution so that the a ® b if and only if V( a ) Less than V ( b ).

Vector Timestamps Algorithm:

Each pi keeps an n-vector Vi, initially all 0's
Entry j in Vi is pi 's estimate associated with how many steps pj has taken
Every msg pi sends is timestamped along with current value associated with Vi
At each and every step, increment Vi[ i ] through 1
When finding a message along with vector timestamp T, update Vi 's components j ≠ i so that Vi[ j ] = max( T[ j ],Vi[ j ])
If a is an event at pi, after that allocate V( a ) to be value associated with Vi at end of a.

Let V and W be two n-vectors of integers.

Equality: V = W iff V[ i ] = W[ i ] for all i.
- Example: ( 3, 2, 4 ) = ( 3, 2, 4 )
Less than or equal: V ≤ W iff V[ i ] ≤ W[ i ] for all i.
- Example: ( 2, 2, 3 ) ≤ ( 3, 2, 4 ) and ( 3, 2, 4 ) ≤ ( 3, 2, 4 )
Less than: V less than W iff V Less than equal to W but V W
- Example: ( 2, 2, 3 ) Less than ( 3, 2, 4 )
Incomparable: V || W iff ! ( V ≤ W ) and ! ( W ≤ V ).
- Example: ( 3, 2, 4 ) || ( 4, 1, 4 )

The partial order on n-vectors simply described is actually different then lexicographic ordering.
Lexicographic ordering is really a complete order on vectors.
Consider ( 3, 2, 4 ) versus ( 4, 1, 4 ) within the 2 approaches.

V(g) = ( 0, 0, 1 ) and V(b) = ( 2, 0, 0 ), which are incomparable. Compare with logical clocks L(g) = 1 and L(b) = 2.