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

Purpose

These are notes on Lamport’s 1978 paper. The paper defines what “before” even means in a system with no shared clock, then builds logical clocks that respect that ordering. It closes by deriving how closely physical clocks must be synchronized to avoid ordering anomalies.

Problem

We would like to order the events in a distributed system by when they actually occurred. No process can observe that order directly, since processes only see their own events and the messages they exchange. What we can do is define a partial ordering that captures every ordering the system itself could observe, and then extend it to a total ordering that stays consistent with the partial one.

A partial ordering of objects is a relation that is reflexive, antisymmetric, and transitive. A total ordering is a partial ordering where every pair is comparable, so for any two objects $a$ and $b$, either $a\le b$ or $b\le a$.

Notation

• $a\to b$: event $a$ happened before event $b$.
  • $\to$ is an irreflexive, transitive relation that defines a partial order over the events in the system.
  • If $a$ and $b$ are events in the same process and $a$ comes first, then $a\to b$.
  • If $a$ is the sending of a message and $b$ is the receipt of that message, then $a\to b$.
  • If $a\to b$ and $b\to c$, then $a\to c$.
  • $a\nrightarrow a$.
• $C_i⟨a⟩$: the clock value of process $P_i$ when event $a$ occurs.
• $a\Rightarrow b$: the total order built from the clocks. Break ties with an arbitrary total order $\prec$ on processes (lexicographic order of process identifiers works). For $a$ in $P_i$ and $b$ in $P_j$:

Provided the clocks satisfy the clock condition below, $a\to b⟹a\Rightarrow b$, so the total order extends the partial one. The reverse implication fails, since $\Rightarrow$ also orders concurrent events.

The diagram below shows three processes with local events and two messages. Every path along a process line or a message arrow gives a happened-before chain; events with no such path between them are concurrent.

sequenceDiagram
    participant P1 as Process P1
    participant P2 as Process P2
    participant P3 as Process P3

    Note over P1: a (local event)
    P1->>P2: m1 (send = b, receive = c)
    Note over P3: d (local event)
    Note over P2: e (local event)
    P2->>P3: m2 (send = f, receive = g)
    Note over P3: h (local event)
    Note over P1,P3: a → b → c → e → f → g → h is a happened-before chain
    Note over P1,P3: d is concurrent with a, b, c, e, and f (no message path connects them)

Clock condition

For any events $a,b$: if $a\to b$, then $C⟨a⟩<C⟨b⟩$.

Two implementation rules make this hold. Each process increments its clock between any two of its own events. And when event $a$ sends a message $m$ carrying the timestamp $T_m=C_i⟨a⟩$, the receiving process sets its clock at the receipt event $b$ to some value greater than $T_m$ (and at least its current value).

Synchronized access to a shared resource

The paper uses the total order to solve mutual exclusion. We want an algorithm for granting a resource to processes that satisfies three conditions:

• (I) A process which has been granted the resource must release it before it can be granted to another process.
• (II) Different requests for the resource must be granted in the order in which they are made.
• (III) If every process which is granted the resource eventually releases it, then every request is eventually granted.

Assumptions

For any two processes $P_i$ and $P_j$, messages sent by $P_i$ are received in the order they were sent. Stop-and-wait or sliding window protocols give you this. We also assume every message is eventually received.

The protocol requires active participation from every process. If any one process fails the whole system stops, because a request cannot be granted until every process has responded.

Algorithm

1. To request the resource, process $P_i$ sends a message $T_m:P_i$ request to all other processes and puts that message on its own request queue, where $T_m$ is the current clock value of $P_i$.
2. When process $P_j$ receives $T_m:P_i$ request, it places it on its request queue and sends a reply message to $P_i$ with its current clock value.
3. To release the resource, $P_i$ removes $T_m:P_i$ request from its request queue and sends a release message with its current clock value to all other processes.
4. When process $P_j$ receives a $P_i$ release message, it removes $T_m:P_i$ request from its request queue.
5. $P_i$ is granted the resource when both conditions hold:
   • Its own $T_m:P_i$ request is ordered by $\Rightarrow$ before every other request in its queue.
   • $P_i$ has received a message timestamped later than $T_m$ from every other process.

sequenceDiagram
    participant P1
    participant P2
    participant P3

    Note over P1: enqueue T1:P1 request locally
    P1->>P2: request (T1)
    P1->>P3: request (T1)
    Note over P2: enqueue T1:P1 request
    Note over P3: enqueue T1:P1 request
    P2-->>P1: reply (T2 > T1)
    P3-->>P1: reply (T3 > T1)
    Note over P1: T1:P1 is earliest request in queue and P1 has messages later than T1 from P2 and P3 → granted
    Note over P1: uses the resource
    Note over P1: dequeue T1:P1 request
    P1->>P2: release (T4)
    P1->>P3: release (T4)
    Note over P2: dequeue T1:P1 request
    Note over P3: dequeue T1:P1 request

State machine perspective

The algorithm is an instance of replicated state machines. Take $C$ to be a set of commands and $S$ a set of states, with a transition function

where $e(c,s)=s^{\prime }$ means executing command $c$ in state $s$ moves the machine to state $s^{\prime }$. Here the state is the request queue and the commands are the request and release messages:

Executing $P_i\text{ request}$ adds the request to the queue, and $P_i\text{ release}$ removes it. Each process runs its own copy of the state machine and executes a command timestamped $T$ only once it has received messages with timestamps at least $T$ from every process, which guarantees it has seen every command ordered before $T$. Since every copy executes the same commands in the same total order, every copy stays in agreement.

Anomalous behavior of the total ordering

Consider a nationwide system. A person issues request $a$ at node $A$, then phones a friend in another city who issues request $b$ at node $B$. The total ordering can place $b\Rightarrow a$ even though $a$ was issued first, because the message that establishes the real ordering (the phone call) is external to the system.

Lamport on anomalous behavior ( Time, Clocks, §Anomalous Behavior)

Paraphrasing the paper’s example: in a nationwide network, a user can issue request $a$ at computer $A$, then telephone a friend in another city who issues request $b$ at computer $B$. It is quite possible for $b$ to receive a lower timestamp and be ordered before $a$, because the causal link between them, the phone call, is invisible to the system. The relevant happened-before relation is the one over all events in the world, not just the ones the system can see.

More concretely, let $\mathcal{L}$ be the set of all relevant events in the world and $L$ the set of events inside our system, so $L\subseteq \mathcal{L}$. In the scenario above, $a{\to }_{\mathcal{L}}b$ but $a{\nrightarrow }_{L}b$. No algorithm based solely on the events in $L$, without knowledge of $\mathcal{L}$, can be guaranteed to order $a$ before $b$.

There are two ways out:

1. Users manually carry timestamps across the external channel, so the person at $A$ tells the person at $B$ a timestamp $T_a$ and the second request is issued with a later one. This pushes the burden onto users.
2. Build clocks that satisfy a strong clock condition: if $a{\to }_{\mathcal{L}}b$, then $C⟨a⟩<C⟨b⟩$. This requires physical clocks.

Physical clocks

Let $C_i(t)$ be the value of clock $C_i$ at physical time $t$. Assume $C_i(t)$ is continuous and differentiable except at isolated points where it jumps on reset. A discrete clock fits this model with an error of up to half a tick.

$\frac{d{C}_i(t)}{dt}$ is the rate the clock runs at time $t$, and a perfect clock runs at rate 1. Assume every clock runs at nearly the correct rate:

The paper notes $\kappa \le 10^{-6}$ for typical crystal controlled clocks.

Rate accuracy alone is not enough, since independent clocks drift apart. We also want the clocks synchronized to within some bound $ϵ$:

Physical clocks never run at exactly the same rate, so drift accumulates and a synchronization algorithm has to periodically bring them back within $ϵ$.

Now let $\mu$ be a lower bound on interprocess message delay: if event $a$ occurs at physical time $t$ and event $b$ in another process satisfies $a\to b$, then $b$ occurs after $t+\mu$. To avoid the anomalous behavior above, an event at time $t+\mu$ must get a larger timestamp than any event at time $t$:

The rate bound gives $C_i(t+\mu )-C_i(t)>(1-\kappa )\mu$, and the synchronization bound gives $C_i(t)>C_j(t)-ϵ$. Adding these, $C_i(t+\mu )-C_j(t)>(1-\kappa )\mu -ϵ$, which is positive exactly when

So the required synchronization tightness is set by the minimum message delay. Faster networks demand tighter clocks.

The punchline

$\frac{ϵ}{1-\kappa }\le \mu$: how tightly clocks must be synchronized ($ϵ$) is set by the minimum interprocess message delay ($\mu$), discounted slightly by the clock rate error ($\kappa$). If information can cross the system faster than the clocks agree with each other, anomalous orderings become possible.

Clock synchronization algorithm

Never set a clock backward

Clocks must only ever be adjusted forward. Setting a clock backward can violate the clock condition for events the clock has already timestamped, since a later event could receive a smaller timestamp than an earlier one.

Let $m$ be a message sent at time $t$ and received at time $t^{\prime }$. Let $v_m=t^{\prime }-t$ be the total delay of the message. The receiver does not know $v_m$, but it knows some lower bound ${\mu }_m$ on the delay. Define ${\zeta }_m=v_m-{\mu }_m$ as the unpredictable delay of the message.

The rules for the physical clocks:

1. For each $i$, if $P_i$ does not receive a message at physical time $t$, then $C_i$ is differentiable at $t$ and $\frac{d{C}_i(t)}{dt}>0$.
2. If $P_i$ sends a message $m$ at physical time $t$, then $m$ contains a timestamp $T_m=C_i(t)$. Upon receiving $m$ at physical time $t^{\prime }$, $P_j$ sets $C_j(t^{\prime })=\max ({\lim }_{\delta \to 0}{C}_j(t^{\prime }-\delta ),T_m+{\mu }_m)$.

The paper proves that with these rules, clocks that communicate often enough converge to within an $ϵ$ determined by the unpredictable delay, so the anomaly-freedom condition above can be met.

Sources

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

Related notes

• distributed clocks
• consistent global state
• mutual exclusion
• Synchronizing Access to Shared Objects