Computer Science 425 Distributed SystemsWhy synchronization?Basics – Processes and EventsPhysical Clocks & SynchronizationSynchronizing Physical ClocksClock Synchronization Using a Time ServerCristian’s AlgorithmCristian’s Algorithm (2)Berkeley AlgorithmThe Network Time Protocol (NTP)Messages Exchanged Between a Pair of NTP Peers (“Connected Servers”)Theoretical Base for NTPLogical ClocksEvents Occurring at Three ProcessesLamport TimestampsSpot the MistakeCorrected Example: Lamport Logical TimeOne thing to Notice …Vector Logical ClocksVector TimestampsExample: Vector Logical TimeComparing Vector TimestampsSummary 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-1Lecture 2-1Computer Science 425Distributed SystemsComputer Science 425Distributed SystemsLecture 2Time & SynchronizationReading: 11.1-11.4 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-2Lecture 2-2Why synchronization?Why synchronization?•You want to catch the 10 Gold West bus at the Illini Union stop at 6.05 pm, but your watch is off by 5 minutes–What if your watch is Fast by 5 minutes?–What if your watch is Late by 5 minutes?•Synchronization is required for –Fairness–Correctness 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-3Lecture 2-3 A Distributed System (DS) consists of a number of processes. Each process has a state (values of variables). Each process takes actions to change its state, which may be an instruction or a communication action (send, receive). An event is the occurrence of an action. Each process has a local clock -- events within a process can be assigned timestamps, and thus ordered.But – in a DS, we also need to know the time order of events across different processes.Clocks across processes are not synchronized in a DS(unlike in a multiprocessor/parallel system, where they are). So…1. Process clocks can be different2. Need algorithms for either (a) time synchronization, or (b) for telling which event happened before whichBasics – Processes and Events Basics – Processes and Events 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-4Lecture 2-4In a DS, each process has its own clock.Clock Skew versus DriftClock Skew = Relative Difference in clock values of two processesClock Drift = Relative Difference in clock frequencies (rates) of two processesA non-zero clock drift will cause skew to continuously increase. Maximum Drift Rate (MDR) of a clock is defined relative to Coordinated Universal Time (UTC)MDR of a process depends on the environment.Max drift rate between two clocks with similar MDR is 2 * MDR Physical Clocks & Synchronization Physical Clocks & Synchronization Max-Synch-Interval = (MaxAcceptableSkew—CurrentSkew) / (MDR * 2) 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-5Lecture 2-5Synchronizing Physical ClocksSynchronizing Physical Clocks•Ci(t): the reading of the software clock at process i when the real time is t.•External synchronization: For a synchronization bound D>0, and for source S of UTC time, for i=1,2,...,N and for all real times t in I. Clocks Ci are accurate to within the bound D.•Internal synchronization: For a synchronization bound D>0, for i, j=1,2,...,N and for all real times t in I. Clocks Ci agree within the bound D.•External synchronization with D Internal synchronization with 2D,)()( DtCtSiDtCtCji )()( 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-6Lecture 2-6Clock Synchronization Using a Time ServerClock Synchronization Using a Time ServermrmtpTime server,S 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-7Lecture 2-7 Uses a time server to synchronize clocks Time server keeps the reference time A client asks the time server for time, the server responds with its current time, and the client uses the value T in the response message to set clockBut round-trip time introduces an error…Cristian’s Algorithm Cristian’s Algorithm Let RTT = response-received-time – request-sent-time (measurable at client)Also, suppose we know (1) the minimum value min of the client-server one-way transmission time(2) that the server timestamped the message at the last possible instant before sending it backThen, the actual time could be between [T+min,T+RTT— min] 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-8Lecture 2-8Client sets its clock to halfway between T+min and T+RTT— min i.e., at T+RTT/2 Expected (i.e., average) skew in client clock time will be = (RTT/2 – min)Can increase clock value, but should never decrease it – Why?Can adjust speed of clock too (take multiple readings) – either up or down is ok. For unusually long RTTs, repeat the time request For non-uniform RTTs, use weighted averageCristian’s Algorithm (2) Cristian’s Algorithm (2) avg-clock-error0 = local-clock-erroravg-clock-errorn = (Wn * local-clock-error) + (1 – Wn) * local-clock-errorn-1 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-9Lecture 2-9 Uses an elected master process to synchronize among clients, without the presence of a time server The elected master pools or broadcasts to all machines requesting for their time, adjusts times received for RTT & latency, averages times, and tells each machine how to adjust.Multiple leaders are used. Averaging client’s clocks may cause the entire system to drift away from UTC over timeFailure of the master requires some time for re-election, so accuracy cannot be guaranteedBerkeley Algorithm Berkeley Algorithm 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-10Lecture 2-10Secondry servers, synched by the primary serverThe Network Time Protocol (NTP) The Network Time Protocol (NTP) Primary server, direct synch.Strata 3, synched by the secondary serversUses a network of time servers to synchronize all processes on a network. Time servers are connected by a synchron- ization subnet tree. The root is adjusted directly . Each node synchronizes its children nodes. 122233333 3 2001, M. T. Harandi and J. Hou (modified I. Gupta) Lecture 2-11Lecture 2-11Messages Exchanged Between a Pair of NTP Peers (“Connected Servers”)Messages Exchanged Between a Pair of NTP Peers (“Connected Servers”)TiTi-1Ti-2Ti- 3Server BServer ATimem m'TimeEach message bears timestamps of recent message events: the local timewhen the
View Full Document
Unlocking...