DOC PREVIEW
U of I CS 425 - Time & Synchronization

This preview shows page 1-2-3-24-25-26 out of 26 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 26 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS 425/ECE 428 Distributed SystemsAcknowledgementWhy synchronize clocks?Plan for todayTime SourcesTerminologySlide 7DefinitionsSynchronizing Physical ClocksInternal Synchronization: Berkeley AlgorithmExternal Synchronization: Cristian’s MethodSlide 12Slide 13The Network Time Protocol (NTP)Messages Exchanged Between a Pair of NTP Peers (Connected Servers)Theoretical Base for NTPSummary on Physical ClocksLogical ClockHappens-Before Relation on EventsEvents Occurring at Three ProcessesLamport’s Logical ClockLamport TimestampsSpot the MistakeCorrected Example: Lamport Logical TimeOne thing to Notice …SummaryLecture 2-1Lecture 2-1CS 425/ECE 428Distributed SystemsCS 425/ECE 428Distributed SystemsLecture 2Time & SynchronizationReading: 11.1-11.4Klara NahrstedtLecture 2-2Lecture 2-2AcknowledgementAcknowledgement•The slides during this semester are based on ideas and material from the following sources: –Slides prepared by Professors M. Harandi, J. Hou, I. Gupta, N. Vaidya, Y-Ch. Hu, S. Mitra. –Slides from Professor S. Gosh’s course at University o Iowa.Lecture 2-3Lecture 2-3Why synchronize clocks? Why synchronize clocks? •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 Faster by 5 minutes?–What if your watch is Late by 5 minutes?•Two sharpshooters in a multiplayer online game kill the same target. Who gets the point? •Object A is observed by S1 and S2 at local times t1 and t2. Which way is A moving? How fast?•Synchronizing clocks helps us–Time-stamping events (provide ‘Fairness’)–Ordering events (provide ‘Correctness’)Lecture 2-4Lecture 2-4Plan for todayPlan for today•Sources of time•How to synchronize clocks?•Can we define sequence of events without physical clocks?Lecture 2-5Lecture 2-5Time SourcesTime Sources•De Facto Primary Standard – International Atomic Time (TAI) –Keeping of TAI started in 1955 –1 atomic second = 9,192,631,770 orbital transitions of Cs133 (Caesium) –86400 atomic seconds = 1 solar day – 3 ms•Coordinated Universal Time (UTC) – International Standard–Keeping of UTC started 1961–Derived from TAI by adding leap seconds to keep it close to solar time–UTC source signals are synchronized–UTC time is re-transmitted by GPS satellites •Local clocks are based on oscillatorsLecture 2-6Lecture 2-6TerminologyTerminology•Distributed System (DS) consists of N processes p1, p2, .. pN•Process pi, i є {1,…N}–State: values of local variables including time»Ci(t): the reading of the local clock at process i when the real time is t–Actions: send message [send(m)], receive message [recv(m)], compute [comp]•Occurrence of an action is called an eventLecture 2-7Lecture 2-7TerminologyTerminology•Events within process pi can be assigned timestamp and thus ordered•Events across different processes in DS need to be ordered, but Clocks in DS across processes are not synchronized–Process clocks can be different•Need algorithms for either –time synchronization or –telling which event happened before whichLecture 2-8Lecture 2-8DefinitionsDefinitions•Skew:–s(t) = Ci(t) – Cj(t)•Maximum Drift Rate (MDR) ρ–|t – Ci(t) | ≤ ρt–(1-ρ) ≤ dCi(t)/dt ≤ (1+ρ) •Synchronization interval R and synchronization bound D–| Ci(t) – Cj(t) | ≤ 2ρt–| Ci(R) – Cj(R)| ≤ 2ρR ≤ D –R ≤ D/2ρ –This calculation ignored propagation delaysMDRUTCclockReal timeClock time Clock 1Clock 2Real timeClock time RRLecture 2-9Lecture 2-9Synchronizing Physical ClocksSynchronizing Physical Clocks•External synchronization: For a synchronization bound D > 0, and for source Source(t) of UTC time, for i=1,2,...,N and for all real times t . Clocks Ci are accurate within the bound D.•Internal synchronization: For a synchronization bound D>0, for i, j=1,2,...,N and for all real times t . Clocks Ci agree within the bound D.,)()( DtCtSourceiDtCtCji )()(Lecture 2-10Lecture 2-10Use elected leader process to ensure maximum skew is ρ among clientsElected leader broadcasts to all machines for their time, adjusts times received for transmission delay & latency, averages times after removing outlierstells each machine how to adjust.In some systems multiple time leaders are used. Averaging client’s clocks may cause the entire system to drift away from UTC over timeFailure of the leader requires some time for re-election, so accuracy cannot be guaranteedInternal Synchronization: Berkeley Algorithm Internal Synchronization: Berkeley AlgorithmLecture 2-11Lecture 2-11External Synchronization: Cristian’s MethodExternal Synchronization: Cristian’s MethodmrmtClient piTime server S(keeps referencetime)mr - message where client pi asks time server S for timemt - message where time server responds with its current time T Client pi uses T in mt to set its clockLecture 2-12Lecture 2-12External Synchronization: Cristian’s MethodExternal Synchronization: Cristian’s Method•RTT = t1 – t2 (Round Trip Time)•Client sets its clock to T + RTT/2•Assumptions: –RTT measured accurately–Transmission and computation delays are symmetric–Server time-stamped the message at the last possible instant before sending it backLecture 2-13Lecture 2-13External Synchronization: Cristian’s MethodExternal Synchronization: Cristian’s Method•Suppose we know the minimum client-server one way transmission delay: min•Then => actual time at client could be between [T + min, T + RTT - min]•Accuracy: RTT/2 – minLecture 2-14Lecture 2-14Secondry 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 serversProvides UTC synchronization service across InternetUses time servers to sync. networked processes. Time servers are connected by sync. subnet tree. The root is adjusted directly. Each node synchronizes its children nodes. 122233333 3Lecture 2-15Lecture 2-15Messages 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 (e.g., m, m’ ) bears timestamps of recent message events: • the local time when the previous NTP message (m) was sent (Ti-3) and received (Ti-2), and • the local time when the current message


View Full Document

U of I CS 425 - Time & Synchronization

Documents in this Course
Lecture 8

Lecture 8

23 pages

TIPS

TIPS

3 pages

The Grid

The Grid

41 pages

Lecture 4

Lecture 4

27 pages

Lecture 4

Lecture 4

20 pages

The Grid

The Grid

41 pages

LECTURE 5

LECTURE 5

25 pages

Multicast

Multicast

23 pages

LECTURE

LECTURE

34 pages

Load more
Download Time & 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 Time & 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 Time & 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?