Module 12 - Clocks

Question 1

Lack of ________ among clocks of different machines

leads to _______, particularly regarding the order of _______

Answer 1

synchronization
confusion
events

Question 2

What is the Roman Calendar?

Answer 2

• lunar calendar, based on moon phases, months of 29 or 30 days
• initially 10 months per year = 304 days + 61 winter days unaccounted for

Question 3

What is the Julian Calendar?

Answer 3

• Named after Julius Caesar
• First solar calendar, based on Earth’s rotation around the sun
• Leap year was initially every three years, then every four years (too many!)
• Not aligned with astronomical events like equinoxes and solstices

Question 4

What is the Gregorian Calendar?

Answer 4

• Named after Pope Gregory, 1582
• Leap years calculated more carefully
• Adopted by US, Canada, Europe
• Accuracy oof 1 day in 7700 years

Question 5

How does solar time measure time?

Answer 5

• Measures based on a transit of the sun, which occurs when the sun reaches the highest point of the day

Question 6

What is a “solar day”?

Answer 6

The time interval between two consecutive transits of the sun. It is NOT constant, and can vary by 16 minutes from the mean depending on the season

Question 7

What is TAI (Temps Atomique International)?

Answer 7

An international time scale based on an average of multiple Cesium 133 atomic clocks

Question 8

What is UTC (Universal Coordinated Time)?

Answer 8

Based on TAI and adjusted using leap seconds whenever the discrepancy grows to 800ms. Synchronized with earth’s rotation and currently behind TAI by tens of seconds

Question 9

What was the Hafele-Keating experiment, conducted in 1971?

Answer 9

• Four atomic clocks were flown around the world in opposite directions and then compared against clocks that remained “stationary” on the ground.
• Eastbound and westbound clocks both gained
  time due to gravitational time dilation.
• The eastbound clock lost time due to kinematic
  time dilation, while the westbound clock
  gained time.
• In the end, clocks flown in opposite directions
  differed by more than 200ns, in agreement
  with theoretical predictions.

Question 10

Suppose we have a clock C, and reference “t” (such as UTC), and C(t) denotes the value of clock C at reference time “t”.

What do the following terms mean:

1. Clock Skew of C relative to “t”
2. Offset of C relative to “t”
3. Maximum drift rate of C

Answer 10

1. Clock skew of C relative to “t” is dC/dt - 1
2. Offset of C relative to “t” is C(t) - t
3. The maximum drift rate of C is a constant ρ such that:
   1 - ρ <= dC/dt <= 1 + ρ

Question 11

In NTP, what is the formula for the offset (θ) of B relative to A?

Answer 11

θ = (T2 - T1)/2 + (T3 - T4)/2

Make sure all time values are relative to the same clock

Question 12

In NTP, what is the formula for the (one-way) network delay between A and B?

Answer 12

δ = (T4 - T1)/2 - (T3 - T2)/2

Make sure all time values are relative to the same clock

Question 13

What does NTP use theta, and delta values for?

What is the precision of an NTP time measurement?

Answer 13

• The minimum value of δ is the best estimate of the delay
• θ is the most reliable estimate of the offset

Precision is generally measured in tens of milliseconds

Question 14

What is NTP used for?

Answer 14

NTP is a tool that runs a network request between a local process (A) and a remote process (B), used to calculate:

• Offset (θ) between clocks on A and B
• One way network delay (δ) for a request between A and B

NTP can be used to synchronous local clocks with remote clocks

Question 15

What does T1, T2, T3, and T4 denote in NTP?

Answer 15

T1 - time at which local process (A) initiates network request
T2 - time at which remote process (B) receives network request
T3 - time at which remote process (B) initiates network response
T4 - time at which local process (A) receives network response

Question 16

Explain the concept of stratums with respect to NTP.

Answer 16

Statum is a validity of a clock. A reference clock such as an atomic clock is said to operate
at stratum 0. A server with such a clock is a stratum 1
server.

Question 17

In NTP, for what case does host A adjust its clock to host B?
What happens to the stratum levels in this case?

Answer 17

Host A will only adjust its clock if its own stratum level its higher than that of B.

If A does adjust its time, then A’s stratum level = B’s stratum level +1 (one more than B’s)

Question 18

What is the protocol used to achieve better accuracy than NTP? What does it leverage?

Answer 18

Precision Time Protocol (PTP) achieves accuracy of less than 100ns. Leverages hardware timestamping

Question 19

For NTP, clocks must be adjusted (by _____ or _____ ) carefully to ensure that does not appear to flow ______

Answer 19

slewing
stepping
backward

Question 20

What is Lamport’s clocks algorithm used for?

Answer 20

Lamport’s clocks algorithm corrects the clocks of unsynchronized processes, ensuring that each process is consistent with the “happens before relation”

Question 21

In Lamport’s Clocks, there are numerous ______ with local ______ running at different ______

Answer 21

processes
clocks
frequencies/speeds

Question 22

What is the motivation behind Lamport’s clocks?

Answer 22

Numerous processes running on un-synchronized clocks, can still agree on a meaningful partial order of events

Question 23

In Lamport’s clocks, what is the “happens before” property for events “a” and “b”?

Use “→” to denote happens before

Answer 23

Happens before is the transitive closure of:

1. If “a” and “b” are events in the same process, and “a” occurs before “b”, then a→b is true
2. If “a” is the event of a message being sent by one process, and “b” is the event of the message being received by another process, then a→b is also true

Question 24

Lamport Clocks. What can we say about events “x” and “y” if both
x→y and y→x are true

Answer 24

then events “x” and “y” are concurrent

Question 25

Lamport Clocks. You have two events “a” and “b”, and a→b. Let C(a) and C(b) denote the logical times of events “a” and “b” respectively

What can you say about C(a) and C(b)?

If C(a) < C(b), can you guarantee that a→b? explain

Answer 25

• If a→b, then C(a) < C(b) must be true

- C(a) < C(b) does NOT guarantee that a→b. Their clocks could be out of sync

Question 26

Describe the Lamport Clock algorithm step-by-step for updating counter C_i at Process P_i

Note that C_i is the logical time at process P_i

Answer 26

1. Process P_i increases its own counter C_i
2. When P_i sends a message “m” to P_j, it tags “m” with a timestamp ts(m) equal to the time C_i after incrementing C_i
3. Upon the receipt of a message “m”, process P_j adjusts its own local counter C_j = max{C_j, ts(m)}, then increments C_j before delivering the message to the application

Question 27

What do vector clocks represent?

Answer 27

• Vector clocks represent logical time just like Lamport Clocks
• They are represented as a vector which is held by each process

Question 28

How are vector clocks constructed? What properties do they hold?

Answer 28

Vector clocks are constructed by letting each process P_i maintain a vector VC, with these 2 properties (for each process, VC_x is x’s vector):

1. VC_i[i] is the number of events that have occurred so far at P_i. It is the local logical clock at process P_i
2. If VC_i[j] = k, then P_i knows that k events have occurred at P_j. It is P_i’s knowledge of the local time at P_j

Question 29

What does the term “knows” mean in vector clocks when defining what a process’s vector holds?

Answer 29

“knows” means that one process leaned about the state of another process by receiving a message from it, either directly or indirectly through another process

Question 30

Describe the Vector Clock algorithm step-by-step for updating a vector clock at process P_i

Answer 30

1. Before executing an event, process P_i increments its own counter by assigning VC_i[i] = VC_i[i] + 1
2. When process P_i sends a message “m” to P_j , it sets m’s (vector) timestamp ts(m) equal to VC_i after incrementing VC_i[i]
3. Upon the receipt of a message “m”, process P_j adjusts its own vector by setting
   VC_j[k] = max{ VC_j[k], ts(m)[k] }
   for each k, and then increments its own VC_j[j]

Question 31

Vector clocks provide a complete characterization of causality among pairs of events. Given two vector clocks VC_i[…] and VC_j[…] representing events “i” and “j” respectively, under what condition does:

1. i happen before j
2. j happen before i
3. i and j are concurrent

Answer 31

1. “i” happens before “j” if VC_i[k] <= VC_j[k] for all elements k, and VC_i[k’] < VC_i[k’] for at least one element k’
2. “j” happens before “i” if VC_j[k] <= VC_i[k] for all elements k, and VC_j[k’] < VC_i[k’] for at least one element k’
3. Neither 1. or 2. are satisfied