Clock SynchronizationIntroductionTopics of DiscussionDefinitionsWhat is clock synchronization?More DefinitionsModelLower Bound on AlgorithmAssumptionsCorrectnessKey step| Dpq -pq|/2ValidityFault-Tolerant Clock SynchronizationMore definitionsRatio of Faulty ProcessesByzantine Clock SynchronizationAlgorithm CONSlide 20More AssumptionsLegendHow the clocks are synchronizedAlgorithm COM(m)This reminds us of …Algorithm OM(1)AnalysisModifications for COM(1)Next ModificationAlgorithm OM(f), f>0Final ModificationMessage ComplexityOther algorithmsReferences1Clock SynchronizationRonilda Lacson, MD, SM2IntroductionAccurate reliable time is necessary for financial and legal transactions, transportation and distribution systems and many other applications involving distributed resourcesFor distributed internet applications, accuracy and reliability of a clock device is requiredA room temperature quartz oscillator may drift as much as a second per day3Topics of DiscussionDefinitionsLower bound on how closely clocks can be synchronized, even where clocks drift and with arbitrary faults – algorithm that shows this bound is tight2 more algorithms : interactive convergence and interactive consistency algorithmsLower bound on the number of processes for f failures4DefinitionsA hardware clock is a mechanism that provides time information to a processorIn a timed execution involving process pi, a hardware clock can be modeled as an increasing function HCiAt real time t, HCi(t) is available as part of pi’s transition function, but pi cannot change HCiHCi(t) = t5What is clock synchronization?Clock synchronization requires processes to bring their clocks close together by using communication between them6More DefinitionsThe adjusted clock of a process pi AC(t)i is a function of the hardware clock HC(t)i and a variable adji During the synchronization process, pi can change the value of adji and thus change the value of AC(t)i-synchronized clocks refer to achieving |AC(t)i-AC(t)j|   for all processes pi and pj after the algorithm terminates at time tf for all t  tf7ModelHC1adj1AC1p1HC2adj2AC2p2HCnadjnACnpnsend/receive channels…8Lower Bound on For every algorithm that achieves -synchronized clocks,  is at least (1-1/n) where  is the uncertainty in the message delay9AlgorithmCode for process piBeginstep(u)Send HCi to all qpDo foreverif u=message V from process q thenDIFF := V +  - HCiSUM := SUM + DIFFRESPONSES := RESPONSES + 1endifif RESPONSES = n-1 then exit endifEndstepBeginstep(u)Enddoadji := adji + SUM/nEndstep10AssumptionsNo faulty processesNo drift in the clock rates, thus the difference between the physical clocks of any 2 processes is a well-defined constantHC gives an accurate local time11CorrectnessAny admissible execution e of the algorithm synchronizes to within  where  = (1-1/n)This can be rewritten as  = (2(/2)+(n-2))/n12Key stepDpq = estimated difference between the physical clocks of p and q as estimated by qpq = the actual difference between the physical clocks of p and qShow |ACp(t)-ACq(t)|  (1-1/n)|ACp(t)-ACq(t)| = |(HCp(t) + adjp) – (HCq(t) + adjq)| = (1/n)|((rq - rp) – (Drq – Drp))|  (1/n)  |((rq - rp) – (Drq – Drp))|  (1/n) (2/2 + (n-2)) = (1-1/n)13| Dpq -pq|/2= |Cp(t) +  - Cq(t’) - pq|= |Cq(t) + pq +  - Cq(t’) - pq|= | + Cq(t) - Cq(t’)|= | - (t’-t)|  /2 Since  - /2  (t’-t)   + /214ValidityAnother key property worth noting is -validity. For any process p, there exists processes q and r such that HCq(t)-  ACp(t)  HCr(t)+ The algorithm is /2-valid15Fault-Tolerant Clock SynchronizationThe problem is still keeping real-time clocks synchronized in a distributed system when processes may failIn addition, consider the case where hardware clocks are subject to drift. Thus, adjusted clocks may drift apart as time elapses and periodic resynchronization is necessary16More definitionsBounded drift : For all times t1 and t2, t2>t1, there exists a positive constant  (the drift) such that (1+)-1(t2-t1)  HCi(t2) – HCi(t1)  (1+)(t2-t1)A hardware clock stays within a linear envelope of the real timeClock-agreement : There exists a constant  such that in every admissible timed execution, for all times t and all non-faulty processes pi and pj,|ACi(t) – ACj(t)|  Clock-validity : There exists a positive constant  such that in every admissible timed execution, for all times t and all non-faulty processor pi,(1+)-1(HCi(t)–HCi(0) )  ACi(t) – ACi(0)  (1+)(HCi(t)–HCi(0))17Ratio of Faulty ProcessesThere is no algorithm that satisfies clock agreement and clock validity if n  3f.18Byzantine Clock SynchronizationInteractive convergence algorithmInteractive consistency algorithm19Algorithm CONEach process reads the value of every process’s clock and sets its own clock to the average of these values – except that if it reads a clock value differing from its own by more than , then it replaces that value by its own clock’s value when forming the average.20Assumptionsn>3fClocks are initially synchronized and they are synchronized often enough so that no 2 non-faulty clocks differ by more than The error in reading other process’s clocks are not taken into account. The algorithm is asynchronous but it assumes immediate access to other process’s clocks. The algorithm does not guarantee clock-validity.21More AssumptionsSince clocks do not really read all other process’s clocks at exactly the same time, they record the difference between another clock’s value and its own. When a process p reads process q’s clock cq, it calculates the difference between cq and the value of its own clock at the same time cp, where qp=cq-cp. When computing the average, it takes qp = qp if |qp|, 0 otherwiseBy taking the average of the n values qp and adding it to its own clock value one gets the Adjusted Clock ACp22LegendЄ = maximum error in reading the clock difference qp = maximum error in the rates at which the clocks runR = length of time between resynchronizationsf = number of faulty processes = (6f+2) є + (3f+1)R = maximum difference between 2 non-faulty clocks = degree of synchronization maintained by this algorithm23How the clocks are synchronizedqp=cq-cpLet p and q be 2 non-faulty processes. If another process r is