Time, Clocks, and the Ordering of Events in a Distributed ...

1 Operating R. Stockton Gaines Systems Editor Time, Clocks, and the Ordering of Events in a Distributed system Leslie Lamport Massachusetts Computer Associates, Inc. The concept of one event happening before another in a Distributed system is examined, and is shown to define a partial Ordering of the Events . A Distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the Events . The use of the total Ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become. Key Words and Phrases: Distributed systems, computer networks, clock synchronization, multiprocess systems CR Categories: , Introduction The concept of time is fundamental to our way of thinking. It is derived from the more basic concept of the order in which Events occur.

2 We say that something happened at 3:15 if it occurred after our clock read 3:15 and before it read 3:16. The concept of the temporal Ordering of Events pervades our thinking about systems. For example, in an airline reservation system we specify that a request for a reservation should be granted if it is made before the flight is filled. However, we will see that this concept must be carefully reexamined when consid- ering Events in a Distributed system . General permission to make fair use in teaching or research of all or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that ACM's copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery. To otherwise reprint a figure, table, other substantial excerpt, or the entire work requires specific permission as does republication, or systematic or multiple reproduc- tion.

3 This work was supported by the Advanced Research Projects Agency of the Department of Defense and Rome Air Development Center. It was monitored by Rome Air Development Center under contract number F 30602-76-C-0094. Author's address: Computer Science Laboratory, SRI Interna- tional, 333 Ravenswood Ave., Menlo Park CA 94025. 1978 ACM 0001-0782/78/0700-0558 $ 558 A Distributed system consists of a collection of distinct processes which are spatially separated, and which com- municate with one another by exchanging messages. A network of interconnected computers, such as the ARPA net, is a Distributed system . A single computer can also be viewed as a Distributed system in which the central control unit, the memory units, and the input-output channels are separate processes. A system is Distributed if the message transmission delay is not negligible com- pared to the time between Events in a single process.

4 We will concern ourselves primarily with systems of spatially separated computers. However, many of our remarks will apply more generally. In particular, a mul- tiprocessing system on a single computer involves prob- lems similar to those of a Distributed system because of the unpredictable order in which certain Events can occur. In a Distributed system , it is sometimes impossible to say that one of two Events occurred first. The relation "happened before" is therefore only a partial Ordering of the Events in the system . We have found that problems often arise because people are not fully aware of this fact and its implications. In this paper, we discuss the partial Ordering defined by the "happened before" relation, and give a Distributed algorithm for extending it to a consistent total Ordering of all the Events . This algorithm can provide a useful mechanism for implementing a Distributed system .

5 We illustrate its use with a simple method for solving syn- chronization problems. Unexpected, anomalous behav- ior can occur if the Ordering obtained by this algorithm differs from that perceived by the user. This can be avoided by introducing real, physical clocks. We describe a simple method for synchronizing these clocks, and derive an upper bound on how far out of synchrony they can drift. The Partial Ordering Most people would probably say that an event a happened before an event b if a happened at an earlier time than b. They might justify this definition in terms of physical theories of time. However, if a system is to meet a specification correctly, then that specification must be given in terms of Events observable within the system . If the specification is in terms of physical time, then the system must contain real clocks. Even if it does contain real clocks, there is still the problem that such clocks are not perfectly accurate and do not keep precise physical time.

6 We will therefore define the "happened before" relation without using physical clocks. We begin by defining our system more precisely. We assume that the system is composed of a collection of processes. Each process consists of a sequence of Events . Depending upon the application, the execution of a subprogram on a computer could be one event, or the execution of a single machine instruction could be one Communications July 1978 of Volume 21 the ACM Number 7 Fig. 1. a, CY ,Y (9 (9 ~o ~ o P4' P3 P2' Pl ~ q7 q6 q5 ql r 4 r 3 r 2 r 1 event. We are assuming that the Events of a process form a sequence, where a occurs before b in this sequence if a happens before b. In other words, a single process is defined to be a set of Events with an a priori total Ordering . This seems to be what is generally meant by a process.~ It would be trivial to extend our definition to allow a process to split into distinct subprocesses, but we will not bother to do so.))

7 We assume that sending or receiving a message is an event in a process. We can then define the "happened before" relation, denoted by "---~", as follows. Definition. The relation "---->" on the set of Events of a system is the smallest relation satisfying the following three conditions: (1) If a and b are Events in the same process, and a comes before b, then a ~ b. (2) If a is the sending of a message by one process and b is the receipt of the same message by another process, then a ~ b. (3) If a ~ b and b ~ c then a ---* c. Two distinct Events a and b are said to be concurrent if a ~ b and b -/-* a. We assume that a ~ a for any event a. (Systems in which an event can happen before itself do not seem to be physically meaningful.) This implies that ~ is an irreflexive partial Ordering on the set of all Events in the system . It is helpful to view this definition in terms of a "space-time diagram" such as Figure 1.

8 The horizontal direction represents space, and the vertical direction represents time--later times being higher than earlier ones. The dots denote Events , the vertical lines denote processes, and the wavy lines denote messagesfl It is easy to see that a ~ b means that one can go from a to b in ' The choice of what constitutes an event affects the Ordering of Events in a process. For example, the receipt of a message might denote the setting of an interrupt bit in a computer, or the execution of a subprogram to handle that interrupt. Since interrupts need not be handled in the order that they occur, this choice will affect the order- ing of a process' message-receiving Events . 2 Observe that messages may be received out of order. We allow the sending of several messages to be a single event, but for convenience we will assume that the receipt of a single message does not coincide with the sending or receipt of any other message.

9 559 Fig. 2. cy c~ (9 (9 ~) O O U -2 - - - q6 -- ;#.i Y _ P3' ~ ~ ~ ~ ~ _~~-~ r3 the diagram by moving forward in time along process and message lines. For example, we have p, --~ r4 in Figure 1. Another way of viewing the definition is to say that a --) b means that it is possible for event a to causally affect event b. Two Events are concurrent if neither can causally affect the other. For example, Events pa and q:~ of Figure 1 are concurrent. Even though we have drawn the diagram to imply that q3 occurs at an earlier physical time than 1)3, process P cannot know what process Q did at qa until it receives the message at p, (Before event p4, P could at most know what Q was planning to do at q:~.) This definition will appear quite natural to the reader familiar with the invariant space-time formulation of special relativity, as described for example in [1] or the first chapter of [2]. In relativity, the Ordering of Events is defined in terms of messages that could be sent.

10 However, we have taken the more pragmatic approach of only considering messages that actually are sent. We should be able to determine if a system performed correctly by knowing only those Events which did occur, without knowing which Events could have occurred. Logical Clocks We now introduce clocks into the system . We begin with an abstract point of view in which a clock is just a way of assigning a number to an event, where the number is thought of as the time at which the event occurred. More precisely, we define a clock Ci for each process Pi to be a function which assigns a number Ci(a) to any event a in that process. The entire system ofclbcks is represented by the function C which assigns to any event b the number C(b), where C(b) = C/(b) ifb is an event in process Pj. For now, we make no assumption about the relation of the numbers Ci(a) to physical time, so we can think of the clocks Ci as logical rather than physical clocks.