Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43115-410, F’04Lamport clocksDave [email protected]_Lamport115-410, F’04Synchronization●Project 4 due today●Homework 2 due Friday●Book report due Friday●FCE reminder–I will read (and take seriously) every word of what you write115-410, F’04Outline●Lamport clocks–Covered in 17.1, 17.2 (different focus from today)–Time, Clocks, and the Ordering of Events in a Distributed System●CACM 21:7 (1978)●Leslie Lamport also famous for ...?115-410, F’04Overview●Light cones●Meeting for beer●“Happened before” partial order●Logical clocks●Advanced techniques115-410, F’04Light cones●Concept–Effects propagate at or below speed of light●Objects, light/radio/X-rays, gravity–Knowledge of events limited the same way–Event propagation modeled by expanding sphere●Four-dimensional “cone”115-410, F’04Light conesSpaceTime115-410, F’04Light conesSpaceTime115-410, F’04Light conesSpaceTime115-410, F’04Light conesSpaceTime115-410, F’04Light conesSpaceTime115-410, F’04Light conesSpaceTime115-410, F’04Light conesSpaceTime115-410, F’04Light conesSpaceTime115-410, F’04Light cones●Future light cone–The part of spacetime potentially influenced by an event●Past light cone–The part of spacetime that could have influenced an event115-410, F’04Meeting for Beer●P1 transmits “Panther Hollow Inn” to blackboard115-410, F’04Meeting for Beer●P1 transmits “Panther Hollow Inn” to blackboard●P1 transmits to P2–Hey, P2, let's go have a beer.–I have transmitted the bar's name to the blackboard.–See you there!115-410, F’04Meeting for Beer●P1 transmits “Panther Hollow Inn” to blackboard●P1 transmits to P2–Hey, P2, let's go have a beer.–I have transmitted the bar's name to the blackboard.–See you there!●P2 receives P1's message115-410, F’04Meeting for Beer●P1 transmits “Panther Hollow Inn” to blackboard●P1 transmits to P2–Hey, P2, let's go have a beer.–I have transmitted the bar's name to the blackboard.–See you there!●P2 receives P1's message●P2 queries blackboard115-410, F’04Meeting for Beer●P1 transmits “Panther Hollow Inn” to blackboard●P1 transmits to P2–Hey, P2, let's go have a beer.–I have transmitted the bar's name to the blackboard.–See you there!●P2 receives P1's message●P2 queries blackboard●It says “Squirrel Cage” - how???115-410, F’04Meeting for BeerP1boardP2115-410, F’04Meeting for BeerP1boardP2115-410, F’04Meeting for BeerP1boardP2115-410, F’04Meeting for BeerP1boardP2115-410, F’04Meeting for BeerP1boardP2115-410, F’04Meeting for BeerP1boardP2115-410, F’04What went wrong?●P1 thought–Blackboard update happened before invitation●P2 thought–Invitation happened before blackboard update●When does an event “happen”?–When its effects propagate “everywhere relevant”●What does “happen before” mean?●Could that green node really be so slow?115-410, F’04Universe Model●System = set of processes●Process = sequence of events●Event–Internal: ++x;–Message transmission–Message reception115-410, F’04“Happened before” partial order●A happens before B (A B)–If A and B happen inside a process, in (A, B) order–If A = transmission, B = reception, of same message–If A B and B C, then A C●A and B are concurrent when–A ! B and B A●Observe: A ! A115-410, F’04Space-time Diagram● –inside a process, or–follow a message●p0 r2●concurrent–p0, q0, r0–p1, q1–q1, r0–p1, r0p0p1p2q0q1q2r0r1r2115-410, F’04 means “possibly causes”●p0 possibly causes p1–...by storing something in P's memory●p0 possibly causes q1–Message could trigger q1●Concurrent events–...cannot cause each other115-410, F’04Logical clocks●Can we assign timestamps to events?●Want–If A B then C(A) < C(B)●Events inside Pi–a b Ci(a) < Ci(b)●Message from Pi to Pj–a=Pi's send, b=Pj's receive Ci(a) < Cj(b)115-410, F’04Logical clocks●Events inside Pi–Increment Ci() between successive events●Message from Pi to Pj–Sender: place timestamp T in message: Ci(send)–Receiver: ensure Cj(receive) > T115-410, F’04Meeting for Beer533 427115-410, F’04Meeting for Beer5354 427115-410, F’04Meeting for Beer5454 455115-410, F’04Meeting for Beer5454 5756115-410, F’04Meeting for Beer5454 5859115-410, F’04Meeting for Beer5455 5959115-410, F’04What this means●P1 wants–<“PHI” written> happened before <read by P2>●Equivalent to “59 < 57” (oops)●The events were concurrent●“PHI” could not cause P2's bar trip115-410, F’04Space-time Diagram●P1 wants–<“PHI” declared> happened before <P2 decided>●Equivalent to “59 < 57” (oops)●The events were concurrent●“PHI” could not cause P2's bar tripPHImeetansmeetqueryqueryansPHI115-410, F’04Fixing the problem●P1 should wait for board to acknowledge●“PHI” causes ACK●ACK causes “Meet me at...”●“Meet me at...” causes bar trip●Then: “PHI” causes bar trip115-410, F’04Extensions●Define total ordering of system events–Typical (timestamp, process #) tuple comparison●Process # used to break timestamp ties●Distributed agreement algorithms–Such as “fair distributed mutual exclusion”●Requests must be granted “in order”●See text: 17.2●Adding physical (real-time) clocks115-410, F’04Summary●Light cones●“Happened before” partial order●Potential causality●Another definition of concurrency–You've dealt with single-clock race conditions●(one memory bus provides one global clock)–In distributed systems there is no global clock●Timestamps track message
View Full Document
Unlocking...