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

Leslie Lamport @ Massachusetts Computer Assoc. Inc.

CACM 1978

Note: In this paper the notation '->' and '=>' are used to denote a partial and total ordering, respectively, between events. So I am using '-->' and '==>' for logical implication and equivalence in this paper.

1. Introduction

Temporal ordering should be reconsidered in distributed systems

Sometimes total ordering is impossible and only partial ordering, therefore, is possible

2. The Partial Ordering

Definition: a -> b = a precedes b in a partial ordering

  1. if a and b are events of the same process and a occurs before b, then a -> b

  2. if a: sending a msg by a process, b: receiving the msg by another process, then a -> b

  3. transitive: if a -> b and b -> c, then a -> c

  4. non-reflective: a -/-> a

  5. if a -/-> b and b -/-> a, then a and b are said to be 'concurrent'

Space-time diagram: see Fig 1 or 2

Horizontal: space, e.g., processes

Vertical: time with later times being higher than earlier ones

Diagonal: msg passing from a process to another

a -> b

event 'a' causally affects event 'b'

there is a path from a to b, following vertical lines and/or message lines

About the reliability of communication: system can be modeled only with actually delivered msgs!

3. Logical Clocks

Logical clock function C(event) = a number assigned by the process in which the event occurs

Clock condition: if a -> b, then C(a) < C(b)

Note: The converse condition does not hold always.

Satisfying the condition ==>

Each process increments its clock between any two successive events, and

Each msg being sent is timestamped with the clock of sender and upon receiving the msg, receiver sets its clock to max(timestamp, clock of receiver) + alpha

4. Ordering the Events Totally

Definition: a => b = total ordering

  1. if C(a) < C(b), then a => b

  2. if C(a) = C(b) and a's process < b's process, then a => b

Note: we assume an arbitrary ordering between processes

An example application of total ordering: mutual exclusion

Requirement:

  1. A resource granted to a process should be released before it could be granted to another process

  2. Different requests for the resource must be granted in the order in which they are made

  3. If every process which is granted the resource eventually releases it, then every request is eventually granted

Caution: a central scheduling process P0 which grants requests in the order they are received

P1 sends a request to P0,

P1 sends a msg to P2, then

P2 sends a request to P0, which happens to arrive before the request from P1

==> violates the requirement (2) & causal ordering

--> Total ordering makes life easy!

Distributed Algorithm: with assumption of reliable stream protocol

To request a resource, broadcast 'req' msg (with the timestamp) and put the req in queue

Upon receiving a 'req', reply ack (with the timestamp) and put the req in queue

To release a resource, remove the corresponding 'req' from the queue and broadcast (timestamped) 'release'

Upon receiving a 'release', remove the corresponding req from queue

The resource is granted if

its 'req' precedes(=>) any 'req' from other processes

this process has received a message from every other process timestamped later than that of its 'req' --> has learned all req which precede its current req

5. Anomalous Behavior: Not anomalous at all!

The system so far does not guarantee to keep the causal ordering between event some of which are out-of-band events, like phone call

Solution

Synchronization by users, or

Physical clock satisfying the strong clock condition:

If a -> b in the set of events possibly containing out-of-band events, C(a) < C(b)

Note that this is actually the requirement for physical clock

6. Physical Clocks

Issues: precision(= granularity of tick) of each clock & synchronization of independent clocks

k = error due to imprecise clock

e = asynchrony of two clocks

How small k and e should be?

Def: u = minimum of the time taken by any out-of-band communication = (shortest distance between 2 processes) / (speed of light)

Necessary condition: C(t + u) > C(t), for any time t

Satisfying the above condition:

  1. Req. for precision: Every clock should tick often enough = differentiable & dC(t)/dt > 0

  2. Algorithm

    Sender sends msg which is timestamped with C(sender) = sender's physical time

    Receiver sets its physical time with max ( C(receiver) at the time of receiving, C(msg) + min msg transfer time )

    If a process does not receive a message at time t, then C(t) should be greater than C(s), t > s

  3. Req. for synchronization: How often messages should be exchanged? Theorem at page 563