Module 12 - Clocks Flashcards
Lack of ________ among clocks of different machines
leads to _______, particularly regarding the order of _______
synchronization
confusion
events
What is the Roman Calendar?
- lunar calendar, based on moon phases, months of 29 or 30 days
- initially 10 months per year = 304 days + 61 winter days unaccounted for
What is the Julian Calendar?
- 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
What is the Gregorian Calendar?
- Named after Pope Gregory, 1582
- Leap years calculated more carefully
- Adopted by US, Canada, Europe
- Accuracy oof 1 day in 7700 years
How does solar time measure time?
- Measures based on a transit of the sun, which occurs when the sun reaches the highest point of the day
What is a “solar day”?
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
What is TAI (Temps Atomique International)?
An international time scale based on an average of multiple Cesium 133 atomic clocks
What is UTC (Universal Coordinated Time)?
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
What was the Hafele-Keating experiment, conducted in 1971?
- 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.
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:
- Clock Skew of C relative to “t”
- Offset of C relative to “t”
- Maximum drift rate of C
- Clock skew of C relative to “t” is dC/dt - 1
- Offset of C relative to “t” is C(t) - t
- The maximum drift rate of C is a constant ρ such that:
1 - ρ <= dC/dt <= 1 + ρ
In NTP, what is the formula for the offset (θ) of B relative to A?
θ = (T2 - T1)/2 + (T3 - T4)/2
Make sure all time values are relative to the same clock
In NTP, what is the formula for the (one-way) network delay between A and B?
δ = (T4 - T1)/2 - (T3 - T2)/2
Make sure all time values are relative to the same clock
What does NTP use theta, and delta values for?
What is the precision of an NTP time measurement?
- 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
What is NTP used for?
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
What does T1, T2, T3, and T4 denote in NTP?
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
Explain the concept of stratums with respect to NTP.
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.
In NTP, for what case does host A adjust its clock to host B?
What happens to the stratum levels in this case?
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)
What is the protocol used to achieve better accuracy than NTP? What does it leverage?
Precision Time Protocol (PTP) achieves accuracy of less than 100ns. Leverages hardware timestamping
For NTP, clocks must be adjusted (by _____ or _____ ) carefully to ensure that does not appear to flow ______
slewing
stepping
backward
What is Lamport’s clocks algorithm used for?
Lamport’s clocks algorithm corrects the clocks of unsynchronized processes, ensuring that each process is consistent with the “happens before relation”
In Lamport’s Clocks, there are numerous ______ with local ______ running at different ______
processes
clocks
frequencies/speeds
What is the motivation behind Lamport’s clocks?
Numerous processes running on un-synchronized clocks, can still agree on a meaningful partial order of events
In Lamport’s clocks, what is the “happens before” property for events “a” and “b”?
Use “→” to denote happens before
Happens before is the transitive closure of:
- If “a” and “b” are events in the same process, and “a” occurs before “b”, then a→b is true
- 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
Lamport Clocks. What can we say about events “x” and “y” if both
x→y and y→x are true
then events “x” and “y” are concurrent
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
- 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
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
- Process P_i increases its own counter C_i
- 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
- 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
What do vector clocks represent?
- Vector clocks represent logical time just like Lamport Clocks
- They are represented as a vector which is held by each process
How are vector clocks constructed? What properties do they hold?
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):
- 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
- 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
What does the term “knows” mean in vector clocks when defining what a process’s vector holds?
“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
Describe the Vector Clock algorithm step-by-step for updating a vector clock at process P_i
- Before executing an event, process P_i increments its own counter by assigning VC_i[i] = VC_i[i] + 1
- 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]
- 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]
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:
- i happen before j
- j happen before i
- i and j are concurrent
- “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’
- “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’
- Neither 1. or 2. are satisfied
