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