Last Class: Clock SynchronizationToday: More Canonical ProblemsLogical ClocksEvent OrderingHappened Before RelationEvent Ordering Using HBLamport’s Logical ClocksExample: Totally-Ordered MulticastingCausalityVector ClocksGlobal StateGlobal State (1)Distributed Snapshot AlgorithmDistributed SnapshotSnapshot Algorithm ExampleSlide 16CS677: 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 is important–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 in which 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 occur in 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 this message, then A -> B•Relation is transitive:–A -> B and B -> C => A -> C•Relation is undefined across processes that do not exhange messages–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-Ordered Multicasting•Updating a replicated database and leaving it in an inconsistent state.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 knows occurred at another process k•Also Vj[i] = Vj[i]+1•Exercise: prove that if V(A)<V(B), then A causally precedes 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 a distributed 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 another process 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 outgoing channels, save messages on all other channels until:–Subsequent marker on a channel: stop saving state for that channelCS677: Distributed OSComputer ScienceLecture 10, page 14Distributed Snapshot•A process finishes when–It receives a marker on each incoming channel and processes them 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 the marker 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 state of the incoming