Unformatted text preview:

CS677: Distributed OSComputer ScienceLecture 10, page 1Last Class: Clock Synchronization• Physical clocks• Clock synchronization algorithms– Cristian’s algorithm– Berkeley algorithmCS677: Distributed OSComputer ScienceLecture 10, page 2Today: More Canonical Problems• Logical clocks• Causality– Vector timestamps• Global state and termination detectionCS677: Distributed OSComputer ScienceLecture 10, page 3Logical 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 10, page 4Event 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 10, page 5Happened 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 exhangemessages– Partial ordering on eventsCS677: Distributed OSComputer ScienceLecture 10, page 6Event 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 10, page 7Lamport’s Logical ClocksCS677: Distributed OSComputer ScienceLecture 10, page 8Example: Totally-OrderedMulticasting• Updating a replicated database and leaving it in an inconsistentstate.CS677: Distributed OSComputer ScienceLecture 10, page 9Causality• 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 10, page 10Vector 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 10, page 11Global 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 10, page 12Global State (1)a) A consistent cutb) An inconsistent cutCS677: Distributed OSComputer ScienceLecture 10, page 13Distributed 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 10, page 14Distributed 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 10, page 15Snapshot Algorithm Examplea) Organization of a process and channels for a distributed snapshotCS677: Distributed OSComputer ScienceLecture 10, page 16Snapshot 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 incoming channel and finishes recording the stateof the incoming


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?