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

Leslie Lamport Massachusetts Computer Associates, Inc.

Copyright © 1978 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org. The definitive version of this paper can be found at ACM's Digital Library.

Abstract

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.

Table of Contents

Introduction
The Partial Ordering
Logical Clocks
Ordering the Events Totally
1. Distributed Mutual Exclusion Problem
2. State Machines
Anomalous Behavior
Physical Clocks
Conclusion
Appendix
Notes
References

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. 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 considering events in a distributed system.

A distributed system consists of a collection of distinct processes which are spatially separated,
and which communicate 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 compared to the time between events in a single process.

We will concern ourselves primarily with systems of spatially separated computers. However, many of our remarks will apply more generally. In particular, a multiprocessing system on a single computer involves problems 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. We illustrate its use with a simple method for solving synchronization problems. Unexpected, anomalous behavior 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. 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 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. [Note] 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.

We assume that sending or receiving a message is an event in a process. We can then define the "happened before" relation, denoted by " $\to$ ", as follows.

Definition. The relation " $\to$ " on the set of events of a system is the smallest relation satisfying the following three conditions:

If $a$ and $b$ are events in the same process, and $a$ comes before $b$ , then $a \to b$ .
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 \to b$ .
If $a \to b$ and $b \to c$ then $a \to 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 $\to$ 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 . 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~~ lines with letters denote messages. [Note] It is easy to see that $a \to b$ means that one can go from $a$ to $b$ in the diagram by moving forward in time along process and message lines. For example, we have $p_{1} \to r_{4}$ in Figure 1 .

Figure 1

Another way of viewing the definition is to say that $a \to 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 $p_{3}$ and $q_{3}$ of Figure 1 are concurrent. Even though we have drawn the diagram to imply that $q_{3}$ occurs at an earlier physical time than $p_{3}$ , process P cannot know what process Q did at $q_{3}$ until it receives the message at $p_{4}$ . (Before event $p_{4}$ , P could at most know what Q was planning to do at $q_{3}$ ).

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. 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 $C_{i}$ for each process $P_{i}$ to be a function which assigns a number $C_{i} ⟨ a ⟩$ to any event $a$ in that process. The entire system of clocks is represented by the function $C$ which assigns to any event $b$ the number $C ⟨ b ⟩$ , where $C ⟨ b ⟩ = C_{j} ⟨ b ⟩$ if $b$ is an event in process $P_{j}$ . For now, we make no assumption about the relation of the numbers $C_{i} ⟨ a ⟩$ to physical time, so we can think of the clocks $C_{i}$ as logical rather than physical clocks. They may be implemented by counters with no actual timing mechanism.

We now consider what it means for such a system of clocks to be correct. We cannot base our definition of correctness on physical time, since that would require introducing clocks which keep physical time. Our definition must be based on the order in which events occur. The strongest reasonable condition is that if an event $a$ occurs before another event $b$ , then $a$ should happen at an earlier time than $b$ . We state this condition more formally as follows.

Note that we cannot expect the converse condition to hold as well, since that would imply that any two concurrent events must occur at the same time. In Figure 1 , $p_{2}$ and $p_{3}$ are both concurrent with $q_{3}$ , so this would mean that they both must occur at the same time as $q_{3}$ , which would contradict the Clock Condition because $p_{2} \to p_{3}$ .

It is easy to see from our definition of the relation " $\to$ " that the Clock Condition is satisfied if the following two conditions hold.

Let us consider the clocks in terms of a space-time diagram. We imagine that a process' clock "ticks" through every number, with the ticks occurring between the process' events. For example, if $a$ and $b$ are consecutive events in process $P_{i}$ with $C_{i} ⟨ a ⟩ = 4$ and $C_{i} ⟨ b ⟩ = 7$ , then clock ticks 5, 6, and 7 occur between the two events. We draw a dashed "tick line" through all the like-numbered ticks of the different processes. The space-time diagram of Figure 1 might then yield the picture in Figure 2 . Condition C1 means that there must be a tick line between any two events on a process line, and condition C2 means that every message line must cross a tick line. From the pictorial meaning of $\to$ , it is easy to see why these two conditions imply the Clock Condition.

Figure 2

We can consider the tick lines to be the time coordinate lines of some Cartesian coordinate system on space-time. We can redraw Figure 2 to straighten these coordinate lines, thus obtaining Figure 3 . Figure 3 is a valid alternate way of representing the same system of events as Figure 2 . Without introducing the concept of physical time into the system (which requires introducing physical clocks), there is no way to decide which of these pictures is a better representation.

Figure 3

The reader may find it helpful to visualize a two-dimensional spatial network of processes, which yields a three-dimensional space-time diagram. Processes and messages are still represented by lines, but tick lines become two-dimensional surfaces.

Let us now assume that the processes are algorithms, and the events represent certain actions during their execution. We will show how to introduce clocks into the processes which satisfy the Clock Condition . Process $P_{i}$ 's clock is represented by a register $C_{i}$ , so that $C_{i} ⟨ a ⟩$ is the value contained by $C_{i}$ during the event $a$ . The value of $C_{i}$ will change between events, so changing $C_{i}$ does not itself constitute an event.

To guarantee that the system of clocks satisfies the Clock Condition , we will insure that it satisfies conditions C1 and C2 . Condition C1 is simple; the processes need only obey the following implementation rule:

To meet condition C2 , we require that each message $m$ contain a timestamp $T_{m}$ which equals the time at which the message was sent. Upon receiving a message timestamped $T_{m}$ , a process must advance its clock to be later than $T_{m}$ . More precisely, we have the following rule.

2. Sender
  
  Receiver

In IR2(b) we consider the event which represents the receipt of the message $m$ to occur after the setting of $C_{j}$ . (This is just a notational nuisance, and is irrelevant in any actual implementation.) Obviously, IR2 insures that C2 is satisfied. Hence, the simple implementation rules IR1 and IR2 imply that the Clock Condition is satisfied, so they guarantee a correct system of logical clocks.

Ordering the Events Totally

We can use a system of clocks satisfying the Clock Condition to place a total ordering on the set of all system events. We simply order the events by the times at which they occur. To break ties, we use any arbitrary total ordering $≺$ of the processes. More precisely, we define a relation $\Rightarrow$ as follows: if $a$ is an event in process $P_{i}$ and $b$ is an event in process $P_{j}$ , then $a \Rightarrow b$ if and only if either

$C_{i} ⟨ a ⟩ < C_{j} ⟨ b ⟩$ or
$C_{i} ⟨ a ⟩ = C_{j} ⟨ b ⟩$ and $P_{i} ≺ P_{j}$ .

P_{1} ≺ P_{2} ≺ P_{3}

a \Rightarrow c \Rightarrow d \Rightarrow e \Rightarrow b

It is easy to see that this defines a total ordering, and that the Clock Condition implies that if $a \to b$ then $a \Rightarrow b$ . In other words, the relation $\Rightarrow$ is a way of completing the "happened before" partial ordering to a total ordering. [Note]

The ordering $\Rightarrow$ depends upon the system of clocks $C_{i}$ , and is not unique. Different choices of clocks which satisfy the Clock Condition yield different relations $\Rightarrow$ . Given any total ordering relation $\Rightarrow$ which extends $\to$ , there is a system of clocks satisfying the Clock Condition which yields that relation. It is only the partial ordering $\to$ which is uniquely determined by the system of events.

Mutual Exclusion Problem

Being able to totally order the events can be very useful in implementing a distributed system. In fact, the reason for implementing a correct system of logical clocks is to obtain such a total ordering. We will illustrate the use of this total ordering of events by solving the following version of the mutual exclusion problem. Consider a system composed of a fixed collection of processes which share a single resource. Only one process can use the resource at a time, so the processes must synchronize themselves to avoid conflict. We wish to find an algorithm for granting the resource to a process which satisfies the following three conditions:

We assume that the resource is initially granted to exactly one process.

These are perfectly natural requirements. They precisely specify what it means for a solution to be correct. [Note] Observe how the conditions involve the ordering of events. Condition II says nothing about which of two concurrently issued requests should be granted first.

It is important to realize that this is a nontrivial problem. Using a central scheduling process which grants requests in the order they are received will not work, unless additional assumptions are made.

To see this, let $P_{0}$ be the scheduling process.
Suppose $P_{1}$ sends a request to $P_{0}$ and then sends a message to $P_{2}$ .
Upon receiving the latter message, $P_{2}$ sends a request to $P_{0}$ .

It is possible for $P_{2}$ 's request to reach $P_{0}$ before $P_{1}$ 's request does. Condition II is then violated if $P_{2}$ 's request is granted first.

To solve the problem, we implement a system of clocks with rules IR1 and IR2 , and use them to define a total ordering $\Rightarrow$ of all events. This provides a total ordering of all request and release operations. With this ordering, finding a solution becomes a straightforward exercise. It just involves making sure that each process learns about all other processes' operations.

To simplify the problem, we make some assumptions. They are not essential, but they are introduced to avoid distracting implementation details. We assume first of all that any two processes $P_{i}$ and $P_{j}$ , the messages sent from $P_{i}$ to $P_{j}$ are received in the same order as they are sent. Moreover, we assume that every message is eventually received. (These assumptions can be avoided by introducing message numbers and message acknowledgement protocols.) We also assume that a process can send messages directly to every other process.

Each process maintains its own request queue which is never seen by any other process. We assume that the request queues initially contain the single message $" T_{0} : P_{0} requests resource "$ , where $P_{0}$ is the process initially granted the resource and $T_{0}$ is less than the initial value of any clock.

The algorithm is then defined by the following five rules. For convenience, the actions defined by each rule are assumed to form a single event.

To request the resource, process $P_{i}$ sends the message $" T_{m} : P_{i} requests resource "$ to every other process, and puts that message on its request queue, where $T_{m}$ is the timestamp of the message.

Click the lock to request the resource.
Click the letter icon to receive the message.
Click the lock to release the resource.
Click the letter icon to receive the message.

Note that conditions (i) and (ii) of rule 5 are tested locally by $P_{i}$ .

Simulation of 3 processes in the mutual exclusion problem.

It is easy to verify that the algorithm defined by these rules satisfies conditions I-III . First of all, observe that condition (ii) of rule 5 , together with the assumption that messages are received in order, guarantees that $P_{i}$ has learned about all requests which preceded its current request. Since rules 3 and 4 are the only ones which delete messages from the request queue, it is then easy to see that condition I holds. Condition II follows from the fact that the total ordering $\Rightarrow$ extends the partial ordering $\to$ . Rule 2 guarantees that after $P_{i}$ requests the resource, condition (ii) of rule 5 will eventually hold. Rules 3 and 4 imply that if each process which is granted the resource eventually releases it, then condition (i) of rule 5 will eventually hold, thus providing condition III .

State Machines

This is a distributed algorithm. Each process independently follows these rules, and there is no central synchronizing process or central storage. This approach can be generalized to implement any desired synchronization for such a distributed multiprocess system. The synchronization is specified in terms of a State Machine, consisting of a set $𝐂$ of possible commands, a set $𝐒$ of possible states, and a function $𝐞 : 𝐂 ⨉ 𝐒 \to 𝐒$ . The relation $𝐞 (C, S) = S'$ means that executing the command $C$ with the machine in state $S$ causes the machine state to change to $S'$ . In our example, the set $𝐂$ consists of all the commands $" P_{i} requests resource "$ and $" P_{i} releases resource "$ , and the state consists of a queue of waiting request commands, where the request at the head of the queue is the currently granted one. Executing a request command adds the request to the tail of the queue, and executing a release command removes a command from the queue. [Note]

Each process independently simulates the execution of the State Machine, using the commands issued by all the processes. Synchronization is achieved because all processes order the commands according to their timestamps (using the relation $\Rightarrow$ ), so each process uses the same sequence of commands. A process can execute a command timestamped $T$ when it has learned of all commands issued by all other processes with timestamps less than or equal to $T$ . The precise algorithm is straight-forward, and we will not bother to describe it.

This method allows one to implement any desired form of multiprocess synchronization in a distributed system. However, the resulting algorithm requires the active participation of all the processes. A process must know all the commands issued by other processes, so that the failure of a single process will make it impossible for any other process to execute State Machine commands, thereby halting the system.

The problem of failure is a difficult one, and it is beyond the scope of this paper to discuss it in any detail. We will just observe that the entire concept of failure is only meaningful in the context of physical time. Without physical time, there is no way to distinguish a failed process from one which is just pausing between events. A user can tell that a system has "crashed" only because he has been waiting too long for a response. A method which works despite the failure of individual processes or communication lines is described in [3] .

Anomalous Behavior

Our resource scheduling algorithm ordered the requests according to the total ordering $\Rightarrow$ . This permits the following type of "anomalous behavior." Consider a nationwide system of interconnected computers. Suppose a person issues a request $𝙰$ on a computer A, and then telephones a friend in another city to have him issue a request $𝙱$ on a different computer B. It is quite possible for request $𝙱$ to receive a lower timestamp and be ordered before request $𝙰$ . This can happen because the system has no way of knowing that $𝙰$ actually preceded $𝙱$ , since that precedence information is based on messages external to the system.

Let us examine the source of the problem more closely. Let $𝓈$ be the set of all system events. Let us introduce a set of events which contains the events in $𝓈$ together with all other relevant external events, such as the phone calls in our example. Let $➡$ denote the "happened before" relation for $𝒮$ . In our example, we had $𝙰 ➡ 𝙱$ , but $𝙰 ↛ 𝙱$ . It is obvious that no algorithm based entirely upon events in $𝓈$ , and which does not relate those events in any way with the other events in $𝒮$ , can guarantee that request $𝙰$ is ordered before request $𝙱$ .

There are two possible ways to avoid such anomalous behavior. The first way is to explicitly introduce into the system the necessary information about the ordering $➡$ . In our example, the person issuing request $𝙰$ could receive the timestamp $T_{𝙰}$ of that request from the system. When issuing request $𝙱$ , his friend could specify that $𝙱$ be given a timestamp later than $T_{𝙰}$ . This gives the user the responsibility for avoiding anomalous behavior.

The second approach is to construct a system of clocks which satisfies the following condition.

This is stronger than the ordinary Clock Condition because $➡$ is a stronger relation than $\to$ . It is not in general satisfied by our logical clocks.

Let us identify $𝒮$ with some set of "real" events in physical space-time, and let $➡$ be the partial ordering of events defined by special relativity. One of the mysteries of the universe is that it is possible to construct a system of physical clocks which, running quite independently of one another, will satisfy the Strong Clock Condition . We can therefore use physical clocks to eliminate anomalous behavior. We now turn our attention to such clocks.

Physical Clocks

Let us introduce a physical time coordinate into our space-time picture, and let $C_{i} (t)$ denote the reading of the clock $C_{i}$ at physical time $t$ . [Note] For mathematical convenience, we assume that the clocks run continuously rather than in discrete "ticks." (A discrete clock can be thought of as a continuous one in which there is an error of up to $\frac{1}{2}$ "tick" in reading it.) More precisely, we assume that $C_{i} (t)$ is a continuous, differentiable function of $t$ except for isolated jump discontinuities where the clock is reset. Then $\frac{d C_{i} (t)}{dt}$ represents the rate at which the clock is running at time $t$ .

Clock

\frac{d C_{i} (t)}{dt} = 1.00

t = 0.0s

Example of a physical clock

In order for the clock $C_{i}$ to be a true physical clock, it must run at approximately the correct rate. That is, we must have $\frac{d C_{i} (t)}{dt} \approx 1$ for all $t$ . More precisely, we will assume that the following condition is satisfied:

For typical crystal controlled clocks, $κ \leq 10^{-6}$ .

Clock

\frac{d C_{i} (t)}{dt} = 1.00

κ = 0.20

t = 0.0s

Example of a physical clock

It is not enough for the clocks individually to run at approximately the correct rate. They must be synchronized so that $C_{i} (t) \approx C_{j} (t)$ for all $i$ , $j$ , and $t$ . More precisely, there must be a sufficiently small constant $ε$ so that the following condition holds:

If we consider vertical distance in Figure 2 to represent physical time, then PC2 states that the variation in height of a single tick line is less than $ε$ .

Left Clock

\frac{d C_{1} (t)}{dt} = 1.00

Right Clock

\frac{d C_{2} (t)}{dt} = 1.00

κ = 0.20

t = 0.0s

Example of two independent physical clocks. Hover over a clock to see the other's time.

Since two different clocks will never run at exactly the same rate, they will tend to drift further and further apart. We must therefore devise an algorithm to insure that PC2 always holds. First, however, let us examine how small $κ$ and $ε$ must be to prevent anomalous behavior. We must insure that the system $𝒮$ of relevant physical events satisfies the Strong Clock Condition . We assume that our clocks satisfy the ordinary Clock Condition , so we need only require that the Strong Clock Condition holds when $a$ and $b$ are events in $𝒮$ with $a ↛ b$ . Hence, we need only consider events occurring in different processes.

Let $μ$ be a number such that if event $a$ occurs at physical time $t$ and event $b$ in another process satisfies $a ➡ b$ , then $b$ occurs later than physical time $t + μ$ .

In other words, $μ$ is less than the shortest transmission time for interprocess messages. We can always choose $μ$ equal to the shortest distance between processes divided by the speed of light. However, depending upon how messages in $𝒮$ are transmitted, $μ$ could be significantly larger.

To avoid anomalous behavior, we must make sure that for any $i$ , $j$ , and $t$ : $C_{i} (t + μ) - C_{j} (t) > 0$ . Combining this with PC1 and 2 allows us to relate the required smallness of $κ$ and $ε$ to the value of $μ$ as follows. We assume that when a clock is reset, it is always set forward and never back. (Setting it back would cause C1 to be violated.) PC1 then implies that $C_{i} (t + μ) - C_{i} (t) > (1 - κ) μ$ . Using PC2 , it is then easy to deduce that $C_{i} (t + μ) - C_{j} (t) > 0$ if the following inequality holds: $\frac{ε}{(1 - κ)} \leq μ$ This inequality together with PC1 and PC2 implies that anomalous behavior is impossible.

We now describe our algorithm for insuring that PC2 holds. Let $m$ be a message which is sent at physical time $t$ and received at time $t'$ . We define $v_{m} = t' - t$ to be the total delay of the message $m$ . This delay will, of course, not be known to the process which receives $m$ . However, we assume that the receiving process knows some minimum delay $μ_{m} \geq 0$ such that $μ_{m} \leq v_{m}$ . We call $ξ_{m} = v_{m} - μ_{m}$ the unpredictable delay of the message.

We now specialize rules IR1 and 2 for our physical clocks as follows:

Left Clock

\frac{d C_{1} (t)}{dt} = 1.00

Right Clock

\frac{d C_{2} (t)}{dt} = 1.20

Message Links

μ_{m} = 0.20s

ξ_{m} = 0.20s

t = 0.0s

Simulation of two physical clocks sending & receiving messages.

Although the rules are formally specified in terms of the physical time parameter, a process only needs to know its own clock reading and the timestamps of messages it receives. For mathematical convenience, we are assuming that each event occurs at a precise instant of physical time, and different events in the same process occur at different times. These rules are then specializations of rules IR1 and IR2 , so our system of clocks satisfies the Clock Condition . The fact that real events have a finite duration causes no difficulty in implementing the algorithm. The only real concern in the implementation is making sure that the discrete clock ticks are frequent enough so C1 is maintained.

We now show that this clock synchronizing algorithm can be used to satisfy condition PC2 .

We assume that the system of processes is described by a directed graph in which an arc from process $P_{i}$ to process $P_{j}$ represents a communication line over which messages are sent directly from $P_{i}$ to $P_{j}$ .
We say that a message is sent over this arc every $𝜏$ seconds if for any $t$ , $P_{i}$ sends at least one message to $P_{j}$ between physical times $t$ and $t + 𝜏$ .

$𝜏$
The diameter of the directed graph is the smallest number $d$ such that for any pair of distinct processes $P_{j}$ , $P_{k}$ , there is a path from $P_{j}$ to $P_{k}$ having at most $d$ arcs.

$d = 5$

In addition to establishing PC2 , the following theorem bounds the length of time it can take the clocks to become synchronized when the system is first started.

THEOREM. Assume a strongly connected graph of processes with diameter $d$ which always obeys rules IR1' and IR2' . Assume that for any message $m$ , $μ_{m} \leq μ$ for some constant $μ$ , and that for all $t \geq t_{0}$ :

PC1 holds.

Then PC2 is satisfied with $ε \approx d (2 κ 𝜏 + ξ)$ for all $t \geq t_{0} + 𝜏 d$ , where the approximations assume $μ + ξ ≪ 𝜏$ .

κ = 0.20

𝜏 = 1.0s

μ = 0.20s

ξ = 1.0s

t = 0.0s

Simulation of a network of clocks synchronizing.

The proof of this theorem is surprisingly difficult, and is given in the Appendix. There has been a great deal of work done on the problem of synchronizing physical clocks. We refer the reader to [4] for an introduction to the subject. The methods describe in the literature are useful for estimating the message delays $μ_{m}$ and for adjusting the clock frequencies $\frac{d C_{i}}{dt}$ (for clocks which permit such an adjustment). However, the requirement that clocks are never set backwards seems to distinguish our situation from ones previously studied, and we believe this theorem to be a new result.

Conclusion

We have seen that the concept of "happening before" defines an invariant partial ordering of the events in a distributed multiprocess system. We described an algorithm for extending that partial ordering to a somewhat arbitrary total ordering, and showed how this total ordering can be used to solve a simple synchronization problem. A future paper will show how this approach can be extended to solve any synchronization problem.

The total ordering defined by the algorithm is somewhat arbitrary. It can produce anomalous behavior if it disagrees with the ordering perceived by the system's users. This can be prevented by the use of properly synchronized physical clocks. Our theorem showed how closely the clocks can be synchronized.

In a distributed system, it is important to realize that the order in which events occur is only a partial ordering. We believe that this idea is useful in understanding any multiprocess system. It should help one to understand the basic problems of multiprocessing independently of the mechanisms used to solve them.

Appendix

Proof of the Theorem

For any $i$ , and $t$ , let us define $C_{i}^{t}$ to be a clock which is set equal to $C_{i}$ at time $t$ and runs at the same rate as $C_{i}$ , but is never reset. In order words,

(1)

for all $t' \geq t$ . Note that

(2)

Suppose process $P_{1}$ at time $t_{1}$ sends a message to process $P_{2}$ which is received at $t_{2}$ with an unpredictable delay $\leq ξ$ , where $t_{0} \leq t_{1} \leq t_{2}$ . Then for all $t \geq t_{2}$ we have:

$C_{2}^{t_{2}} (t)$ $\geq C_{2}^{t_{2}} (t_{2}) + (1 - κ) (t - t_{2})$ by (1) and PC1
$\geq C_{1} (t_{1}) + μ_{m} + (1 - κ) (t - t_{2})$ by IR2' (b)
$= C_{1} (t_{1}) + (1 - κ) (t - t_{1}) - ((t_{2} - t_{1}) - μ_{m}) + κ (t_{2} - t_{1})$
$\geq C_{1} (t_{1}) + (1 - κ) (t - t_{1}) - ξ$

Hence, with these assumptions, for all $t \geq t_{2}$ we have:

(3)

Now suppose that for $i = 1, ..., n$ we have $t_{i} \leq t_{i}^{'} < t_{i + 1}$ , $t_{0} \leq t_{1}$ , and that at time $t_{i}^{'}$ process $P_{i}$ sends a message to process $P_{i + 1}$ which is received at time $t_{i + 1}$ with an unpredictable delay less than $ξ$ . Then repeated application of the inequality (3) yields the following result for $t \geq t_{n + 1}$ .

(4)

From PC1 , IR1' and 2' we deduce that

C_{1} (t_{1}^{'}) \geq C_{1} (t_{1}) + (1 - κ) (t_{1}^{'} - t_{1})

Combining this with (4) and using (2) , we get

(5)

for $t \geq t_{n + 1}$ .

For any two processes $P$ and $P^{'}$ , we can find a sequence of processes $P = P_{0}, P_{1}, ..., P_{n + 1} = P^{'}$ , $n \leq d$ , with communication arcs from each $P_{i}$ to $P_{i + 1}$ . By hypothesis (b) we can find times $t_{i}$ , $t_{i}^{'}$ with $t_{i}^{'} - t_{i} \leq τ$ and $t_{i + 1} - t_{i}^{'} \leq v$ , where $v = μ + ξ$ . Hence, an inequality of the form (5) holds with $n \leq d$ whenever $t \geq t_{1} + d (τ + v)$ . For any $i$ , $j$ and any $t$ , and $t_{1}$ with $t_{1} \geq t_{0}$ and $t \geq t_{1} + d (τ + v)$ we therefore have:

(6)

Now let $m$ be any message timestamped $T_{m}$ , and suppose it is sent at time $t$ and received at time $t^{'}$ . We pretend that $m$ has a clock $C_{m}$ which runs at a constant rate such that $C_{m} (t) = T_{m}$ and $C_{m} (t^{'}) = T_{m} + μ_{m}$ . Then $μ_{m} \leq t^{'} - t$ implies that $\frac{d C_{m}}{d t} \leq 1$ . Rule IR2' (b) simply set $C_{j} (t^{'})$ to $maximum (C_{j} (t^{'} - 0), C_{m} (t^{'}))$ . Hence, clocks are reset only by setting them equal to other clocks.

For any time $t_{x} \geq t_{0} + \frac{μ}{(1 - κ)}$ , let $C_{x}$ be the clock having the largest value at time $t_{x}$ . Since all clocks run at a rate less than $1 + κ$ , we have for all $i$ and all $t \geq t_{x}$ :

(7)

We now consider the following two cases:

In case (i) , (7) simply becomes

(8i)

In case (ii) , since $C_{m} (t_{1}) = C_{q} (t_{1})$ and $\frac{d C_{m}}{dt} \leq 1$ , we have

C_{x} (t_{x}) \leq C_{q} (t_{1}) + (t_{x} - t_{1})

Hence (7) yields

(8ii)

Since $t_{x} \geq t_{0} + \frac{μ}{1 - κ}$ , we get

$C_{q} (t_{x} - \frac{μ}{1 - κ})$ $\leq C_{q} (t_{x}) - μ$ by PC1
$\leq C_{m} (t_{x}) - μ$ by choice of $m$
$\leq C_{m} (t_{x}) - \frac{(t_{x} - t_{1}) μ_{m}}{v_{m}}$ $μ_{m} \leq μ, t_{x} - t_{1} \leq v_{m}$
$= T_{m}$ by definition of $C_{m}$
$= C_{q} (t_{1})$ by IR2' (a)

Hence, $C_{q} (t_{x} - \frac{μ}{1 - κ}) \leq C_{q} (t_{1})$ , so $t_{x} - t_{1} \leq \frac{μ}{1 - κ}$ and thus $t_{1} \geq t_{0}$ .

Letting $t_{1} = t_{x}$ in case (i), we can combine (8i) and (8ii) to deduce that for any $t$ , $t_{x}$ with $t \geq t_{x} \geq t_{0} + \frac{μ}{1 - κ}$ there is a process $P_{q}$ and a time $t_{1}$ with $t_{x} - \frac{μ}{1 - κ} \leq t_{1} \leq t_{x}$ such that for all $i$ :

(9)

Choosing $t$ and $t_{x}$ with $t \geq t_{x} + d (τ + v)$ , we can combine (6) and (9) to conclude that there exists a $t_{1}$ and a process $P_{q}$ such that for all $i$ :

(10)

Letting $t = t_{x} + d (τ + v)$ , we get

d (τ + v) \leq t - t_{1} \leq d (τ + v) + \frac{μ}{1 - κ}

Combining this with (10) , we get

(11)

Using the hypothesis that $κ ≪ 1$ and $μ \leq v ≪ τ$ , we can rewrite (11) as the following approximate inequality.

(12)

\begin{matrix} C_{q} (t_{1}) + (t - t_{1}) - d (κ τ + ξ) \\ ⪅ C_{i} (t) ⪅ \\ C_{q} (t_{1}) + (t - t_{1}) + d κ τ \end{matrix}

Since this holds for all $i$ , we get

| C_{i} (t) - C_{j} (t) | ⪅ d (2 κ τ + ξ)

and this holds for all $t ⪆ t_{0} + d τ$ . ∎

Note that relation (11) of the proof yields an exact upper bound for $| C_{i} (t) - C_{j} (t) |$ in case the assumption $μ + ξ ≪ τ$ is invalid. An examination of the proof suggests a simple method for rapidly initializing the clocks, or resynchronizing them if they should go out of synchrony for any reason. Each process sends a message which is relayed to every other process. The procedure can be initiated by any process, and requires less than $2 d (μ + ξ)$ seconds to effect the synchronization, assuming each of the messages has an unpredictable delay less than $ξ$ .

Acknowledgement. The use of timestamps to order operations, and the concept of anomalous behavior are due to Paul Johnson and Robert Thomas.

Notes

Go to source.
Go to source.
Go to source.
Go to source.
Go to source.
Go to source.
Go to source.
Go to source.
Go to source.

References