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

lastdance

8页

0次

2021-03-07

100墨值下载

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: 4.32, 5.29

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 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.

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.

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.

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. 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. 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'

P2'

Pl ~

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.

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. 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.

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. 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. They may be implemented by counters with no

actual timing mechanism.

Communications July 1978

of Volume 21

the ACM Number 7

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: 4.32, 5.29

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 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.

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.

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.

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. 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. 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'

P2'

Pl ~

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.

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. 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.

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. 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. They may be implemented by counters with no

actual timing mechanism.

Communications July 1978

of Volume 21

the ACM Number 7

of 8

100墨值下载

database

关注

评论