Each process executes on a single processor, and the processors do not share memory (Chapter 6 briefly considered the case of processes that share memory). Each process pi in has a state si that, in general, it transforms as it executes. The process’s state includes the values of all the variables within it. Its state may also include the values of any objects in its local operating system environment that it affects, such as files. We assume that processes cannot communicate with one another in any way except by sending messages through the network.
So, for example, if the processes operate robot arms connected to their respective nodes in the system, then they
are not allowed to communicate by shaking one another’s robot hands! As each process pi executes it takes a series of actions, each of which is either amessage send or receive operation, or an operation that transforms pi ’s state – one that
changes one or more of the values in si. In practice, we may choose to use a high-leveldescription of the actions, according to the application. For example, if the processes in are engaged in an eCommerce application, then the actions may be ones such as ‘client dispatched order message’ or ‘merchant server recorded transaction to log’.
We define an event to be the occurrence of a single action that a process carries out as it executes – a communication action or a state-transforming action. The sequence of events within a single process pi can be placed in a single, total ordering, which we denote by the relation i between the events.
That is, if and only if the event e occurs before e at pi . This ordering is well defined, whether or not the process is multithreaded,
since we have assumed that the process executes on a single processor. Now we can define the history of process pi to be the series of events that take place within it, ordered as we have described by the relation Clocks • We have seen how to order the events at a process, but not how to timestamp them – i.e., to assign to them a date and time of day. Computers each contain their own physical clocks. These clocks are electronic devices that count oscillations occurring in a crystal at a definite frequency, and typically divide this count and store the result in a counter register. Clock devices can be programmed to generate interrupts at regular intervals in order that, for example, timeslicing can be implemented; however, we shall not concern ourselves with this aspect of clock operation.
The operating system reads the node’s hardware clock value, Hi t , scales it and adds an offset so as to produce a software clock Ci t = Hi t + that approximately measures real, physical time t for process pi . In other words, when the real time in an absolute frame of reference is t, Ci t is the reading on the software clock. For example,
Ci t could be the 64-bit value of the number of nanoseconds that have elapsed at time t since a convenient reference time. In general, the clock is not completely accurate, so Ci t will differ from t. Nonetheless, if Ci behaves sufficiently well (we shall examine the notion of clock correctness shortly), we can use its value to timestamp any event at pi . Note that successive events will correspond to different timestamps only if the clock resolution – the period between updates of the clock value – is smaller than the time interval between successive events. The rate at which events occur depends on such factors as the length of the processor instruction cycle.
Clock skew and clock drift • Computer clocks, like any others, tend not to be in perfect agreement
Coordinated Universal Time • Computer clocks can be synchronized to external sources of highly accurate time. The most accurate physical clocks use atomic oscillators, whose
drift rate is about one part in 1013. The output of these atomic clocks is used as the standard second has been defined as 9,192,631,770 periods of transition between the two hyperfine levels of the ground state of Caesium-133 (Cs133).
Seconds and years and other time units that we use are rooted in astronomical time. They were originally defined in terms of the rotation of the Earth on its axis and its rotation about the Sun.
However, the period of the Earth’s rotation about its axis is gradually getting longer, primarily because of tidal friction; atmospheric effects and convection currents within the Earth’s core also cause short-term increases and decreases in the period. So astronomical time and atomic time have a tendency to get out of step.
Coordinated Universal Time – abbreviated as UTC (from the French equivalent) – is an international standard for timekeeping. It is based on atomic time, but a so-called ‘leap second’ is inserted – or, more rarely, deleted – occasionally to keep it in step with astronomical time. UTC signals are synchronized and broadcast regularly from landbased
radio stations and satellites covering many parts of the world. For example, in the USA, the radio station WWV broadcasts time signals on several shortwave frequencies.
Satellite sources include the Global Positioning System (GPS).Receivers are available commercially. Compared with ‘perfect’ UTC, the signals received from land-based stations have an accuracy on the order of 0.1–10 milliseconds,
depending on the station used. Signals received from GPS satellites are accurate to about 1 microsecond. Computers with receivers attached can synchronize their clocks with these timing signals.
Synchronizing physical clocks
In order to know at what time of day events occur at the processes in our distributed system – for example, for accountancy purposes – it is necessary to synchronize the processes’ clocks, Ci , with an authoritative, external source of time. This is external synchronization. And if the clocks Ci are synchronized with one another to a known degree of accuracy, then we can measure the interval between two events occurring at different computers by appealing to their local clocks, even though they are not necessarily synchronized to an external source of time. This is internal synchronization.We define these two modes of synchronization more closely as follows, over an interval
of real time I:
External synchronization: For a synchronization bound D 0 , and for a source S of UTC time, S t – Ci t < D, for i = 1 2 N and for all real times t in I. Another way of saying this is that the clocks Ci are accurate to within the bound D.
Internal synchronization: For a synchronization bound D 0 , Ci t – Cj t D for i j = 1
2 N , and for all real times t in I. Another way of saying this is that he clocks Ci agree within the bound D. Clocks that are internally synchronized are not necessarily externally synchronized, since they may drift collectively from an external source of time even though they agree with one another. However, it follows from the definitions that if the system is externally synchronized with a bound D then the same system is internally synchronized with a bound of 2D. Various notions of correctness for clocks have been suggested. It is common to define a hardware clock H to be correct if its drift rate falls within a known bound (a value derived from one supplied by the manufacturer, such as 10–6 seconds/second).
This means that the error in measuring the interval between real times t and t ( t t ) is bounded:
1 – t – t H t – H t 1 + t – t
This condition forbids jumps in the value of hardware clocks (during normal operation). Sometimes we also require our software clocks to obey the condition but a weaker condition of monotonicity may suffice. Monotonicity is the condition that a clock C only ever advances: t t C t C t For example, the UNIX make facility is a tool that is used to compile only those source files that have been modified since they were last compiled. The modification dates of each corresponding pair of source and object files are compared to determine this condition. If a computer whose clock was running fast set its clock back after compiling a source file but before the file was changed, the source file might appear to have been modified prior to the compilation. Erroneously, make will not recompile the source file.
We can achieve monotonicity despite the fact that a clock is found to be running fast. We need only change the rate at which updates are made to the time as given to applications. This can be achieved in software without changing the rate at which the underlying hardware clock ticks – recall that Ci t = Hi t + , where we are free to
choose the values of and . A hybrid correctness condition that is sometimes applied is to require that a clock
obeys the monotonicity condition, and that its drift rate is bounded between synchronization points, but to allow the clock value to jump ahead at synchronization points.
A clock that does not keep to whatever correctness conditions apply is defined to be faulty. A clock’s crash failure is said to occur when the clock stops ticking altogether;
any other clock failure is an arbitrary failure. A historical example of an arbitrary failure is that of a clock with the ‘Y2K bug’, which broke the monotonicity condition by registering the date after 31 December 1999 as 1 January 1900 instead of 2000; another example is a clock whose batteries are very low and whose drift rate suddenly becomes
very large.
Note that clocks do not have to be accurate to be correct, according to the definitions. Since the goal may be internal rather than external synchronization, the criteria for correctness are only concerned with the proper functioning of the clock’s ‘mechanism’, not its absolute setting. We now describe algorithms for external synchronization and for internal
synchronization.
Logical time and logical clocks
From the point of view of any single process, events are ordered uniquely by times shown on the local clock. However, as Lamport [1978] pointed out, since we cannot synchronize clocks perfectly across a distributed system, we cannot in general use physical time to find out the order of any arbitrary pair of events occurring within it. In general, we can use a scheme that is similar to physical causality but that applies in distributed systems to order some of the events that occur at different processes. This ordering is based on two simple and intuitively obvious points: • If two events occurred at the same process pi i = 1 2 N , then they occurred in the order in which pi observes them – this is the order i that we defined above.• Whenever a message is sent between processes, the event of sending the message occurred before the event of receiving the message. Lamport called the partial ordering obtained by generalizing these two relationships the happened-before relation. It is also sometimes known as the relation of causal ordering or potential causal ordering.
We can define the happened-before relation, denoted by , as follows: HB1: If process pi : e i e’, then e e .
HB2: For any message m, send(m) receive(m) – where send(m) is the event of sending the message, and receive(m)
is the event of receiving it. HB3: If e, e and e are events such that e e and e e , then e e .
Totally ordered logical clocks • Some pairs of distinct events, generated by different processes, have numerically identical Lamport timestamps. However, we can create a total order on the set of events
that is, one for which all pairs of distinct events are ordered – by taking into account the identifiers of the processes at which events occur. If e is an event occurring at pi with local timestamp Ti , and e is an event occurring at pj with local timestamp Tj , we define the global logical timestamps for these events to be Ti i and Tj j , respectively. And we define Ti i Tj j if and only if either Ti Tj , or Ti = Tj and i j . This ordering has no general physical significance
(because process identiiers are arbitrary), but it is sometimes useful. Lamport used it, for example, to order the entry of processes to a critical section.
Vector clocks • Mattern [1989] and Fidge [1991] developed vector clocks to overcome the shortcoming of Lamport’s clocks: the fact that from L e L e we cannot conclude that e e . . A vector clock for a system of N processes is an array of N
integers. Each process keeps its own vector clock, Vi , which it uses to timestamp local events. Like Lamport timestamps, processes piggyback vector timestamps on the messages they send to one another, and there are simple rules for updating the clocks:
VC1: Initially, Vi j = 0 , for i j = 1 2 N .
VC2: Just before pi timestamps an event, it sets Vi i :=Vi i + 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 Vi j := max Vi j t j , for j = 1 2 N . Taking the componentwise maximum of two vector timestamps in this way is known as a merge operation.For a vector clock Vi , Vi i is the number of events that pi has timestamped, and Vi j j i is the number of events that have occurred at pj that have potentially affected pi . (Process pj may have timestamped more events by this point, but no information has flowed to pi about them in messages as yet.)
Clocks, Events and Process States
o A distributed system consists of a collection P of N processes pi, i = 1,2,… NEach process pi has a state si consisting of its variables (which it transforms as it executes)
o Processes communicate only by messages (via a network)
o Actions of processes: Send, Receive, change own state
o Event: the occurrence of a single action that a process carries out as it executes
o Events at a single process pi, can be placed in a total ordering denoted by the relation →i between the events. i.e.e →i e’ if and only if event e occurs before event e’ at process pi
o A history of process pi: is a series of events ordered by →i
o history(pi) = hi =<ei0, ei1, ei2, …>
Clocks
To timestamp events, use the computer‘s clock • At real time, t, the OS reads the time on the computer‘s hardware clock Hi(t)
§ It calculates the time on its software clock Ci(t)=αHi(t) + β
o e.g. a 64 bit value giving nanoseconds since some base time
o Clock resolution: period between updates of the clock value
In general, the clock is not completely accurate – but if Ci behaves well enough, it can be used to timestamp events at pi
Skew between computer clocks in a distributed system
Computer clocks are not generally in perfect agreement
Clock skew: the difference between the times on two clocks (at any instant)
Computer clocks use crystal-based clocks that are subject to physical variations
Clock drift: they count time at different rates and so diverge (frequencies of oscillation differ)
Clock drift rate: the difference per unit of time from some ideal reference clock
Ordinary quartz clocks drift by about 1 sec in 11-12 days. (10-6 secs/sec).
High precision quartz clocks drift rate is about 10-7 or 10-8 secs/sec
Coordinated Universal Time (UTC)
UTC is an international standard for time keeping
It is based on atomic time, but occasionally adjusted to astronomical time
International Atomic Time is based on very accurate physical clocks (drift rate 10-13)
It is broadcast from radio stations on land and satellite (e.g.GPS)
Computers with receivers can synchronize their clocks with these timing signals (by requesting time from GPS/UTC source)
Signals from land-based stations are accurate to about 0.1-10 millisecond
Signals from GPS are accurate to about 1 microsecond
