Computer Science 425 Distributed Systems CS 425 / CSE 424 / ECE 428 Fall 2010Last LectureExample of a Global StateThe distributed version is challenging and importantDetecting Global PropertiesAlgorithms to Find Global StatesObvious First Solution…Two Processes and Their Initial StatesExecution of the ProcessesProcess Histories and StatesConsistent StatesThe “Snapshot” AlgorithmThe “Snapshot” Algorithm (2)Chandy and Lamport’s ‘Snapshot’ AlgorithmSnapshot ExampleProvable Assertion: Chandy-Lamport algo. determines a consistent cutGlobal States useful for detecting Global PredicatesGlobal State PredicatesQuick Note – Liveness versus SafetySummary, AnnouncementsOptional SlidesSide Issue: Causality ViolationDetecting Causality ViolationLecture 6-1Lecture 6-1Computer Science 425Distributed SystemsCS 425 / CSE 424 / ECE 428Fall 2010Computer Science 425Distributed SystemsCS 425 / CSE 424 / ECE 428Fall 2010Indranil Gupta (Indy)September 9, 2010Lecture 6Global SnapshotsReading: Sections 11.5 2010, I. Gupta, K. Nahrtstedt, S. Mitra, N. Vaidya, M. T. Harandi, J. HouLecture 6-2Lecture 6-2Last Lecture Last Lecture •Time synchronization–Berkeley algorithm–Cristian’s algorithm–NTP–Is it possible to synchronize two servers’ clocks with error=0?•Lamport’s timestamps–Logical timestamps–Do the clock values of two servers need to be the same?–What are “concurrent” events?•Vector TimestampsLecture 6-3Lecture 6-3[United Nations photo by Paul Skipworth for Eastman Kodak Company ©1995 ]Example of a Global StateExample of a Global StateLecture 6-4Lecture 6-4The distributed version is challenging and importantThe distributed version is challenging and important•How would you take this photograph if each country’s premier were sitting in their respective capital, and sending messages to each other?•That’s the challenge of distributed global snapshots!•In a cloud: multiple servers handling multiple concurrent events and interacting with each other •Without the ability to obtain a global photograph of the system, it would be a chaotic system (with potentially lots of inconsistencies)Lecture 6-5Lecture 6-5Detecting Global PropertiesDetecting Global Propertiesp2p1messagegarbage objectobjectreferencea. Garbage collectionp2p1wait-forwait-forb. Deadlockp2p1activatepassive passivec. TerminationLecture 6-6Lecture 6-6Algorithms to Find Global StatesAlgorithms to Find Global States•Why?–(Distributed) garbage collection [think Grid application]–(Distributed) deadlock detection, termination [think database transactions]–Two clients buy the last flight ticket at around the same time•What?–Global state=state of all processes + state of all communication channels–Capture the instantaneous state of each process–And the instantaneous state of each communication channel, i.e., messages in transit on the channels•How?–We’ll see this lecture!Lecture 6-7Lecture 6-7Obvious First Solution…Obvious First Solution…•Synchronize clocks of all processes•Ask all processes to record their states at known time t•Problems?–Time synchronization possible only approximately (but distributed banking applications cannot take approximations)–Does not record the state of messages in the channels•Again: synchronization not required – causality is enough!Lecture 6-8Lecture 6-8Two Processes and Their Initial StatesTwo Processes and Their Initial Statesp1p2c2c1accountwidgets$1000 (none)account widgets$50 2000Lecture 6-9Lecture 6-9Execution of the ProcessesExecution of the Processesp1p2(empty)<$1000, 0> <$50, 2000>(empty)c2c11. Global state S02. Global state S13. Global state S24. Global state S3p1p2(Order 10, $100)<$900, 0> <$50, 2000>(empty)c2c1p1p2(Order 10, $100)<$900, 0> <$50, 1995>(five widgets)c2c1p1p2(Order 10, $100)<$900, 5> <$50, 1995>(empty)c2c1Send 5 widgetsLecture 6-10Lecture 6-10Process Histories and States Process Histories and States For a process Pi , where events ei0, ei1, … occur:history(Pi) = hi = <ei0, ei1, … >prefix history(Pik) = hik = <ei0, ei1, …,eik >Sik : Pi ’s state immediately after kth event For a set of processes P1 , …,Pi , …. :global history: H = i (hi) global state: S = i (Siki) a cut C H = h1c1 h2c2 … hncnthe frontier of C = {eici, i = 1,2, … n}Lecture 6-11Lecture 6-11Consistent States Consistent States A cut C is consistent if and only if e C (if f e then f C) A global state S is consistent if and only if it corresponds to a consistent cut P1P2P3e10e11e12e13e20e21e22e30e31e32Inconsistent cutConsistent cutLamport’s “happens-before”Lecture 6-12Lecture 6-12The “Snapshot” Algorithm The “Snapshot” Algorithm Records a set of process and channel states such that the combination is a consistent global state. Assumptions (System Model!):There is a communication channel between each pair of processes (@each process: N-1 in and N-1 out)Communication channels are unidirectional and FIFO-orderedNo failure, all messages arrive intact, exactly onceAny process may initiate the snapshot (by sending “Marker” message)Snapshot does not interfere with normal executionEach process is able to record its state and the state of its incoming channels (no central collection)Lecture 6-13Lecture 6-13The “Snapshot” Algorithm (2) The “Snapshot” Algorithm (2) 1. Marker sending rule for initiator process P0 After P0 has recorded its own state• for each outgoing channel C, send a marker message on C 2. Marker receiving rule for a process Pk on receipt of a marker over channel C if Pk has not yet recorded its own state-record Pk’s own state-record the state of C as “empty”-for each outgoing channel C, send a marker on C -turn on recording of messages over other incoming channels-else-record the state of C as all the messages received over C since Pk saved its own state; stop recording state of CLecture 6-14Lecture 6-14Chandy and Lamport’s ‘Snapshot’ AlgorithmChandy and Lamport’s ‘Snapshot’ AlgorithmMarker receiving rule for process pi On pi’s receipt of a marker message over channel c:if (pi has not yet recorded its state) itrecords its process state now;records the state of c as the empty set;turns on recording of messages arriving over other incoming channels;else pi records the state of c as the set of messages it has received over c since it saved its state.end ifMarker sending rule for process
View Full Document
Unlocking...