3 - Logical Vector Clocks Flashcards
Explain what logic clocks are, and what problem they solve.
Physical clocks are not perfect, so asynchronous DS need to achieve synchronisation through messages. Logic clocks capture causal dependencies, by relating events.
Explain the three critea for Happened Before Relation.
- local order: if a,b in Ei, and a occurs before b, then a -> b
- message exchange if a in Ei is the event of sending a message m and b in Ej is the event of receiving m, then a -> b
- transitivity if a -> b and b-> c, then a -> c
Explain what happens when event b is neither in the past or the future of event a, in case of HB relation.
Then the events are concurrent ( a||b)
Is the concurrency HB relation transistive?
No, the relation for concurrent events cannot be determined
When does a logic clock characterize the HB relation?
C(a) < C(b) iff a ->b
C = E->S
Explain how lamports scalar clock works.
If a in Ei and a is not a message-receive event, then
- P i executes LC_i ++, and then LC(a) := LC_i
If a is the event “sending message m” in P_i and b is the event “receiving m” in P_j then
- P_i sends LC(a) along with m
- P_j assigns LC_j := max(LC_j +1,LC(a)+1)
- P_j sets LC(b) := LC_j
Explain how Lamports logical clock violates the HB relation.
Lamports clock is scalar: any pair of events in any two different processes are concurrent, but in general do not have equal clock value.
(if LC(a) < LC(b) then either a -> b or a || b)
Regarding vector clocks: P1 sends m with V(a) = (3,5) and P2 has latest event b with V(b) = (1,7). What will be the new vclock value of the receive event (c) on P2?
(1,7) -> (1,8)
max((1,8),(3,5))=(3,8)
How can you compare two clock vectors?
V < W iff V leq W and V != W
What is the “meaning” of the value inside a local vector clock.
It is the amount of events that occured in Process x that process i knows about. This can be communicated either directly or indirectly.
Can concurrency occur in vector clocks?
yes, due to delays etc. it can happen that such comparrison confloicts happen.
Do vector clocks violate the HB relation?
no, they succeed in upholding the characteristics.