Warning:
JavaScript is turned OFF. None of the links on this page will work until it is reactivated.
If you need help turning JavaScript On, click here.
This Concept Map, created with IHMC CmapTools, has information related to: ch 11 time, Messages exchanged between a pair of NTP peers All modes use UDP Each message bears timestamps of recent events: Local times of Send and Receive of previous message Local times of Send of current message Recipient notes the time of receipt Ti ( we have Ti-3, Ti-2, Ti-1, Ti) In symmetric mode there can be a non-negligible delay between messages with Accuracy of NTP For each pair of messages between two servers, NTP estimates an offset o, between the two clocks and a delay di (total time for the two messages, which take t and t’) Ti-2 = Ti-3 + t + o and Ti = Ti-1 + t’ - o This gives us (by adding the equations) : di = t + t’ = Ti-2 - Ti-3 + Ti - Ti-1 Also (by subtracting the equations) o = oi + (t’ - t )/2 where oi = (Ti-2 - Ti-3 + Ti-1 - Ti)/2 Using the fact that t, t’ɬ it can be shown that oi - di /2 ≤ o ≤ oi + di /2 . Thus oi is an estimate of the offset and di is a measure of the accuracy NTP servers filter pairs <oi, di>, estimating reliability from variation, allowing them to select peers Accuracy of 10s of millisecs over Internet paths (1 on LANs), Computer clocks and timing events Each computer in a DS has its own internal clock used by local processes to obtain the value of the current time processes on different computers can timestamp their events but clocks on different computers may give different times computer clocks drift from perfect time and their drift rates differ from one another. clock drift rate: the relative amount that a computer clock differs from a perfect clock Even if clocks on all computers in a DS are set to the same time, their clocks will eventually vary quite significantly unless corrections are applied ???? Skew between computer clocks in a distributed system Computer clocks are not generally in perfect agreement Skew: the difference between the times on two clocks (at any instant) Computer clocks are subject to clock drift (they count time at different rates) Clock drift rate: the difference per unit of time from some ideal reference clock Ordinary quartz clocks drift by about 1 sec in 11-12 days. (10-6 secs/sec). High precision quartz clocks drift rate is about 10-7 or 10-8 secs/sec, Coordinated Universal Time (UTC) International Atomic Time is based on very accurate physical clocks (drift rate 10-13) UTC is an international standard for time keeping It is based on atomic time, but occasionally adjusted to astronomical time It is broadcast from radio stations on land and satellite (e.g. GPS) Computers with receivers can synchronize their clocks with these timing signals Signals from land-based stations are accurate to about 0.1-10 millisecond Signals from GPS are accurate to about 1 microsecond in which Clock correctness A hardware clock, H is said to be correct if its drift rate is within a bound > 0. (e.g. 10-6 secs/ sec) This means that the error in measuring the interval between real times t and t’ is bounded: (1 - (t’ - t) ≤ H(t’) - H(t) ≤ (1 + (t’ - t) (where t’>t) Which forbids jumps in time readings of hardware clocks Weaker condition of monotonicity t' > t C(t’) > C(t) e.g. required by Unix make can achieve monotonicity with a hardware clock that runs fast by adjusting the values of a Ci(t)= aHi(t) + a faulty clock is one that does not obey its correctness condition crash failure - a clock stops ticking arbitrary failure - any other failure e.g. jumps in time, NTP - synchronisation of servers The synchronization subnet can reconfigure if failures occur, e.g. a primary that loses its UTC source can become a secondary a secondary that loses its primary can use another primary Modes of synchronization: Multicast A server within a high speed LAN multicasts time to others which set clocks assuming some delay (not very accurate) Procedure call A server accepts requests from other computers (like Cristian's algorithm). Higher accuracy. Useful if no hardware multicast. Symmetric Pairs of servers exchange messages containing time information Used where very high accuracies are needed (e.g. for higher levels) also Messages exchanged between a pair of NTP peers All modes use UDP Each message bears timestamps of recent events: Local times of Send and Receive of previous message Local times of Send of current message Recipient notes the time of receipt Ti ( we have Ti-3, Ti-2, Ti-1, Ti) In symmetric mode there can be a non-negligible delay between messages, Skew between computer clocks in a distributed system Computer clocks are not generally in perfect agreement Skew: the difference between the times on two clocks (at any instant) Computer clocks are subject to clock drift (they count time at different rates) Clock drift rate: the difference per unit of time from some ideal reference clock Ordinary quartz clocks drift by about 1 sec in 11-12 days. (10-6 secs/sec). High precision quartz clocks drift rate is about 10-7 or 10-8 secs/sec and Coordinated Universal Time (UTC) International Atomic Time is based on very accurate physical clocks (drift rate 10-13) UTC is an international standard for time keeping It is based on atomic time, but occasionally adjusted to astronomical time It is broadcast from radio stations on land and satellite (e.g. GPS) Computers with receivers can synchronize their clocks with these timing signals Signals from land-based stations are accurate to about 0.1-10 millisecond Signals from GPS are accurate to about 1 microsecond, Berkeley algorithm Cristian’s algorithm - a single time server might fail, so they suggest the use of a group of synchronized servers it does not deal with faulty servers Berkeley algorithm (also 1989) An algorithm for internal synchronization of a group of computers A master polls to collect clock values from the others (slaves) The master uses round trip times to estimate the slaves’ clock values It takes an average (eliminating any above some average round trip time or with faulty clocks) It sends the required adjustment to the slaves (better than sending the time which depends on the round trip time) Measurements 15 computers, clock synchronization 20-25 millisecs drift rate < 2x10-5 If master fails, can elect a new master to take over (not in bounded time) ???? NTP - synchronisation of servers The synchronization subnet can reconfigure if failures occur, e.g. a primary that loses its UTC source can become a secondary a secondary that loses its primary can use another primary Modes of synchronization: Multicast A server within a high speed LAN multicasts time to others which set clocks assuming some delay (not very accurate) Procedure call A server accepts requests from other computers (like Cristian's algorithm). Higher accuracy. Useful if no hardware multicast. Symmetric Pairs of servers exchange messages containing time information Used where very high accuracies are needed (e.g. for higher levels), 11.3.1 Synchronization in a synchronous system a synchronous distributed system is one in which the following bounds are defined (ch. 2 p. 50): the time to execute each step of a process has known lower and upper bounds each message transmitted over a channel is received within a known bounded time each process has a local clock whose drift rate from real time has a known bound but Christian's Method Cristian’s method (1989) for an asynchronous system A time server S receives signals from a UTC source Process p requests time in mr and receives t in mt from S p sets its clock to t + Tround/2 Accuracy ± (Tround/2 - min) : because the earliest time S puts t in message mt is min after p sent mr. the latest time was min before mt arrived at p the time by S’s clock when mt arrives is in the range [t+min, t + Tround - min], We need to measure time accurately: to know the time an event occurred at a computer to do this we need to synchronize its clock with an authoritative external clock Algorithms for clock synchronization useful for concurrency control based on timestamp ordering authenticity of requests e.g. in Kerberos There is no global clock in a distributed system this chapter discusses clock accuracy and synchronisation Logical time is an alternative It gives ordering of events - also useful for consistency of replicated data also Computer clocks and timing events Each computer in a DS has its own internal clock used by local processes to obtain the value of the current time processes on different computers can timestamp their events but clocks on different computers may give different times computer clocks drift from perfect time and their drift rates differ from one another. clock drift rate: the relative amount that a computer clock differs from a perfect clock Even if clocks on all computers in a DS are set to the same time, their clocks will eventually vary quite significantly unless corrections are applied, Clock correctness A hardware clock, H is said to be correct if its drift rate is within a bound > 0. (e.g. 10-6 secs/ sec) This means that the error in measuring the interval between real times t and t’ is bounded: (1 - (t’ - t) ≤ H(t’) - H(t) ≤ (1 + (t’ - t) (where t’>t) Which forbids jumps in time readings of hardware clocks Weaker condition of monotonicity t' > t C(t’) > C(t) e.g. required by Unix make can achieve monotonicity with a hardware clock that runs fast by adjusting the values of a Ci(t)= aHi(t) + a faulty clock is one that does not obey its correctness condition crash failure - a clock stops ticking arbitrary failure - any other failure e.g. jumps in time and 11.3.1 Synchronization in a synchronous system a synchronous distributed system is one in which the following bounds are defined (ch. 2 p. 50): the time to execute each step of a process has known lower and upper bounds each message transmitted over a channel is received within a known bounded time each process has a local clock whose drift rate from real time has a known bound, Christian's Method Cristian’s method (1989) for an asynchronous system A time server S receives signals from a UTC source Process p requests time in mr and receives t in mt from S p sets its clock to t + Tround/2 Accuracy ± (Tround/2 - min) : because the earliest time S puts t in message mt is min after p sent mr. the latest time was min before mt arrived at p the time by S’s clock when mt arrives is in the range [t+min, t + Tround - min] and Berkeley algorithm Cristian’s algorithm - a single time server might fail, so they suggest the use of a group of synchronized servers it does not deal with faulty servers Berkeley algorithm (also 1989) An algorithm for internal synchronization of a group of computers A master polls to collect clock values from the others (slaves) The master uses round trip times to estimate the slaves’ clock values It takes an average (eliminating any above some average round trip time or with faulty clocks) It sends the required adjustment to the slaves (better than sending the time which depends on the round trip time) Measurements 15 computers, clock synchronization 20-25 millisecs drift rate < 2x10-5 If master fails, can elect a new master to take over (not in bounded time)