Chapter 3: Time

Question 1

Real time clock (RTC)

Answer 1

• RTC continuously ticks even when the PC is hibernated or switched off
• Based on alternative power source Referred to as “wall clock” time
• Should not be confused with system clock * Should not be confused with real‐time computing

Question 2

Measuring time: System clock NN

Answer 2

time_t time(time_t * t) Returns the time in number of seconds since 1970‐01‐01

Question 3

CPU time NN

Answer 3

• Time the program spent on the processor
• Processes & threads can be preempted
• According to process, schedule and priorities

Question 4

Unix millennium bug - The Y2038 problem

Answer 4

Affects software and systems that:

• store system time as a signed 32‐bit integer and
• interpret this number as the number of seconds since Thursday, January 1st, 1970
• Represents time until 03:14:07 UTC on Tuesday, January 19th, 2038
• Times beyond “wrap around” & are stored internally as a negative number (int overflow)
• Systems interpret as a date in 1901 rather than 2038!
• Today, affects programs working with future dates (does this matter? 2038?)

Question 5

Other vulnerable systems & expected surprises

Answer 5

Embedded systems

• Telecommunication systems
• Transportation systems
• Flight, automobiles, …. ABS, tracking control, parking aids, …
• As of 2011, most embedded systems use 8‐bit or 16‐bit microprocessors! Y 24 Problem ) more frequently ( sweet
• While our desktops are transitioning to 64‐bit systems

Question 6

Coordinated universal time (UTC)

Answer 6

• Universal
• Usable everywhere in the world
• Independent from time zones
• Converted to local time by adding/subtracting local time zone Coordinated ( = derives from estimtes)
• Several institutions contribute their estimates of current time
• UTC is built by combining these estimatesUTCbased on International Atomic Time (TAI): Time standard based on “average” of signals from400 atomic clocks worldwide

Question 7

From GMT & TAI to UTC

Answer 7

• Observatory in Greenwich derived GMT from astronomical events like the solar day
• UTC is based on a quantum resonance of a caesium atom (therefore, more accurate)
• Atomic second is number of transitions of Caesium 133 atom defined based on mean solar second in its year of introduction
• Caesium clocks around the world report the number of ticks of their clocks to standard body in Paris
• Thus, International Atomic Time (TAI) is derived (mean number of ticks of caesium atom 133 since 1.1.1958)

Question 8

From GMT to UTC NN

Answer 8

• Today, 86400 TAI seconds about 3 ms less than a mean solar day
• 86400 TAI seconds per day vs. change in rotation of earth would eventually have midnight fall in the middle of the day To prevent this, extra seconds are added or removed inside the TAI time‐scale to keep synchronized with GMT
• TAI seconds are constant, leap seconds keep time scales in sync. (atomic vs. solar), giving rise to UTC
• Up to and including 2012, total of 26 leap seconds have been added (most recently on June 30th, 2015)

Question 9

Leap second NN

Answer 9

• During a leap second, either one second is removed from day, or a second is added Happens at the end of the UTC day
• If a leap second is added, time in UTC is specified as 23:59:60, i.e., two seconds from 23:59:59 to 0:00:00 instead of one
• If a leap second is deleted, time jumps from 23:59:58 to 0:00:00 in one second instead of two

Question 10

Notions of time

Answer 10

• Time seen by an external observer
• Global clock of perfect accuracy Time seen on clocks of individual nodes – Each has its own clock
• Clocks may drift out of sync Logical notion of time
• Ordering of events and causality
• Based on information flow about those events

Question 11

Global clock: External time reference

Answer 11

• The “gold standard” against which many protocols are defined Not implementable Use of external time is risky
• Many protocols that seek to provide properties defined by external observers are extremely costly
• Are unable to cope with failures of the synchronization system

Question 12

Time seen on internal clocks

Answer 12

• Most computers have reasonable clocks Clock skew: Instantaneous difference between readings of two clocks
  
  • Clock drift: Rate at which skew increases between a clock and some standard /Rate of change do they separate
• 10‐6 sec/sec for quartz oscillator about 4 ms/hour or 1 sec per 11.6 days

Question 13

Clock synchronization

Answer 13

• Mechanisms to get clocks on different processors to agree on time
  
  • An example of a distributed agreement protocol “Time” is a universal synchronization mechanism Having synchronized clocks makes many things easier
• ​Debugging events in a log
• Email messages and threads of emails on mailing list
• A common point of reference

Question 14

Synchronized time: Systems need it!

Answer 14

• Stock market sale and buy orders and confirmation timestamps
• Network fault isolation, reporting and restore
• Network monitoring, measurement and control
• Distributed multimedia stream synchronization
• Experiment setup, measurement and control
• Cryptographic key management and lifetime control

Question 15

Clock synchronization mechanisms

Answer 15

• Hardware support: Radio receivers, GPS receivers, atomic clocks, shared backplane signals
• Tight synchronization
• Negligible overhead
• Costly (can’t equip every computer with an atomic clock)
• Not possible for all configurations

Question 16

Hardware clock synchronization

Answer 16

• Global positioning system (GPS)
• Broadcast signals via radio waves Backplanes and buses
• Synchronization among processors in chassis
• Tight bounds are possible

Question 17

Software clock synchronization

Answer 17

• Request to reference clock source for time
• Request involves network round trip time (RTT)
• Response is wrong by the time client receives it
• Client must adjust response based on knowledge of network RTT Client -time request-> Server(got UTC) -responste t->

Question 18

Hardware and software clocks

Answer 18

• At real time, t, OS reads time on computer’s hardware clock Hi(t) Calculates time on its software clock: Ci(t)= a * Hi(t) + b (for process i) b = offset a = constant Monotonicity requirement: t’ > t: C(t’) > C(t) =: time monotonously continues
• Can achieve monotonicity with a hardware clock that runs fast by adjusting the values a and b

Question 19

Perfect time NN

Question 20

Clock properties

Answer 20

• Adjusting the clock is not straight forward
• Set clock = new clock value Time must increase monotonically Can’t go back to the past
• Timestamps are important, can’t repeat them Time should not show sudden jumps
• Cannot jump on your way to the future
• Lose the present time & miss a deadline
• External & internal synchronization

Question 21

Probabilistic clock synchronization

Answer 21

By Flaviu Cristian (IBM, 1989) Uses a time server connected to a time reference source (UTC) external Transmission time is unbounded, but usually reasonably short Probabilistic (averaging) algorithm, synchronization is achieved to the degree that network delays are short compared to desired accuracy Primarily intended for operation on LANs Intend is external synchronization

Question 22

Cristian’s Method (1989)

Answer 22

• Client measures round trip time for request to server
• Server responds with time value
• Client assumes transmission delays split equally
• Could factor in time to process request at server Client -dT request ->time-server (need processing time t) -dT response-> (dT+dT = RTT) * t = t+RTT/2

Question 23

Problems with Cristian’s algorithm

Answer 23

• Centralized time server
• Distribution possible via broadcast to many servers Communication with single server is preferred Simpler approach Better estimates based on series of requests Time server is trusted & single point of failure Malicious, failed server would wreak havoc

Question 24

Berkeley algorithm overview

Answer 24

• Clock synchronization algorithm developed in 1989 as part of Berkeley Unix efforts
• Assumes no machine has accurate time source Performs internal synchronization to set clocks of all machines to within a bound
• Intended for use in intranets / LANs Experimentally: Synchronization of clocks to within 20‐25 ms on LAN Summary: Server is chosen (via an election process) Server polls clients who reply with their time Server observes the RTT of the messages and estimates the time of each client and its own Server averages the clock times, ignoring any values it receives far outside the values of the others
• Server sends out the amount (positive or negative) that each client must adjust its clock
• Avoids further uncertainty due to RTT at clients
• Accuracy originally reported was 20‐25 ms (15 nodes)

Question 25

Network time protocol (NTP)

Answer 25

• Provides Coordinated Universal Time (UTC) including scheduled leap second adjustments
• No information about timezones or daylight saving time transmitted (must be obtained separately)
• Time service and dissemination of time over Internet Maintains time to within tens of milliseconds over Internet; achieves 1 millisecond accuracy in LANs under ideal conditions
• Supported by daemon (ntpd) in user space (kernel support) via UDP on port 123

Question 26

Summary on “physical clocks”

Answer 26

• With a receiver, a clock can be synchronized to 1–10s ms of UTC
• Quartz crystal clocks drift 1 micro second per second, about 4 ms per hour
• On a network, computer clocks can be synchronized to within 30 ms of each other (using NTP) In 30 ms, a 32‐bit 2.4 GHz CPU can execute about 720 million instructions

Question 27

Logical clocks

Answer 27

• Key idea is to abandon the idea of physical time Often sufficient to know the order of events
• Lamport (1978) introduced logical (virtual) time and methods to synchronize logical clocks Leslie Lamport, “Time, clocks, and the ordering of events in a distributed system”, Communications of the ACM, Vol. 27, No. 7, July 1978, pp. 558‐565 Won the Dijkstra Prize in Distributed Computing (2000) and the ACM SIGOPS Hall of Fame Award (2007)

Question 28

Events and event ordering

Answer 28

• Often sufficient to know the order of events
• An event may be an instruction execution, method call, order entry, etc.
• Events include message send & receive Within a single process order determined by instruction execution sequence Between two processes on same computer order determined using local physical clock Between two different computers order cannot be determined using local physical clocks, since those clocks cannot be synchronized perfectly

Question 29

The happens‐before relation

Answer 29

• *Describes a causal ordering of events**, denoted by
• *→** If a and b are events in the same process and a occurred before b then a → b

If a is the event of sending a message m in one process and b is the event of receiving m in another process then a → b

The relaton“→” is transitive: If a→ b and b→ c then a → c If neither a → b nor b → a then a and b are concurrent, denoted by a || b abhingig

Question 30

Potential causality & “→” relation

Answer 30

• Intuitively, past events influence future events
• Influence among causally related events is referred to as causal effects
• If a → b, event a (may) causally effects event b
• Concurrent events do not causally affect each other (e.g., neither a → b nor b → a) For any two events a and b, either a→b, b→a, or a||b
• “→” captures flow of data between events, but data may flow in ways other than via message passing
• First event might or might not have caused the second event

Question 31

Lamport clock (logical clock)

Answer 31

• Implementation of clock that tracks “→” numerically
• Each process Pi has a logical clock Ci
• Clock Ci can assign a value Ci(a) to any event a in process Pi
  
  • ​Value Ci(a) is the timestamp of event a in process Pi Timestamps have no relation to physical time, which leads to the term logical clock Logical clocks assign monotonically increasing timestamps
• Can be implemented by a simple counter

Question 32

Correctness condition

Answer 32

Clock condition If a → b then C(a) But not: If C(a) Correctness conditions For any two events a and b in the same process Pi, if a → b then Ci(a) If a is the event of sending a message in process Pi and b is the event of receiving that same message in a different process Pj then Ci(a)

Question 33

Implementation of logical clocks

Answer 33

• Clock Ci must be incremented between any two successive events in process Pi – C = C + d(d > 0, usually 1) If a is the event of sending a message m in process Pi then m is assigned a timestamp
• Tm = Ci(a) When that same message m is received by a different process Pk, Ck is set to a value greater than its present value (prior to the message receipt) and greater than Tm Ck =max{Ck ,Tm} + d(d>0,usually1)

Question 34

Lamport clocks Sketch

Answer 34

• One way relation
• “happens before” send Message (msg: Message) = clock = clock + 1 ​send Over Network (msg, clock) let receiveMessage(msg:Message, cl:Clock) =
• clock = max(clock, cl) + 1

Question 35

Limitation of Logical Clocks

Answer 35

• If C(a) a may or may not happen‐before b
  
  • Example illustrating this limitation C(p0)
• C(p0) One cannot determine whether two events are causally related from timestamps alone

Question 36

Vector clocks

Answer 36

• System with n processes Each process Pi has a clock Ci, which is an integer vector of length n: Ci = ( Ci[1], Ci[2], …, Ci[n] ) Ci(a) is the timestamp (clock value) of event a at process Pi Ci[i], entry i of Ci, is Pi’s logical time
• Ci[i] represents the number of events that process Pi has timestamped * Pi : (Ci[1], …, Ci[i], …, Ci[n])

Question 37

Implementation of vector clocks

Answer 37

• Clock Ci is incremented between any two successive events in process Pi
  
  • Ci[i] = Ci[i] + d (d > 0, usually 1)
• If event a is the event of sending a message m in process Pi, then message m is assigned a vector timestamp Tm = Ci(a)
• When that same message misreceived by a different process Pk, Ck is updated as follows:
• For all p, Ck[p] = max{ Ck[p], Tm[p] }

Question 38

Vector Clock example

Answer 38

• Events p0, p1, q0, and r0 updated by first implementation rule
  
  • Received q1 updated by both implementation rules Received p2 tells P about Q and R R’s clock is old, but better than nothing!

Question 39

Vector clocks example 2

Answer 39

‐ Extension of Lamport clocks‐ Two‐way relation‐ “happened before”‐ “happened after”

Question 40

Comparing vector clocks

Answer 40

• If ta
  
  • ta = tb iff for all i: ta[i] = tb[i]
  • ta ≠ tb iff for any i: ta[i] ≠ tb[i]
  • ta ≤ tb iff for all i: ta[i] ≤ tb[i]
  • ta Overcomes the limitation of logical clocks