DOC PREVIEW
UMass Amherst CS 677 - Clock Synchronization

This preview shows page 1-2-3-4 out of 11 pages.

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

Unformatted text preview:

CS677: Distributed OSComputer ScienceLecture 11, page 1Last Class: Clock Synchronization• Physical clocks• Clock synchronization algorithms– Cristian’s algorithm– Berkeley algorithmCS677: Distributed OSComputer ScienceLecture 11, page 2Today: More Canonical Problems• Logical clocks• Causality– Vector timestamps• Global state and termination detectionCS677: Distributed OSComputer ScienceLecture 11, page 3Global Positioning System• Computing a position in a two-dimensional space.CS677: Distributed OSComputer ScienceLecture 11, page 4Global Positioning System• Real world facts that complicate GPS1.It takes a while before data on asatellite’s position reaches thereceiver.2.The receiver’s clock is generally notin synch with that of a satellite.CS677: Distributed OSComputer ScienceLecture 11, page 5Clock Synchronization in WirelessNetworks• Reference broadcast sync (RBS): receivers synchronize with oneanother using RB server– Mutual offset = Ti,s- Tj,s (can average over multiple readings)CS677: Distributed OSComputer ScienceLecture 11, page 6Network Time Protocol• Widely used standard - based on Cristian’s algoCS677: Distributed OSComputer ScienceLecture 11, page 7Logical Clocks• For many problems, internal consistency of clocks isimportant– Absolute time is less important– Use logical clocks• Key idea:– Clock synchronization need not be absolute– If two machines do not interact, no need to synchronize them– More importantly, processes need to agree on the order inwhich events occur rather than the time at which they occurredCS677: Distributed OSComputer ScienceLecture 11, page 8Event Ordering• Problem: define a total ordering of all events that occurin a system• Events in a single processor machine are totally ordered• In a distributed system:– No global clock, local clocks may be unsynchronized– Can not order events on different machines using local times• Key idea [Lamport ]– Processes exchange messages– Message must be sent before received– Send/receive used to order events (and synchronize clocks)CS677: Distributed OSComputer ScienceLecture 11, page 9Happened Before Relation• If A and B are events in the same process and A executed before B,then A -> B• If A represents sending of a message and B is the receipt of thismessage, then A -> B• Relation is transitive:– A -> B and B -> C => A -> C• Relation is undefined across processes that do not exchangemessages– Partial ordering on eventsCS677: Distributed OSComputer ScienceLecture 11, page 10Event Ordering Using HB• Goal: define the notion of time of an event such that– If A-> B then C(A) < C(B)– If A and B are concurrent, then C(A) <, = or > C(B)• Solution:– Each processor maintains a logical clock LCi– Whenever an event occurs locally at I, LCi = LCi+1– When i sends message to j, piggyback Lci– When j receives message from i• If LCj < LCi then LCj = LCi +1 else do nothing– Claim: this algorithm meets the above goalsCS677: Distributed OSComputer ScienceLecture 11, page 11Lamport!s Logical ClocksCS677: Distributed OSComputer ScienceLecture 11, page 12Example: Totally-OrderedMulticasting• Updating a replicated database and leaving it in an inconsistentstate.CS677: Distributed OSComputer ScienceLecture 11, page 13Causality• Lamport’s logical clocks– If A -> B then C(A) < C(B)– Reverse is not true!!• Nothing can be said about events by comparing time-stamps!• If C(A) < C(B), then ??• Need to maintain causality– If a -> b then a is casually related to b– Causal delivery:If send(m) -> send(n) => deliver(m) -> deliver(n)– Capture causal relationships between groups of processes– Need a time-stamping mechanism such that:• If T(A) < T(B) then A should have causally preceded BCS677: Distributed OSComputer ScienceLecture 11, page 14Vector Clocks• Each process i maintains a vector Vi– Vi[i] : number of events that have occurred at i– Vi[j] : number of events I knows have occurred at process j• Update vector clocks as follows– Local event: increment Vi[I]– Send a message :piggyback entire vector V– Receipt of a message: Vj[k] = max( Vj[k],Vi[k] )• Receiver is told about how many events the sender knowsoccurred at another process k• Also Vj[i] = Vj[i]+1• Exercise: prove that if V(A)<V(B), then A causallyprecedes B and the other way around.CS677: Distributed OSComputer ScienceLecture 11, page 15Enforcing Causal Communication• Figure 6-13. Enforcing causal communication.CS677: Distributed OSComputer ScienceLecture 11, page 16Global State• Global state of a distributed system– Local state of each process– Messages sent but not received (state of the queues)• Many applications need to know the state of the system– Failure recovery, distributed deadlock detection• Problem: how can you figure out the state of adistributed system?– Each process is independent– No global clock or synchronization• Distributed snapshot: a consistent global stateCS677: Distributed OSComputer ScienceLecture 11, page 17Global State (1)a) A consistent cutb) An inconsistent cutCS677: Distributed OSComputer ScienceLecture 11, page 18Distributed Snapshot Algorithm• Assume each process communicates with anotherprocess using unidirectional point-to-point channels (e.g,TCP connections)• Any process can initiate the algorithm– Checkpoint local state– Send marker on every outgoing channel• On receiving a marker– Checkpoint state if first marker and send marker on outgoingchannels, save messages on all other channels until:– Subsequent marker on a channel: stop saving state for thatchannelCS677: Distributed OSComputer ScienceLecture 11, page 19Distributed Snapshot• A process finishes when– It receives a marker on each incoming channel and processesthem all– State: local state plus state of all channels– Send state to initiator• Any process can initiate snapshot– Multiple snapshots may be in progress• Each is separate, and each is distinguished by tagging themarker with the initiator ID (and sequence number)ACBMMCS677: Distributed OSComputer ScienceLecture 11, page 20Snapshot Algorithm Examplea) Organization of a process and channels for a distributed snapshotCS677: Distributed OSComputer ScienceLecture 11, page 21Snapshot Algorithm Exampleb) Process Q receives a marker for the first time and records its local statec) Q records all incoming messaged) Q receives a marker for its


View Full Document

UMass Amherst CS 677 - Clock Synchronization

Download Clock 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 Clock 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 Clock 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?