3 - Logical Vector Clocks Flashcards

1
Q

Explain what logic clocks are, and what problem they solve.

A

Physical clocks are not perfect, so asynchronous DS need to achieve synchronisation through messages. Logic clocks capture causal dependencies, by relating events.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Explain the three critea for Happened Before Relation.

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Explain what happens when event b is neither in the past or the future of event a, in case of HB relation.

A

Then the events are concurrent ( a||b)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Is the concurrency HB relation transistive?

A

No, the relation for concurrent events cannot be determined

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

When does a logic clock characterize the HB relation?

A

C(a) < C(b) iff a ->b

C = E->S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Explain how lamports scalar clock works.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Explain how Lamports logical clock violates the HB relation.

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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?

A

(1,7) -> (1,8)
max((1,8),(3,5))=(3,8)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How can you compare two clock vectors?

A

V < W iff V leq W and V != W

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the “meaning” of the value inside a local vector clock.

A

It is the amount of events that occured in Process x that process i knows about. This can be communicated either directly or indirectly.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Can concurrency occur in vector clocks?

A

yes, due to delays etc. it can happen that such comparrison confloicts happen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Do vector clocks violate the HB relation?

A

no, they succeed in upholding the characteristics.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly