Week 8 - Clocks Flashcards
(12 cards)
State the 2 types of clocks
Hardware
Logical
What is every clock subject to?
Drift rate
When talking about clocks, what does δ represent?
The skew of synchronisation
Two clocks are said to be δ-synchronised at clock time if and only if
The absolute difference in times are less than δ
A set of clocks are well-synchronised if an only if
Any two non-faulty nodes are δ-synchronised
How is clock synchronisation implemented?
Each node implements a virtual clock that has bounds for skew and drift rate
State the 2 requirements for a reliable time source
Time must be distributed frequently enough to bound skew
No node is required to implement too much adjustment in a single resynchronisation action
Two events are said to be concurrent if
A did not happen before B and B did not happen before A
Why don’t clock syntonisation algorithms with a single reliable time source work?
Clocks can not go backwards and shoot forwards in time, with a single RTS there will be latency between the request for the time being sent and the node receiving the response.
What is the Berkeley algorithm for clock synchronisation?
Time server polls each client periodically
Server computes the average
Server gives client an amount of time to gradually add or subtract from its clock
What are the three properties a convergence function must satisfy?
Monotonicity - Preserves the given order
Translation Invariance - Produces exactly the same response, regardless of how its input is shifted
Accuracy Preservation
State 4 examples of convergence functions
Egocentric average
Fast convergence algorithm
Fault-tolerant midpoint - The midpoint of the range spanned by the arguments after the highest k
and lowest k have been discarded
Fault-tolerant average - The average of arguments after the highest k and lowest k values have been discarded
