Logical ClocksTime: A major issue in distributed systemsTime in Distributed SystemsExternal TimeTime seen on internal clocksLogical notion of timeLogical time as a time-space pictureNotationLogical clocksAlgorithmIllustration of logical timestampsConcurrent eventsVector timestampsIllustration of vector timestampsVector timestamps accurately represent happens-before relationSlide 16Examples of VT’s and happens-beforeNotice that vector timestamps require a static notion of system membershipWhat about “real-time” clocks?Interpretations of temporal termsNeither clock is appropriatePerspectives on logical timeCausal notions of past, futureSlide 24Issues raised by timeWays to extend time to a total orderAn exampleEasy caseA more complex exampleSlide 30Slide 31Slide 32OptimizationsSlide 34Slide 35Slide 36Slide 37Slide 38More examplesSlide 40Slide 41Slide 42Slide 43Totem and TransisSlide 45Things to noticeMajor uses of timeLogical ClocksKen BirmanTime: A major issue in distributed systemsWe tend to casually use temporal conceptsExample: “p suspects that q has failed”Implies a notion of time: first q was believed correct, later q is suspected faultyChallenge: relating local notion of time in a single process to a global notion of timeDiscuss this issue before developing practical tools for dealing with other aspects, such as system stateTime in Distributed SystemsThree notions of time:Time seen by external observer. A global clock of perfect accuracyTime seen on clocks of individual processes. Each has its own clock, and clocks may drift out of sync.Logical notion of time: event a occurs before event b and this is detectable because information about a may have reached b.External TimeThe “gold standard” against which many protocols are definedNot implementable: no system can avoid uncertain details that limit temporal precision!Use of external time is also risky: many protocols that seek to provide properties defined by external observers are extremely costly and, sometimes, are unable to cope with failuresTime seen on internal clocksMost workstations have reasonable clocksClock synchronization is the big problem (will visit topic later in course): clocks can drift apart and resynchronization, in software, is inaccurateUnpredictable speeds a feature of all computing systems, hence can’t predict how long events will take (e.g. how long it will take to send a message and be sure it was delivered to the destination)Logical notion of timeHas no clock in the sense of “real-time”Focus is on definition of the “happens before” relationship: “a happens before b” if:both occur at same place and a finished before b started, ora is the send of message m, b is the delivery of m, ora and b are linked by a chain of such eventsLogical time as a time-space pictureabdcp0p1p2p3a, b are concurrent c happens after a, bd happens after a, b, cNotationUse “arrow” to represent happens-before relationFor previous slide:a  c, b  c, c  dhence, a  d, b  da, b are concurrentAlso called the “potential causality” relationLogical clocksProposed by Lamport to represent causal orderWrite: LT(e) to denote logical timestamp of an event e, LT(m) for a timestamp on a message, LT(p) for the timestamp associated with process p Algorithm ensures that if a  b, then LT(a) < LT(b)AlgorithmEach process maintains a counter, LT(p)For each event other than message delivery: set LT(p) = LT(p)+1When sending message m, set LT(m) = LT(p)When delivering message m to process q, set LT(q) = max(LT(m), LT(q))+1Illustration of logical timestamps0 1 2 7p0p1p2p30 1 6 0 2 3 4 5 60 1Concurrent eventsIf a, b are concurrent, LT(a) and LT(b) may have arbitrary values!Thus, logical time lets us determine that a potentially happened before b, but not that a definitely did so!Example: processes p and q never communicate. Both will have events 1, 2, ... but even if LT(e)<LT(e’) e may not have happened before e’Vector timestampsExtend logical timestamps into a list of counters, one per process in the systemAgain, each process keeps its own copyEvent e occurs at process p: p increments VT(p)[p] (p’th entry in its own vector clock)q receives a message from p: q sets VT(q)=max(VT(q),VT(p)) (element-by-element)Illustration of vector timestamps[1,0,0,0] [2,0,0,0][0,0,1,0][2,1,1,0] [2,2,1,0]p0p1p2p3[0,0,0,1]Vector timestamps accurately represent happens-before relationDefine VT(e)<VT(e’) if, for all i, VT(e)[i]<VT(e’)[i], and for some j, VT(e)[j]<VT(e’)[j]Example: if VT(e)=[2,1,1,0] and VT(e’)=[2,3,1,0] then VT(e)<VT(e’)Notice that not all VT’s are “comparable” under this rule: consider [4,0,0,0] and [0,0,0,4]Vector timestamps accurately represent happens-before relationNow can show that VT(e)<VT(e’) if andonly if e  e’:If e  e’, then there exists a chain e0  e1  ...  en on which vector timestamps increase “hop by hop”If VT(e)<VT(e’) suffices to look at VT(e’)[proc(e)], where proc(e) is the place that e occured. By definition, we know that VT(e’)[proc(e)] is at least as large as VT(e)[proc(e)], and by construction, this implies a chain of events from e to e’Examples of VT’s and happens-beforeExample: suppose that VT(e)=[2,1,0,1] and VT(e’)=[2,3,0,1], so VT(e)<VT(e’)How did e’ “learn” about the 3 and the 1? Either these events occured at the same place as e’, orSome chain of send/receive events carried the values!If VT’s are not comparable, the corresponding events are concurrentNotice that vector timestamps require a static notion of system membershipFor vector to make sense, must agree on the number of entriesLater will see that vector timestamps are useful within groups of processesWill also find ways to compress them and to deal with dynamic group membership changesWhat about “real-time” clocks?Accuracy of clock synchronization is ultimately limited by uncertainty in communication latenciesThese latencies are “large” compared with speed of modern processors (typical latency may be 35us to 500us, time for thousands of instructions)Limits use