分布式计算chapter单击此处编辑母版标题

1、 Introduction Clocks,events and process states Synchronizing physical clocks Logical time and logical clocks Global states Distributed debugging SummaryChapter 10: Time and Global States Need to measure accurately E.g. auditing in e-commerce Algorithms depending on E.g. consistency, makeTime is an i

2、mportant issue in DS Physicists view Newtons notation: absolute physical time Einsteins Relativity Theory Peoples approaches dealing with time Approximately synchronize Logical clocksThere is no universe physical clock Introduction Clocks,events and process states Synchronizing physical clocks Logic

3、al time and logical clocks Global states Distributed debugging SummaryChapter 10: Time and Global States A collection of N processes pi, i = 1,2, . N si The state of pi E.g. variables Actions of pi Operations that transform pis state Send or receive message between pj Model of a distributed system e

4、 Event: occurrence of a single actioni occur before in pi , e.g. e i e Total order of events in pi history(pi ) = hi hi = Model of a distributed system A device that count oscillations occurring in a crystal at a definite frequency Hardware time: Hi(t) The counts of oscillation since an original poi

5、nt Software time: Ci(t) = Hi(t)+ Timestamp of an event Clock in computer Clock drift Crystal oscillate at different rate Clock drift can not be avoided Clock skew The instantaneous difference between the readings of any two clocksClock skew and clock driftNetwork Rotation of earth on its axis and ab

6、out the Sun Days, Years, etc Second is 1/86400 astronomical time Standard second Atomic oscillator Drift rate: one part in 1013 Since 1967: 9,192,631,770 periods of transition between the two hyperfine levels of the ground state of Cs133Astronomical Time &International Atomic Time shift between astr

7、onomical time and atomic time The period of the Earths rotation about its axis is gradually getting longer Tidal friction, atmospheric effects, etc Leap second Atomic time which is inserted a leap second occasionally to keep in step with astronomical time Broadcast UTC to the World E.g., by GPS or W

8、WVCoordinated Universal Time (UTC) Introduction Clocks,events and process states Synchronizing physical clocks Logical time and logical clocks Global states Distributed debugging SummaryChapter 10: Time and Global States Ci : pis clock I: an interval of real time External synchronization For a synch

9、ronization bound D 0, and for a source S of UTC time, |S(t)-Ci(t)| 0, |Ci(t)-Cj(t)| D for i, j =1,2, N, and for all real times t in I Clocks Ci agree within the bound D If accurate to within D, then agree within 2DExternal & Internal synchronization (2) Correctness of a hardware clock H A bounded dr

10、ift rate , e.g. 10-6 seconds/second,t and t are real time (1 - )(t - t) = H(t) - H(t) t C(t) C(t) Set clock back Errors in the make process Change the clock rateGeneral synchronization issues= ( 1 + )H(t) - H(t)(t - t)(1 - ) = Clock failures Crash failure: stop ticking Arbitrary failure, e.g. Y2K bu

11、gGeneral synchronization issues (2) Protocol Sender: send M(t) Receiver: set time to t + Ttrans Bounds are know in synchronous systemv min Ttrans =0, then oi (t+t) /2 = o = oi + (t+t) /2Thenoi - di /2 = o = oi + di /2oi is the estimated timedi is the measure of the accuracy NTP servers retain 8 most

12、 recent pairs The value oi of that corresponds to the minimum value di is chosen to estimate o A NTP server exchanges with several peers in addition to with parent Peers with lower stratum numbers are favoured Peers with the lowest synchronization dispersion are favouredSymmetric mode sync. implemen

13、tation Introduction Clocks,events and process states Synchronizing physical clocks Logical time and logical clocks Global states Distributed debugging SummaryChapter 10: Time and Global States HB1: If process pi: eie, then eeHB2: For any message m, send(m) receive(m)HB3: IF e, eand e are events such

14、 that e e and e e, then e eCausal orderingHappen-before relation Examplea | e ShortcomingsNot suitable to processes collaboration that does not involve messages transmissionCapture potential causal orderingHappen-before relation LC1Li is incremented before each event is issued at process pi : Li :=L

15、i+1 LC2: (a) When a process pi sends a message m, it piggybacks on m the value t = Li(b) On receiving (m,t), a process Pj computes Lj := max(Lj, t) and then applies LC1 before timestamping the event receive(m)Lamport timestamps algorithm e e L(e) L(e) L(e) L(e) e e or e|eLamport timestamps algorithm

16、 (2)abcdefm1m2213451p1p2p3Physical time Useful in some applicationsTotally ordered logical clocksAssumptionTi : local timestamp of e that is an event occurring at piTj : local timestamp of e that is an event occurring at pjDefine the timestamps of e, e are (Ti, i), (Tj, j)Define (Ti, i) (Tj, j) if T

17、i Tj , or Ti = Tj and i j Each process pi keeps a vector clock Vi VC1: Initially, Vij=0, for i, j = 1,2, N VC2: Just before pi timestamps an event, it sets Vii := Vii +1 VC3: pi includes the value t= Vi in every message it sends VC4: When pi receives a timestamp t in a message, it sets Vij :=max(Vij

18、, tj), for j=1,2,NVector Clocks - algorithm Compare vector timestamps V = V iff V j = Vj for j = 1,2, N V = V iff Vj=Vj for j = 1,2, N V V iff Vj Vj for j = 1,2, N Otherwise VV V(e) V(e) ee, V(e) V(e) e|eVector Clocks - significanceVector Clocks - exampleabcdefm1m2(2,0,0)(1,0,0)(2,1,0)(2,2,0)(2,2,2)

19、(0,0,1)p1p2p3Physical time Introduction Clocks,events and process states Synchronizing physical clocks Logical time and logical clocks Global states Distributed debugging SummaryChapter 10: Time and Global States Distributed garbage collection Based on reference counting Should include the state of

20、communication channels Distributed deadlock detection Look for “waits-for” relationship Distributed termination detection Look for state in which all processes are passive Distributed debugging Need collect values of distributed variables at the same timeRequirements of global states The essential p

21、roblem of Global states Absence of global timeGlobal states and consistent cutsHistory of process pihi = Prefix of a processs historyhik = Global history of processes set H = h1 h2 hN The state of process pisik : the state before the kth event occursThe state of channel between the pi and pj when tr

22、ansmit the massageA cut of a system executionA subset of of its global history that is a union of prefixes of process histories.C = A global stateS = (s1, s2, sN)si corresponding to the cut of C is that of pi immediately after the last event processed by pi in the cut- eiciGlobal states and consiste

23、nt cutsA cut C is consistent: For all events eC, f e f C, m1m2p1p2Physical timee10Consistent cutInconsistent cute11e12e13e20e21e22Global states and consistent cutsA consistent global state: correspond to a consistent cutThe si corresponding to the cut C is that of pi immediately after the last event

24、 processed by pi in CExecution of a distributed systemS0 S1 S2 Global states and consistent cutsA runa total ordering of all the events in a global history that is consistent with each local historys ordering, i Not all runs pass through consistent global state A linearization (consistent) runan ord

25、ering of the events in a global history H that is consistent with this happened-before relation on H.Pass only consistent global state Global states and consistent cutsS is reachable from a state Sthere is a linearization that pass through S and then S AimCapture consistent global state of a distrib

26、uted systemThe “snapshot” algorithm of Chandy and Lamport Neither channels nor processes fail Unidirectional channels, FIFO message delivery Complete connection among all processes Any process may initiate a global snapshot at any time Process may continue execution and send and receive normal messa

27、ge while snapshot takes place The “snapshot” algorithm - assumptions When one process record a state Si, make all other processes record states that have been caused by SiThe “snapshot” algorithm - idea Incoming channels, outgoing channels Process state + channel state Marker message Marker sending

28、rule: a process sends a marker after it has recorded its state, but before it send any other messages Marker receiving rule: a process records its state if the state has changed since last recording, or record the states of the incoming channelThe “snapshot” algorithm - methodMarker receiving rule f

29、or process pi On pis 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

30、 has received over c since it saved its state.end ifMarker sending rule for process piAfter pi has recorded its state, for each outgoing channel c: pi sends one marker message over c (before it sends any other message over c). p1 trade p2 in widget which is 10$ per item Initial state p1 has sent 50$

31、 to p2 to buy 5 widget, and p2 has received the orderThe “snapshot” algorithm - examplep1p2c2c1accountwidgets$1000(none)accountwidgets$502000 The final recorded state P1:; p2:;c1:;c2:Execution of the processes in the examplep1p2(empty)(empty)c2c11. Global state S02. Global state S13. Global state S2

32、4. Global state S3p1p2(Order 10, $100), M(empty)c2c1p1p2(Order 10, $100), M(five widgets) Mc2c1p1p2(Order 10, $100)(empty)c2c1(M = marker message) The caught states are consistent Examine two events ei, ej between pi and pj, such that eiejCharacterising the observed state - proofProof: We want to pr

33、ove: if ej occurred before pj recorded its state, then ei must have occurred before pi recorded its stateThe opposite of what we want to prove: pi recorded its state before ei occurredCharacterising the observed state - proofProving:Because ei ej, then there are messages m1, m2 at pj. Before these m

34、essages, there must be a marker saying pi has recorded its stateThese marker message let pj record state before ejSo: the caught state is consistent Introduction Clocks,events and process states Synchronizing physical clocks Logical time and logical clocks Global states Distributed debugging Summary

35、Chapter 10: Time and Global States example Safety condition of a distributed system: |xi-xj|=V(sj)i for i,j = 1,2, N If one processs state depends upon another, the global state also encompasses the state upon which it dependsObserving consistent global states The lattice of collected global states

36、Monitor construct the reachability lattice by the consistent global state identification algorithm Find consistent global states Establish the reachability relation between statesSij is in level (i+j) Show all the linearizations corresponding to a historyObserving consistent global states continued

37、Apply a given global state predicate on the states Possibly : there is a consistent global state s through which a linearization of H passes such that (s) is true Definitely : for all linearizations L of H, there is a consistent global state set S through which L passes such that (S) is trueObservin

38、g consistent global states Evaluating possibly There is a downwards way in which there is a state evaluated to True by Evaluating definitely There is no downwards way in which there is not a state evaluated to True by Example If evaluates to True in the state at level 5, then definitely If evaluates

39、 to false in the state at level 5, then possibly Evaluating possibly and definitely Asynchronous systems High time cost To find consistent global state S = (s1, s2, , sn), the monitor Should examine any two local states si and sj Synchronous systems |Ci(t)-Cj(t)| =V(sj)i si and sj should occurred at

40、 the same real timeEvaluating possibly and definitely in synchronous systems Introduction Clocks,events and process states Synchronizing physical clocks Logical time and logical clocks Global states Distributed debugging SummaryChapter 10: Time and Global States Clock skew, clock drift Synchronize p

41、hysical clocks Christians algorithm Berkeley algorithm Network Time Protocol Logical time Happen-before relation Lamport timestamp algorithm Vector clockSummary Global states Consistent cut, consistent state Snapshot algorithm Construct reachability relationship by snapshot Global debugging The moni

42、tor collects distributed events with vector timestamp Construct reachability relationship Examine possibly and definitely Summary continuedEvents occurring at three processesp1p2p3abcdefm1m2PhysicaltimeDetecting global propertiesp2p1messagegarbage objectobjectreferencea. Garbage collectionp2p1wait-f

43、orwait-forb. Deadlockp2p1activatepassivepassivec. TerminationPi has record its state?markerOp1Op2Op3Pi incoming channelrecord statechannel state: executed ops.Opn record statetimemarkerPiOp1Op2Op3Pi has record its state after update channel state: Op1, Op2, Op3markerPiOp1Op2Op3Pi has not record its

44、state after update Reachability between states in the snapshot algorithmSinitSfinalSsnapactual execution e0,e1,.recording recording beginsendspre-snap: e0,e1,.eR-1post-snap: eR,eR+1,.Find pre-snap events and post-snap events1. The snapshot is consistent global states that record a set of events that

45、 occurred on some processes2. Approach: Swap ej that should belong to post-snap events and ej+1 that should belong to pre-snap events according to the snap3. Analysis(1) This situation could not happen if ej ej+1 Since if ej+1 belongs to the pre-snap events, because the snapshot is consistent global

46、 states, so ej must belongs to the pre-snap events(2) This situation could happen if and only ej | ej+1 Then swap ej and ej+1 will not change the happen-before relationship, so the linearization condition isnt brokenVector timestamps and variable values for the execution of Figure 10.9m1m2p1p2Physical timeCut C1(1,0)(2,0)(4,3)(2,1)(2,2)(2,3)(3,0)x1= 1x1= 100 x1= 105x2= 100 x2= 95x2= 90 x1= 90Cut C2T