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.
Manipulating Vector Timestamps:
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.
Vector Timestamps Example:
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.