Time & Clocks

The Problem with Physical Time

In a single machine, we can confidently use the system clock to determine the order of events. In a distributed system, this is impossible because:

Clocks drift apart.
Network latency is variable, making synchronization imperfect (e.g., NTP).
A node might pause (Garbage Collection, VM migration) and lose track of time.

Clock Offset DistributionThe probability distribution of clock offsets across a cluster of nodes.

✦Intuition

Why time matters

Without a shared notion of time, how do we agree on which user made an update first? How do we detect causality between events across different machines?

Logical Time

Since physical time is unreliable, Leslie Lamport proposed a solution in 1978: Logical Clocks. Instead of measuring absolute time (seconds/minutes), logical clocks measure the ordering of events.

DDefinition 2.1

Happens-Before Relation (→)

An event $A$ happens before event $B$ (written as $A \rightarrow B$ ) if:

$A$ and $B$ occurred on the same process, and $A$ happened before $B$ .
$A$ is the sending of a message by one process, and $B$ is the receipt of that message by another process.
Transitivity: If $A \rightarrow B$ and $B \rightarrow C$ , then $A \rightarrow C$ .

Lamport Timestamps

Each process $P_i$ maintains a local counter, $C_i$ .

Event Ordering with Lamport Clocks

Before executing an event, process $P_i$ increments its counter: $C_i = C_i + 1$ .

When sending a message $m$ , $P_i$ piggybacks its current counter value on the message: $(m, C_i)$ .

Upon receiving a message $(m, C_{msg})$ , a process $P_j$ updates its counter to be greater than both its current value and the message's value: $C_j = \\max(C_j, C_{msg}) + 1$ .

∎

TTheorem 2.2

Lamport Clock Guarantee

If event $a$ happens before event $b$ ( $a \rightarrow b$ ), then the Lamport timestamp of $a$ is strictly less than the Lamport timestamp of $b$ ( $L(a) < L(b)$ ).

!Common pitfall

The Reverse is Not True

If $L(a) < L(b)$ , we cannot conclude that $a \rightarrow b$ . They might be concurrent events that just happened to be assigned these timestamps. This limitation led to the development of Vector Clocks.

← Previous

Introduction & Fallacies

Course Progression

2 of 10

The CAP Theorem