Starting from:
$25
Problem Set 2: Time and Ordering, Snapshots
Problem Set 2: Time and Ordering, Snapshots
1. [5 pts] A clock is reading 12:33:57.0 (hr:min:sec) when it is discovered to be
3 seconds fast. Explain why it is undesirable to set it back to the right time at
that point and show (numerically) how it should be adjusted so as to be
correct after 6 seconds has elapsed.
2. [5 pts] A client attempts to synchronize with a time server. It records the
round-trip times and timestamps returned by the server in the table below.
Which of the times in the table below should it use to set its clock and why?
What should it set its clock to? What is the estimated accuracy w.r.t to
server’s clock? If minimum time to send or receive a message from the server
is know to be at least 8ms, does your answer change? Why?
3. [3 pts] If in problem 2 if it is required to sync to within 1ms of the server, is
that feasible? Explain your answer.
4. [5 pts] By considering a chain of zero or more messages connecting events e
and e′, and using induction, show that eà e′ implies L(e) <= L(e'), where
L(e) is the Lamport timestamp of event e.
5. [5 pts] Show that Vj[i] <= Vi[i] where Vi is vector clock at process i.
6. [5 pts] In a similar fashion to 4, show that eà e′ implies V(e) <= V(e')
7. [5 pts] Using result from 5, show that if e and e′ are concurrent that neither
V(e) <= V(e') nor V(e’) <= V(e). Thus show that if V(e) < V(e') then e à e’.
Round-trip Time (ms) Server Clock (hh:mm:ss)
24 12:43:33.456
28 12:43:35.235
22 12:43:36.124
(
I. Mark one pair of events that are concurrent with each other.
P0
P1
P2
P3
② To
=3 .
Q→- t -3 -
Z
Cµo% ?? , Eggo ,
' ' o ) czgo.gl ,
o ) -
⑥ .
*
Logo ?
" .
⑥
-
'
1070,0 ) Go ggglgo ) -
'
④ ca ,
e .
-
- 9
I
II. Mark one pair of events that are concurrent with each other.
P0
P1
P2
P3
iII. Identify an event at process P2 that happens before an event at P1.
P0
P1
P2
P3
0
O
IV. Mark all Lamport timestamps on this figure for all events.
All processes start with zero timestamps.
P0
P1
P2
P3
o
K B 4 5 6
A
70
3 4 5
72
A 3 6
Oak 45
O •
3 4 56
V. Mark all vector timestamps on this figure for all events.
All processes start with zero timestamps.
P0
P1
P2
P3
[4%1,0] ↳ 0,40 ) [3,011,904*441,0] [5,448 [6,4/1,0]
[9%0]
[ Oglio ,0] [0,3%0] [0,9019 [3,6%0]
[0,0/90] [ 0,20,0] [94/90]
[ o , 2,03 [0,9307 [ 3,4503 [ 3,46 ;D
↳ 998
Go , 1,03 Co , e. 4,03 C344,07
[99%0]
Cop ,o,D Cos9232132 Cop ,2 , [932,43 [ 93,45 )
VI. Mark all Lamport timestamps on this figure for all events.
All processes start with zero timestamps.
P0
P1
P2
P3
•
45 6 7 8 9
00
"
7- 10
O
6 8
O
23 4 89 9 10
VII. Mark all vector timestamps on this figure for all events.
All processes start with zero timestamps.
P0
P1
P2
P3
[ go ,o,o)
['
'
'
' " D G " " 'D C 35923 [940,336,1%3] [6,1%3]
[0,4%3
coiled
aim airbed
[90,903 amid G. ii. D
[990 'D
[ on , Coming [ on .gs) G 's Gibbs ) [5%2,6] [6,447)
P0
P1
P2
a
Marker Message
Regular Message c c
b
I. Chandy-Lamport Global Snapshots Algorithm
• Mark the entire global snapshot collected.
soit si Duplicate Co2 co coffee?dcI easy Record
, I
I avail :c
V a
→
IT Duplicate marker
Ago .µ code
P2 is initiator marker
. Record local state 52
Tops recording 802
• Sends od markers
• Turn on recording on channels Coz , Cry
Sisco , =L 95222242=2
Sos 90=2 Sifu =L
see # =L
Sets , =L
II. Chandy-Lamport Global Snapshots Algorithm
• Mark the entire global snapshot collected.
P0
P1
P2
a
Marker Message
Regular Message c c
b
c d
e
f
& is
go ,
Record 900 at
deg
ps2
,
Record
bcoi-h7@uoiiy9urlicdI.L
's
t
.
p tourism
S2 Cox g. plicate
Go - Sd •
Record
Ci27c02
SI = coz =L , Ce ,
- L )
so -
-
eco = ed gin - L
S 1=71--4 )
III. Mark all Lamport timestamps for application messages
on this figure for all events.
All Lamport timestamps start from zero.
P0
P1
P2
a
Marker Message
Regular Message c c
b
c d
e
f
O
I 3 6
49
O
2 3
⑨
I 2 4 5 G
IV. Mark all vector timestamps for application messages
on this figure for all events.
All vector timetstamps start from zeroes.
P0
P1
P2
a
Marker Message
Regular Message c c
b
c d
e
f
[ go ,o) C " " D C 2,923 [ 3,443
[ 5h03 [1,323%0] Glib
[ 999
fo ,o,D [ 0,923 Grid C '
is [ 1.3.53
Problem Set 2: Time and Ordering, Snapshots
1. A clock is reading 12:33:57.0 (hr:min:sec) when it is discovered to be 3
seconds fast. Explain why it is undesirable to set it back to the right time at
that point and show (numerically) how it should be adjusted so as to be
correct after 6 seconds has elapsed.
It will be undesirable to set the clock back to the right time as we will have
stored time events in the future in our log which will cause the system to
malfunction. We will fix this by slowing down our clock. To fix the 3 second
drift in 6 seconds, we will slow down our clock by a factor of
½(Terror+6seconds-12:33:57:0)+12:33:57:0.
2. A client attempts to synchronize with a time server. It records the round-trip
times and timestamps returned by the server in the table below. Which of
the times in the table below should it use to set its clock and why? What
shouldit set its clock to? What is the estimated accuracy w.r.t to server’s
clock? If minimum time to send or receive a message from the server is
known to be at least 8ms, does your answer change? Why?
Round-trip Time (ms) Server Clock
(hh:mm:ss)
24 12:43:33.456
28 12:43:35.235
22 12:43:36.124
The client should use the time corresponding to the minimum round trip time of 22
seconds.
The error for the case with no network latency will be (22-0-0)/2 = 11ms according to
Christian’s algorithm. The time set by the algorithm will be 12:43:36:124 + 0.011 =
12:43:36:135
The Error will be at most (22-8-8)/2ms = 3ms with Christian’s algorithm.
The time set by the algorithm will be 12:43:36.124 + {(22 + 8 – 8)/2 ms}
= 12:43:36.124 + 0.011 = 12:43:36.135
While the overall time remains the same, with the server latency being 8
seconds, the error is bounded to 3ms while the error for a network with no
latency is at most 11ms. This is because as the time duration for
measuring intervals decreases (as we go towards no latency), measuring
time gets harder.
3. If in problem 2 if it is required to sync to within 1ms of the server, is that
feasible? Explain your answer.
To synchronize a clock within ± 1 ms it is necessary to obtain a round-trip time of no
more than 18 ms if the network latency is 8 ms. (RTT - 8 – 8 = 1, RTT = 18ms) It is
possible to obtain round-trip time of 18ms, but it may be improbable that such a time
could be found. The file server risks failing to synchronize over a long period, when it
could synchronize with a lower accuracy.
4. By considering a chain of zero or more messages connecting events e and
e′, and using induction, show that e→e′ implies L(e) <= L(e'), where L(e)
is the Lamport timestamp of event e.
Step 1: The event e1 - e2 will be true if there is a direct connection between
the two nodes and will imply L(e1) <= L(e2) (Will be true as the event e1 will
send its value (1 in this case) which will be incremented by e2)
Step 2: Let e1 - e2 - … - ek-2 - ek-1-ek imply L(e1) <= L(e2) <= … <= L(ek-2)
<= L(ek-1) <= L(ek) be true for k causal events
Step 3: To Prove: L(e1) <= …. <= L(en) will be true for an event n = k+1 that is
en-en+1 if there is a causal relationship between them
Let there be a chain of events connection e and e’ such that e = e1 and e’ = en.
As these are connected, e1-en and from the Induction hypothesis, L(e1) will
be less than L(en). Hence L(e) will be less than L(e’).
5. Show that Vj[i] <= Vi[i] where Vi is vector clock at process i.
Lets us assume that Vj[i] is strictly greater than Vi[i]. If this is true then every
connection from j to i will increase i’s value in the vector array for Vi. This
will also imply that in the beginning state, Pj will have detected an event ei
before Pi itself but this is not possible as there is no way for Pj to know the
events that occur at Process i without process i without process i recording
it. This will also not follow the property of vector clocks that state that “If ej
occurred before pj recorded its state, then ei must have occurred before pi
recorded its state”. As this will not be possible, our assumption must be
wrong and hence Vj[i] must always be less than Vi[i].
6. In a similar fashion to 4, show that e→e′ implies V(e) <=V(e')
Step 1: e1-e2will imply V(e1) <= V(e2) as e1 will be connected to e2 and hence
will at least have all the values of the vector smaller than itself from e1 and
will have all the values greater than e1’s vector array its existing vector array
(e2)
Step 2: Let e1-ek imply V(e1) <= V(ek) be true for all k (Assuming there is a
chain of events leading from e1 to ek)
Step 3: To prove: V(e1) <= … <=V(en) where n = k+1, e1 = e and en=e’.
Let the events e1 be connected to en by a series of events such V(e1) <= V(ek)
by the induction hypothesis. As ek is connected directly to ek+1, ek-ek+1 and
V(ek) <= V(ek+1) is true. This will imply that V(e1)<= V(ek+1) and as k+1 = n,
e1-en and V(e1) <= V(en) (by the Induction Hypothesis).
7. Using result from 5, show that if e and e′ are concurrent that neither V(e)<=
V(e') nor V(e’)<= V(e). Thus show that if V(e) < V(e') then e→e’.
Let e and e’ be concurrent and let e occur at process i and e’ occur at process
j . Because these events are concurrent, none of the messages sent from the
I’th process sent after event e (inclusive) will have sent its timestamp to
process j by the time e’ occurs at pj, and vice versa. We know that the source
increments its value in the vector clock by 1 before sending a message and
the receiving event increments its value by 1 only after receiving the event
(and other entries if their timestamps are greater than the receiving events),
it follows that V j [k] < V i[k] and Vi[j] < Vj[j] and therefore that neither V(e)
<= V(e’) nor V(e’) <= V(e).
This can only be possible when the two events V(e) < V(e’) are causal. Hence
it is proved that e - e’.
P3
I. Mark one pair of events that are concurrent with each other.
P3
II. Mark one pair of events that are concurrent with each other.
P0
P1
P2
P3
P0
P1
P2
iII. Identify an
event at process
P2 that happens before an event at P1.
P3
P0
P1
P2
P3
IV. Mark all Lamport timestamps on this figure for all
events.All processes start with zero timestamps.
P3
V. Mark all vector timestamps on this figure for all
events.All processes start with zero timestamps.
P0
P1
P2
P3
VI. Mark all Lamport timestamps on this figure for all
events.All processes start with zero timestamps.
P0
P1
P2
P3
P0
P1
P2
P3
VII. Mark all vector timestamps on this figure for all
events.All processes start with zero timestamps.
c
Regular Message c
I. Chandy-Lamport Global Snapshots Algorithm•
Mark the entire global snapshot collected.
P0
P1
P2
c
Regular Message c
II. Chandy-Lamport Global Snapshots Algorithm•
Mark the entire global snapshot collected.
P0
P1
P2
a
Marker Message
b
c
Regular Message c
III. Mark all Lamport timestamps for application
messages on this figure for all events.
All Lamport timestamps start from zero.
P0
P1
P2
a
Marker Message
b
c d
e
f
c
Regular Message c
IV. Mark all vector timestamps for application
messages on this figure for all events.
All vector timetstamps start from zeroes.
P0
P1
P2
a
Marker Message
b
c d
e
f
c
Regular Message c
P0
P1
P2
a
Marker Message
b
c d
e
f
1. [5 pts] A clock is reading 12:33:57.0 (hr:min:sec) when it is discovered to be
3 seconds fast. Explain why it is undesirable to set it back to the right time at
that point and show (numerically) how it should be adjusted so as to be
correct after 6 seconds has elapsed.
2. [5 pts] A client attempts to synchronize with a time server. It records the
round-trip times and timestamps returned by the server in the table below.
Which of the times in the table below should it use to set its clock and why?
What should it set its clock to? What is the estimated accuracy w.r.t to
server’s clock? If minimum time to send or receive a message from the server
is know to be at least 8ms, does your answer change? Why?
3. [3 pts] If in problem 2 if it is required to sync to within 1ms of the server, is
that feasible? Explain your answer.
4. [5 pts] By considering a chain of zero or more messages connecting events e
and e′, and using induction, show that eà e′ implies L(e) <= L(e'), where
L(e) is the Lamport timestamp of event e.
5. [5 pts] Show that Vj[i] <= Vi[i] where Vi is vector clock at process i.
6. [5 pts] In a similar fashion to 4, show that eà e′ implies V(e) <= V(e')
7. [5 pts] Using result from 5, show that if e and e′ are concurrent that neither
V(e) <= V(e') nor V(e’) <= V(e). Thus show that if V(e) < V(e') then e à e’.
Round-trip Time (ms) Server Clock (hh:mm:ss)
24 12:43:33.456
28 12:43:35.235
22 12:43:36.124
(
I. Mark one pair of events that are concurrent with each other.
P0
P1
P2
P3
② To
=3 .
Q→- t -3 -
Z
Cµo% ?? , Eggo ,
' ' o ) czgo.gl ,
o ) -
⑥ .
*
Logo ?
" .
⑥
-
'
1070,0 ) Go ggglgo ) -
'
④ ca ,
e .
-
- 9
I
II. Mark one pair of events that are concurrent with each other.
P0
P1
P2
P3
iII. Identify an event at process P2 that happens before an event at P1.
P0
P1
P2
P3
0
O
IV. Mark all Lamport timestamps on this figure for all events.
All processes start with zero timestamps.
P0
P1
P2
P3
o
K B 4 5 6
A
70
3 4 5
72
A 3 6
Oak 45
O •
3 4 56
V. Mark all vector timestamps on this figure for all events.
All processes start with zero timestamps.
P0
P1
P2
P3
[4%1,0] ↳ 0,40 ) [3,011,904*441,0] [5,448 [6,4/1,0]
[9%0]
[ Oglio ,0] [0,3%0] [0,9019 [3,6%0]
[0,0/90] [ 0,20,0] [94/90]
[ o , 2,03 [0,9307 [ 3,4503 [ 3,46 ;D
↳ 998
Go , 1,03 Co , e. 4,03 C344,07
[99%0]
Cop ,o,D Cos9232132 Cop ,2 , [932,43 [ 93,45 )
VI. Mark all Lamport timestamps on this figure for all events.
All processes start with zero timestamps.
P0
P1
P2
P3
•
45 6 7 8 9
00
"
7- 10
O
6 8
O
23 4 89 9 10
VII. Mark all vector timestamps on this figure for all events.
All processes start with zero timestamps.
P0
P1
P2
P3
[ go ,o,o)
['
'
'
' " D G " " 'D C 35923 [940,336,1%3] [6,1%3]
[0,4%3
coiled
aim airbed
[90,903 amid G. ii. D
[990 'D
[ on , Coming [ on .gs) G 's Gibbs ) [5%2,6] [6,447)
P0
P1
P2
a
Marker Message
Regular Message c c
b
I. Chandy-Lamport Global Snapshots Algorithm
• Mark the entire global snapshot collected.
soit si Duplicate Co2 co coffee?dcI easy Record
, I
I avail :c
V a
→
IT Duplicate marker
Ago .µ code
P2 is initiator marker
. Record local state 52
Tops recording 802
• Sends od markers
• Turn on recording on channels Coz , Cry
Sisco , =L 95222242=2
Sos 90=2 Sifu =L
see # =L
Sets , =L
II. Chandy-Lamport Global Snapshots Algorithm
• Mark the entire global snapshot collected.
P0
P1
P2
a
Marker Message
Regular Message c c
b
c d
e
f
& is
go ,
Record 900 at
deg
ps2
,
Record
bcoi-h7@uoiiy9urlicdI.L
's
t
.
p tourism
S2 Cox g. plicate
Go - Sd •
Record
Ci27c02
SI = coz =L , Ce ,
- L )
so -
-
eco = ed gin - L
S 1=71--4 )
III. Mark all Lamport timestamps for application messages
on this figure for all events.
All Lamport timestamps start from zero.
P0
P1
P2
a
Marker Message
Regular Message c c
b
c d
e
f
O
I 3 6
49
O
2 3
⑨
I 2 4 5 G
IV. Mark all vector timestamps for application messages
on this figure for all events.
All vector timetstamps start from zeroes.
P0
P1
P2
a
Marker Message
Regular Message c c
b
c d
e
f
[ go ,o) C " " D C 2,923 [ 3,443
[ 5h03 [1,323%0] Glib
[ 999
fo ,o,D [ 0,923 Grid C '
is [ 1.3.53
Problem Set 2: Time and Ordering, Snapshots
1. A clock is reading 12:33:57.0 (hr:min:sec) when it is discovered to be 3
seconds fast. Explain why it is undesirable to set it back to the right time at
that point and show (numerically) how it should be adjusted so as to be
correct after 6 seconds has elapsed.
It will be undesirable to set the clock back to the right time as we will have
stored time events in the future in our log which will cause the system to
malfunction. We will fix this by slowing down our clock. To fix the 3 second
drift in 6 seconds, we will slow down our clock by a factor of
½(Terror+6seconds-12:33:57:0)+12:33:57:0.
2. A client attempts to synchronize with a time server. It records the round-trip
times and timestamps returned by the server in the table below. Which of
the times in the table below should it use to set its clock and why? What
shouldit set its clock to? What is the estimated accuracy w.r.t to server’s
clock? If minimum time to send or receive a message from the server is
known to be at least 8ms, does your answer change? Why?
Round-trip Time (ms) Server Clock
(hh:mm:ss)
24 12:43:33.456
28 12:43:35.235
22 12:43:36.124
The client should use the time corresponding to the minimum round trip time of 22
seconds.
The error for the case with no network latency will be (22-0-0)/2 = 11ms according to
Christian’s algorithm. The time set by the algorithm will be 12:43:36:124 + 0.011 =
12:43:36:135
The Error will be at most (22-8-8)/2ms = 3ms with Christian’s algorithm.
The time set by the algorithm will be 12:43:36.124 + {(22 + 8 – 8)/2 ms}
= 12:43:36.124 + 0.011 = 12:43:36.135
While the overall time remains the same, with the server latency being 8
seconds, the error is bounded to 3ms while the error for a network with no
latency is at most 11ms. This is because as the time duration for
measuring intervals decreases (as we go towards no latency), measuring
time gets harder.
3. If in problem 2 if it is required to sync to within 1ms of the server, is that
feasible? Explain your answer.
To synchronize a clock within ± 1 ms it is necessary to obtain a round-trip time of no
more than 18 ms if the network latency is 8 ms. (RTT - 8 – 8 = 1, RTT = 18ms) It is
possible to obtain round-trip time of 18ms, but it may be improbable that such a time
could be found. The file server risks failing to synchronize over a long period, when it
could synchronize with a lower accuracy.
4. By considering a chain of zero or more messages connecting events e and
e′, and using induction, show that e→e′ implies L(e) <= L(e'), where L(e)
is the Lamport timestamp of event e.
Step 1: The event e1 - e2 will be true if there is a direct connection between
the two nodes and will imply L(e1) <= L(e2) (Will be true as the event e1 will
send its value (1 in this case) which will be incremented by e2)
Step 2: Let e1 - e2 - … - ek-2 - ek-1-ek imply L(e1) <= L(e2) <= … <= L(ek-2)
<= L(ek-1) <= L(ek) be true for k causal events
Step 3: To Prove: L(e1) <= …. <= L(en) will be true for an event n = k+1 that is
en-en+1 if there is a causal relationship between them
Let there be a chain of events connection e and e’ such that e = e1 and e’ = en.
As these are connected, e1-en and from the Induction hypothesis, L(e1) will
be less than L(en). Hence L(e) will be less than L(e’).
5. Show that Vj[i] <= Vi[i] where Vi is vector clock at process i.
Lets us assume that Vj[i] is strictly greater than Vi[i]. If this is true then every
connection from j to i will increase i’s value in the vector array for Vi. This
will also imply that in the beginning state, Pj will have detected an event ei
before Pi itself but this is not possible as there is no way for Pj to know the
events that occur at Process i without process i without process i recording
it. This will also not follow the property of vector clocks that state that “If ej
occurred before pj recorded its state, then ei must have occurred before pi
recorded its state”. As this will not be possible, our assumption must be
wrong and hence Vj[i] must always be less than Vi[i].
6. In a similar fashion to 4, show that e→e′ implies V(e) <=V(e')
Step 1: e1-e2will imply V(e1) <= V(e2) as e1 will be connected to e2 and hence
will at least have all the values of the vector smaller than itself from e1 and
will have all the values greater than e1’s vector array its existing vector array
(e2)
Step 2: Let e1-ek imply V(e1) <= V(ek) be true for all k (Assuming there is a
chain of events leading from e1 to ek)
Step 3: To prove: V(e1) <= … <=V(en) where n = k+1, e1 = e and en=e’.
Let the events e1 be connected to en by a series of events such V(e1) <= V(ek)
by the induction hypothesis. As ek is connected directly to ek+1, ek-ek+1 and
V(ek) <= V(ek+1) is true. This will imply that V(e1)<= V(ek+1) and as k+1 = n,
e1-en and V(e1) <= V(en) (by the Induction Hypothesis).
7. Using result from 5, show that if e and e′ are concurrent that neither V(e)<=
V(e') nor V(e’)<= V(e). Thus show that if V(e) < V(e') then e→e’.
Let e and e’ be concurrent and let e occur at process i and e’ occur at process
j . Because these events are concurrent, none of the messages sent from the
I’th process sent after event e (inclusive) will have sent its timestamp to
process j by the time e’ occurs at pj, and vice versa. We know that the source
increments its value in the vector clock by 1 before sending a message and
the receiving event increments its value by 1 only after receiving the event
(and other entries if their timestamps are greater than the receiving events),
it follows that V j [k] < V i[k] and Vi[j] < Vj[j] and therefore that neither V(e)
<= V(e’) nor V(e’) <= V(e).
This can only be possible when the two events V(e) < V(e’) are causal. Hence
it is proved that e - e’.
P3
I. Mark one pair of events that are concurrent with each other.
P3
II. Mark one pair of events that are concurrent with each other.
P0
P1
P2
P3
P0
P1
P2
iII. Identify an
event at process
P2 that happens before an event at P1.
P3
P0
P1
P2
P3
IV. Mark all Lamport timestamps on this figure for all
events.All processes start with zero timestamps.
P3
V. Mark all vector timestamps on this figure for all
events.All processes start with zero timestamps.
P0
P1
P2
P3
VI. Mark all Lamport timestamps on this figure for all
events.All processes start with zero timestamps.
P0
P1
P2
P3
P0
P1
P2
P3
VII. Mark all vector timestamps on this figure for all
events.All processes start with zero timestamps.
c
Regular Message c
I. Chandy-Lamport Global Snapshots Algorithm•
Mark the entire global snapshot collected.
P0
P1
P2
c
Regular Message c
II. Chandy-Lamport Global Snapshots Algorithm•
Mark the entire global snapshot collected.
P0
P1
P2
a
Marker Message
b
c
Regular Message c
III. Mark all Lamport timestamps for application
messages on this figure for all events.
All Lamport timestamps start from zero.
P0
P1
P2
a
Marker Message
b
c d
e
f
c
Regular Message c
IV. Mark all vector timestamps for application
messages on this figure for all events.
All vector timetstamps start from zeroes.
P0
P1
P2
a
Marker Message
b
c d
e
f
c
Regular Message c
P0
P1
P2
a
Marker Message
b
c d
e
f
1 file (766.0bytes)
