iKen BirmanCornell University. CS5410 Fall 2008. Real time and clocksy Lamport showed that if we care about event ordering, the best option is to use logical clocksB b l iyBut suppose we care about real time?y How well can clocks be synchronized?yTo what extent can the operating system help us build yTo what extent can the operating system help us build applications that are sensitive to time?Introducing “wall clock time”y There are several optionsy “Extend” a logical clock or vector clock with the clock time and use it to break tiestime and use it to break tiesy Makes meaningful statements like “B and D were concurrent, although B occurred first”yBut unless clocks are closely synchronized such statements yBut unless clocks are closely synchronized such statements could be erroneous!y We use a clock synchronization algorithm to reconcile differences between clocks on various computers in the differences between clocks on various computers in the networkSynchronizing clocksy Without help, clocks will often differ by many millisecondsPbl i h h hi dld i f yProblem is that when a machine downloads time from a network clock it can’t be sure what the delay wasyThis is because the “uplink” and “downlink” delays are This is because the uplink and downlink delays are often very different in a networky Outright failures of clocks are rare…Synchronizing clocksDelay: 123mspWhat time is it?time.windows.com09:23.02921y Suppose p synchronizes with time.windows.com and notes that 123 ms elapsed while the protocol was running what time is it now?while the protocol was running… what time is it now?Synchronizing clocksy Options?y P could guess that the delay was evenly split, but this is l th i WAN tti (d li k d rarely the case in WAN settings (downlink speeds are higher)y P could ignore the delayg yy P could factor in only “known” delayy For example, suppose the link takes at least 25ms in each di idirection…Synchronizing clocks25ms25msDelay: 123ms25ms25mspWhat time is it?time.windows.com09:23.02921y Suppose p synchronizes with time.windows.com and notes that 123 ms elapsed while the protocol was running what time is it now?while the protocol was running… what time is it now?Synchronizing clocksy In general can’t do better than uncertainty in the link delay from the time source down to pyTake the measured delayyTake the measured delayy Subtract the “certain” componenty We are left with the uncertaintyy Actual time can’t get more accurate than this uncertainty!What about GPS?y GPS has a network of satellites that send out the time, with microsecond precisionEh di i l il d yEach radio rec eiver captures several signals and compares the time of arrivalyThis allows them to triangulate to determine positionyThis allows them to triangulate to determine positionGPS TriangulationIssues in GPS triangulationy Depends on very accurate model of satellite positiony In practice, variations in gravity cause satellite to move hil i bitwhile in orbity Assumes signal was receiv ed “directly”yUrban “canyons” with reflection an issueyUrban canyons with reflection an issuey DOD encrypts low‐order bitsGPS as a time sourcey Need to estimate time for signals to transit through the atmospherey This isn’t hard because the orbit of the satellites is well knownyMust correct for issues such as those just mentionedyMust correct for issues such as those just mentionedy Accurate to +/‐ 25ms without correctionsyCan achieve +/1 1us accuracy with correction yCan achieve +/1 1us accuracy with correction algorithm, if enough satellites are visibleConsequences?y With a cheap GPS rec eiv er, 25ms accuracy, which is large compared to time for exchanging messagesy 10,000 msgs/second on modern platformsy … hence .1ms “data rates”M lk h hi h yMoreover, clocks on cheap machines have 10ms accuracyy But with expensive GPS, we could timestamp as many as 100 000 msgs/secondmany as 100,000 msgs/secondAccuracy and Precisiony Accuracy is a measure of how close a clock is to “true” timePiii f h l f lk yPrecisionis a measure of how close a set of clocks are to one‐anotheryBoth are often expressed in terms of a window and a yBoth are often expressed in terms of a window and a drift rateThought questiony We are building an anti‐missile systemy Radar tells the interceptor where it should be and what time to get theretime to get therey Do we want the radar and interceptor to be as accurate as possible, or as precise as possible?p,p pThought questiony We want them to agree on the time but it isn’t important whether they are accurate with respect to “true” timetrue timey “Precision” matters more than “ac cur acy”yAlthough for this a GPS time source would be the wa y to yAlthough for this, a GPS time source would be the wa y to goy Might achieve higher precision than we can with an “internal” hiti tl!synchronization protocol!Real systems?y Typically, some “master clock” owner periodically broadcasts the timeP h d hi lkyProcesses then update their clocksy But they can drift between updatesyHence we generally treat time as having fairly low yHence we generally treat time as having fairly low accuracyy Often precision will be poor compared to message p p p ground‐trip timesClock synchronizationy To optimize for precision we cany Set all clocks from a GPS source or some other time “b d ” “broadcast” sourcey Limited by uncertainty in downlink timesyOr run a protocol between the machinesOr run a protocol between the machinesy Many have been reported in the literaturey Precision limited by uncertainty in message delaysS bi fil i b f h ySome can even overcome arbitrary failures in a subset of the machines!Adjusting clocks: Not easy!y Suppose the current time is 10:00.00pmy Now we discover we’re wrongy It’s actually 9:59.57pm!y Options:y Set the clock back by 3 seconds…y But what will this do to timers?yImplies a need for a “global time warp”Implies a need for a global time warpy Introduce an artificial time drifty E.g. make clock run slowly for a little whileReal systemsy Many adjust time “abruptly”y Time could seem to freeze for a while, until the clock is t ( if it ft)accurate (e.g. if it was fast)y Or might jump backwards or forw ards with no warning to applicationsppy This