UI CS 449 - Clock Synchronization
Course Cs 449-
Pages 4

Unformatted text preview:

1 Page: 1 © 2007 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 20 Clock Synchronization  Reading a Remote Clock – Paper by Flaviu Cristian (Cri89a) – “Probabilistic Clock Synchronization” – Method for reading remote clocks – Systems assumed to have random unbounded communication delays. – Approach does not guarantee that a processor can always read a remote clock. – A process can read the clock of another process with a given precision with a probability as close to 1 as desired. – After reading clock, the actual reading precision is known. Page: 2 © 2007 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 20 Clock Synchronization  The Problem of Reading Remote Times – Process P sends message (“time = ?”) to process Q. Process Q replies with message (“time = T”) – When P receives the message (“time = T”), what time is it in Qʼs clock? » i.e. what is the time displayed by Qʼs clock? » one can only try to derive an interval. – Definitions: » t = the real-time when P receives the message from Q. » CQ(t) = value displayed by Qʼs clock at real-time t » min = minimal delay to send message from P to Q or vice versa. » D = half the roundtrip delay measured by P. – Note: small letters/symbols indicate real times2 Page: 3 © 2007 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 20 Clock Synchronization – Let be the real time delays for sending and returning a message. » message path: » min + α accounts for message time from P to Q » min + β accounts for message time from Q to P – Let 2d be the real time roundtrip delay, then – We are interested in β, since this is the time that has passed since Q wrote its time in the message to P. How big is β? (min ),(min ), , + + !" # " #0P Q P! !2 2d = + +min! "Page: 4 © 2007 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 20 Clock Synchronization – Using we get since α could be 0. – Qʼs clock can run at any speed in [1 - ρ, 1 + ρ], where ρ is again the clock drift rate. – Thus substituting β from above 2 2d = + +min! "0 2 2! ! "#d minC t T TQ( ) [ (min )( ), (min )( )]! + + " + + +# $ # $1 1C tT T dQ( )[ (min)( ), (min min)( )]!+ " + + " +1 2 2 1# #3 Page: 5 © 2007 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 20 Clock Synchronization – Now, relate to the time measured in P. – Since Pʼs clock could have maximum drift we must assume – This is the smallest interval possible C t T T dQ( ) [ (min)( ), ( min)( )]! + " + " +1 2 1# #d D! +( )1")]1min()21(2),1min([)]1min()1(2),1min([)]1min)()1(2(),1min([)(2!!!!!!!!!+"++"+#+"++"+=+"++"+$DTTDTTDTTtCQρ2 is ignored Page: 6 © 2007 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 20 Clock Synchronization – Processor P cannot determine where in the interval Qʼs clock value is. – Suggestion: Estimate CQ by function – The actual error is – What is a good choice for best choice for function is to choose midpoint C T DQP( , )| ( , ) ( )|C T D C tQPQ!C T DQP( , )4 Page: 7 © 2007 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 20 Clock Synchronization – Midpoint – Thus » this is “Pʼs reading of Qʼs clock” – The maximal error this can cause is half the largest possible interval. 12121 2 1 2 12 1 1 2 1 21 2( min( ) ( ) min( ))( min( ) ( ))min ( )T T DT DT D+ ! + + + ! + =+ ! ! ! + + =! + +" " "" " "" "C T D T DQp( , ) min ( )! " + +# #1 2[ min( ), ( ) min( )]T T D+ ! + + ! +1 2 1 2 1" " "Page: 8 © 2007 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 20 Clock Synchronization – Thus largest possible error is: – Any other estimate choice leads to a bigger maximum error. 121212122 1 2 1 12 1 2 1 12 1 2 1 12 1 2 21 2[ ( ) min( ) ( min( ))][ ( ) min( ) min( )][ ( ) min( ) min( )][ ( ) min]( ) minT D TT D TDDD+ + ! + ! + ! =+ + ! + ! ! ! =+ ! + ! ! =+ ! =+ !" " "" " "" " """e D= + !( ) min1


View Full Document

UI CS 449 - Clock Synchronization

Course: Cs 449-
Pages: 4
Download Clock Synchronization
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Clock Synchronization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Clock Synchronization 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?