DOC PREVIEW
CORNELL CS 614 - Study Guide

This preview shows page 1-2-16-17-18-33-34 out of 34 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 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 34 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 34 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 34 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 34 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 34 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 34 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

TimeWhat’s wrong with the clocks?Why is synchronization so complicated?External Clock SynchronizationInternal Clock SynchronizationSoftware Clock SynchronizationCorrect clock - DefinitionFailure modesThe clock synchronization problemOptimal accuracyPaper 1: Optimal Clock SynchronizationAuthenticated AlgorithmSlide 13Slide 14Slide 15Achieving Optimal AccuracyAuthenticated MessagesNonauthenticated AlgorithmBroadcast PrimitiveInitialization and IntegrationPaper 2: Why try another approach?Probabilistic ICSTheir approachProbabilistic Clock ReadingSlide 25Staggering MessagesTransitive Remote Clock ReadingRound Message Exchange ProtocolOutline of AlgorithmsConvergence FunctionsSlide 31Failure classesConclusions – Which one is better?Slide 34TimeMaya HaridasanApril 15thWhat’s wrong with the clocks?Why is synchronization so complicated?Due to variations of transmission delays each process cannot have an instantaneous global view of every remote clock valuePresence of drifting ratesHardest: support faulty elementsExternal Clock SynchronizationSynchronize clocks with respect to an external time reference: usually useful in loosely coupled networks or real-time systems (Ex, NTP)Internal Clock SynchronizationEnables a process to measure the duration of distributed activities that start on one processor and terminate on another one.Establishes an order between distributed events in a manner that closely approximates their real time precedence.Synchronize clocks among themselvesSoftware Clock Synchronization1. Deterministic  assumes an upper bound on transmission delays – guarantees some precision2. Statistical  expectation and standard deviation of the delay distributions are known3. Probabilistic  no assumptions about delay distributionsRealistic?Reliable?Any guarantees?Correct clock - DefinitionA correct clock Hp satisfies the bounded drift condition:(1 – ρ)(t – s) ≤ Hp(t) – Hp(s) ≤ (1 + ρ)(t – s)Perfect hardware clockHp(t) – Hp(s) = (t – s)ClockvaluesReal timeHp(t) – Hp(s) < (1- ρ)(t – s)Hp(t) – Hp(s) > (1+ ρ)(t – s)Failure modesCrash Failure: processor behaves correctly and then stops executing foreverPerformance Failure: processor reacts too slowly to a trigger eventArbitrary Failure (a.k.a Byzantine):processor executes uncontrolled computationThe clock synchronization problemProperty 1 (Agreement):| Lpi(t) – Lpj(t) |  δ, (δ is the precision of the clock synchronization algorithm)Property 2 (Accuracy):(1 – ρv)(t – s) + a ≤ Lp(t) – Lp(s) ≤ (1 + ρv)(t – s) + bWhat is optimal accuracy?ρv ≠ ρOptimal accuracyDrift rate of the synchronized clocks is bounded by the maximum drift rate of correct harware clocks(1 – ρ)(t – s) + a ≤ Lp(t) – Lp(s) ≤ (1 + ρ)(t – s) + bρv = ρPaper 1: Optimal Clock SynchronizationClaims:• Accuracy need not be sacrificed in order to achieve synchronization• It’s the first synchronization algorithm where logical clocks have the same accuracy as the underlying physical clocks•Unified solution to all models of failureAuthenticated AlgorithmP – logical time between resynchronizationskth resynchronization - Waiting for time kPreal time tReady to synchronizelogical time kPAuthenticated AlgorithmP – logical time between resynchronizationslogical time kPReady to synchronizeAuthenticated AlgorithmP – logical time between resynchronizationslogical time kPReady to synchronizeAuthenticated AlgorithmP – logical time between resynchronizationslogical time kPKp + Synchronize!Achieving Optimal AccuracyUncertainty of tdelay introduces a difference in the logical time between resynchronizations  Reason for non-optimal accuracySolution:Slow down the logical clocks by a factor of where  = tdel / 2(1 + )P(P -  - )Authenticated MessagesCorrectness: If at least f + 1 correct processes broadcast messages by time t, then every correct process accepts the message by time t + tdelUnforgeability:If no correct process broadcasts a message by time t, then no correct process accepts the message by t or earlierRelay:If a correct process accepts the message at time t, then every correct process does so by time t + tdelNonauthenticated AlgorithmReplace signed communication with a broadcast primitive Primitive relays messages automaticallyCost of O(n2) messages per resynchronizationNew limit on number of faulty processes allowed:n > 3fBroadcast Primitive(echo, round k)Received f + 1 distinct (init, round k)!1Received f + 1 distinct (echo, round k)!2Received 2f + 1 distinct (echo, round k)!Accept (round k)3Initialization and IntegrationSame algorithms can be used to achieve initial synchronization and integrate new processes into the networkA process independently starts clock CoOn accepting a message at real time t, it sets C0 = α“Passive” scheme for integration of new processesPaper 2: Why try another approach?Traditional deterministic fault-tolerant clock synchronization algorithms:Assume bounded communication delaysRequire the transmission of at least N2 messages each time N clocks are synchronizedBursty exchange of messages within a narrow re-synchronization real-time intervalProbabilistic ICSProposes family of fault-tolerant internal clock synchronization (ICS) protocolsProbabilistic reading achieves higher precisions than deterministic readingDoesn’t assume unbounded communication delaysUse of convergence function optimal accuracyClaims:Their approachOnly requires to send a number of unreliable broadcast messagesStaggers the message traffic in timeUses a new transitive remote clock reading methodNumber of messages in the best case: N + 1(N time server processes)Probabilistic Clock ReadingBasic Idea:T0 T2T1m1 m2(T2 – T0)(1 + ) = maximum bound (real time)min ≤ t(m2) ≤ (T2 – T0)(1 + ) - min max(m2)(1 + ) + min(m2)(1 - )2Cq = T1 +pqProbabilistic Clock ReadingBasic Idea:T0 T2T1m1 m2pqIs error ≤  ?Yes: SuccessNo? Try reading again (Limit: D)Maximum acceptable clock reading errorStaggering Messagespqrcycleslotp slots per cyclek cycles per roundp slots per cyclek cycles per roundTransitive Remote Clock ReadingCan reduce the number of messages per round to N + 1pqrTCr (T,p)Cq (T,p)tpCr (T,q)Ttqreal timeCr (T,q) = Cr (T,p) + T - Cq (T,p)Cannot be used when arbitrary failures can occur!Round Message Exchange ProtocolFinish ModeClock times:p q r10 11 101 1 2finish messages terrReply


View Full Document

CORNELL CS 614 - Study Guide

Documents in this Course
Load more
Download Study Guide
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 Study Guide 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 Study Guide 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?