Computer Science 425 Distributed SystemsAcknowledgementAdministrativePlan for todayWhy synchronize clocks?Review of Lamport TimestampsLamport Logical Time ExampleProblem with Lamport Logical ClockExampleVector Logical ClocksVector TimestampsExample: Vector Logical TimeComparing Vector TimestampsExerciseGlobal State and Global SnapshotExample of a Global StateHow would you take this photograph if each country’s premier were sitting in their respective capital? -- that’s the challenge of distributed global snapshots!Why take a global snapshot?What is Global state of a Distributed System?Obvious First AttemptProcess HistoryGlobal History and CutConsistent StatesSystem ExecutionRuns and LinearizationState ReachabilityGlobal State PredicatesQuick Note – Liveness versus SafetySummaryLecture 3-1Lecture 3-1Computer Science 425Distributed SystemsComputer Science 425Distributed SystemsLecture 3Logical Clock and Global States/ SnapshotsReading: Chapter 11.4&11.5Klara NahrstedtLecture 3-2Lecture 3-2AcknowledgementAcknowledgement•The slides during this semester are based on ideas and material from the following sources: –Slides prepared by Professors M. Harandi, J. Hou, I. Gupta, N. Vaidya, Y-Ch. Hu, S. Mitra. –Slides from Professor S. Gosh’s course at University o Iowa.Lecture 3-3Lecture 3-3Administrative Administrative •Form Groups for MP projects –Up to 3 members per group•Group Formation Deadline: September 1–Email names to TA today•Coming Next Homework 1 (Thursday)•Introductory material to get introduced to the Eclipse/Android Programming Environment is posted - (Optional MP0)•Ying Huang (TA) – changed office hours–Monday 2-3pm –Thursday 3:15-4:15pmLecture 3-4Lecture 3-4Plan for today Plan for today •Can we define sequence of events without using physical clocks?–Lamport logical clock –Vector clock•Computing logical sequence of eventsLecture 3-5Lecture 3-5Why synchronize clocks? Why synchronize clocks? •Two sharpshooters in a multiplayer online game kill the same target. Who gets the point? •Object A is observed by S1 and S2 at local times t1 and t2. Which way is A moving? How fast?•Synchronizing clocks helps us–Time-stamping events (provide ‘Fairness’)–Ordering events (provide ‘Correctness’)Lecture 3-6Lecture 3-6Review of Lamport TimestampsReview of Lamport Timestampsabc de fm1m2213 451p1p2p3Physical timeLecture 3-7Lecture 3-7Lamport Logical Time Example Lamport Logical Time Example p 1p 2p 3p 412233545768910700001243687nClock ValueMessagetimestampPhysical TimeLecture 3-8Lecture 3-8Problem with Lamport Logical ClockProblem with Lamport Logical Clock•Let timestamp(a) be the Lamport logical clock timestamp a b => timestamp(a) < timestamp(b) (if a happens before b, then Lamport_timestamp(a) < Lamport_timestamp(b))timestamp(a) < timestamp(b) => a b(If Lamport_timestamp(a) < Lamport_timestamp(b), it does NOT imply that a happens before bLecture 3-9Lecture 3-9logically concurrent eventsExampleExample p 1p 2p 3p 412233545768910700001243687nClock ValueMessagetimestampPhysical TimeNote: Lamport Timestamps: 3 < 7, but event with timestamp 3 is concurrent to event with timestamp 7, i.e., events are not in ‘happen-before’ relation.Lecture 3-10Lecture 3-10Vector Logical Clocks Vector Logical Clocks Vector Logical time is better: All processes use a vector of counters (logical clocks), ith element is the clock value for process i, initially all zero. Each process i increments the ith element of its vector upon an instruction or send event. Vector value is timestamp of the event. A send(message) event carries its vector timestamp (counter vector) For a receive(message) event, Max(Vreceiver[j] , Vmessage[j]), if j is not self Vreceiver[j] + 1 otherwiseVreceiver[j] =Lecture 3-11Lecture 3-11Vector TimestampsVector Timestampsabc de fm1m2(2,0,0)(1,0,0)(2,1,0) (2,2,0)(2,2,2)(0,0,1)p1p2p3Physical timeLecture 3-12Lecture 3-12Example: Vector Logical Time Example: Vector Logical Time p 1p 2p 3p 40,0,0,0Vector logical clockMessage(vector timestamp)Physical Time0,0,0,00,0,0,00,0,0,0(1,0,0,0)1,0,0,01,1,0,02,0,0,02,0,1,0(2,0,0,0)2,0,2,02,0,2,1(2,0,2,0)1,2,0,02,2,3,0(1,2,0,0)4,0,2,24,2,4,2(4,0,2,2)2,0,2,23,0,2,2(2,0,2,2)2,0,2,34,2,5,3(2,0,2,3)n,m,p,qLecture 3-13Lecture 3-13Comparing Vector Timestamps Comparing Vector Timestamps VT1 = VT2, iff VT1[i] = VT2[i], for all i = 1, … , n VT1 < VT2, iff VT1[i] < VT2[i], for all i = 1, … , n VT1 < VT2, iff VT1 < VT2 & j (1 < j < n & VT1[j] < VT2 [j]) VT1 is concurrent with VT2iff (not VT1 < VT2 AND not VT2 < VT1)Lecture 3-14Lecture 3-14ExerciseExerciseShow: a b if and only if vectorTS(a) < vectorTS(b)Lecture 3-15Lecture 3-15Global State and Global SnapshotGlobal State and Global Snapshot•Counting Camels–Satellites cover the entire area of interest–Each satellite can count the number of camels in its zone–How to compute the total number of camels? This is the Global State ProblemLecture 3-16Lecture 3-16[United Nations photo by Paul Skipworth for Eastman Kodak Company ©1995 ]Example of a Global StateExample of a Global StateLecture 3-17Lecture 3-17How would you take this photograph if each country’s premier were sitting in their respective capital?-- that’s the challenge of distributed global snapshots!How would you take this photograph if each country’s premier were sitting in their respective capital?-- that’s the challenge of distributed global snapshots!Lecture 3-18Lecture 3-18Why take a global snapshot?Why take a global snapshot?p2p1messagegarbage objectobjectreferencea. (Distributed) Garbage collectionp2p1wait-forwait-forb. (Distributed) Deadlock Detectionp2p1activatepassive passivec. Termination DetectionLecture 3-19Lecture 3-19What is Global state of a Distributed System?What is Global state of a Distributed System?•At real time t, the global state is –Instantaneous states of all processes–Messages in transit on channelstLecture 3-20Lecture 3-20Obvious First AttemptObvious First Attempt•If we have perfectly synchronized clocks–Each process pi records its xi state at some future time t–Sends xi(t) to all other processes•Problem –This approach does not record state of the channels–Perfect synchronization is not possible (message delay un- certainity is nonzero)•Relax the Problem –Instead of actual global state of the system we will try to capture a
View Full Document
Unlocking...