-
Notifications
You must be signed in to change notification settings - Fork 1
Time
a hb b means that event a happened before event b.
Clock Condition. For any events a, b: if a --> b then C(a) < C(b).
Since A--> B is equivalent to !B --> !A, we have: if C(a) >= C(b) then a !--> b. We ignore the case C(a) == C(b), we have if C(a) > C(b) then a !--> b which is equivalent to if C(b) < C(a) then b --> a or a and b are concurrent. Since a and b are symmetrical, we have if C(a) < C(b) then a --> b or a and b are concurrent. Therefore when we order events a and b
according to this rule, if we have C(a) < C(b), we know:
-
a happened before bor -
aandbare concurrent
For both two cases, we order a and b. And we ensure that we respect Clock
Condition since b !--> a.
IR2. (a) If event a is the sending of a message m by process Pi, then the message m contains a timestamp Tm = Ci(a). (b) Upon receiving a message m, process Pj sets Cj greater than or equal to its present value and greater than Tm.
(b) says Pj = max(Pj', Tm). But it's not precise. Take the following example,
if if Q? = Q2, (b) is satified. But the result is that Q has two events that
have the same LC. And the first Q2 hb P1 which is not true.
P1
P --------|-------------------------------->
\
\
Q -|---|-----|----------------------------->
Q1 Q2 Q?
The exact algorithm should be:
Pj := max(Pj', Tm);
If (Pj = Pj') Pj := Pj + 1;
Dynamo uses it
Spanner uses it.