Time in Distributed Systems: Physical Clock Skew, NTP Drift, and Lamport Timestamps

Why You Need This in Real Life

At 11:42:00.100 AM, User A deposits $100 into a distributed bank account on Node 1. At 11:42:00.105 AM (5 milliseconds later), User A withdraws$100 on Node 2.

Both database nodes use Last-Write-Wins (LWW) resolution based on local hardware system clocks. But Node 2’s physical clock drifts backward by 12 milliseconds due to Network Time Protocol (NTP) synchronization adjustments.

Node 2 stamps the withdrawal with timestamp 11:42:00.093 AM.

When the database nodes sync records, Node 1 compares the timestamps: 093 AM (withdrawal) is smaller than 100 AM (deposit). The database assumes the withdrawal occurred before the deposit, rejects the transaction for insufficient funds, and logs a corrupt transaction sequence.

Relying on physical system time (System.currentTimeMillis()) to determine event order across independent servers is one of the most dangerous anti-patterns in distributed engineering.

To guarantee accurate event causality, Leslie Lamport invented Logical Clocks.

---

Part 1: Why Physical Clocks Fail in Distributed Systems

Every server node contains a hardware quartz crystal oscillator that ticks at a specific frequency to track time. However, quartz crystals are physically imperfect:

• Thermal Drift: Temperature fluctuations inside server racks cause crystal oscillation speeds to change.
• Clock Skew & Drift: Two identical servers sitting side-by-side will drift apart by 1 to 2 milliseconds per day.

Node 1 Physical Clock:  12:00:00.000  --->  12:00:01.002 (Drifts fast)
Node 2 Physical Clock:  12:00:00.000  --->  12:00:00.998 (Drifts slow)
                                            -----------------------
                                            Clock Skew Delta = 4ms!

Network Time Protocol (NTP) Limits

Servers use NTP to synchronize physical time with atomic clocks via network packets. However, NTP cannot eliminate physical time uncertainty:

• Asymmetric Network Latency: NTP assumes outbound and return network packet transit times are identical. If inbound routes take longer than outbound routes, NTP miscalculates clock drift.
• NTP Stepping vs Smearing: When NTP detects a large clock delta (e.g., 500ms), it either jumps time backward abruptly (stepping—breaking monotonic time) or slows down the clock rate (smearing).

Because physical time is inherently uncertain ($\pm 10\text{ms}$ to $\pm 100\text{ms}$ error windows), distributed systems cannot use wall-clock timestamps to establish absolute event ordering.

---

Part 2: Leslie Lamport’s Happened-Before Relation ($\rightarrow$)

In his seminal 1978 paper “Time, Clocks, and the Ordering of Events in a Distributed System”, Leslie Lamport demonstrated that ordering does not require physical time. It only requires tracking causal relationships (which event happened before another).

He defined the Happened-Before Relation ($\rightarrow$):

1. Local Process Rule: If events $a$ and $b$ occur within the same process, and $a$ occurs before $b$, then $a \rightarrow b$.
2. Message Passing Rule: If event $a$ is the sending of a message by one process, and event $b$ is the receipt of that message by another process, then $a \rightarrow b$.
3. Transitivity Rule: If $a \rightarrow b$ and $b \rightarrow c$, then $a \rightarrow c$.

If neither $a \rightarrow b$ nor $b \rightarrow a$ is true, events $a$ and $b$ are concurrent ($a \parallel b$).

Process P1:   e11 -------> e12 (Send M1)
                             \
                              \  Message M1
                               v
Process P2:                 e21 (Receive M1) -------> e22

Causality Graph: e11 -> e12 -> e21 -> e22

---

Part 3: Lamport Logical Timestamps Algorithm

A Lamport Timestamp is a simple monotonically increasing integer counter maintained by each node without hardware clock interaction.

Algorithm Rules

1. Each process $P_i$ maintains a local integer counter $L_i$, initialized to 0.
2. Before executing a local event, process $P_i$ increments its counter: $L_i = L_i + 1$
3. When sending a message, $P_i$ includes its updated counter $L_i$ in the message payload.
4. When receiving a message with timestamp $L_{\text{msg}}$, process $P_j$ updates its local counter: $L_j = \max(L_j, L_{\text{msg}}) + 1$

Process 1 (L1)          Process 2 (L2)
    |                       |
  Local e11 (L1=1)          |
    |                       |
  Send M1 (L1=2) ---------> | (Msg contains L=2)
    |                       Receive M1: L2 = max(0, 2) + 1 = 3
    |                       Local e21 (L2=3)
    v                       v

---

Part 4: Runnable Java Implementation of Lamport Timestamps

package com.example.clock;

import java.util.concurrent.atomic.AtomicInteger;

public class LamportClock {

    private final AtomicInteger counter = new AtomicInteger(0);

    // 1. Triggered on local internal process events
    public int tick() {
        return counter.incrementAndGet();
    }

    // 2. Triggered before sending a network message
    public int sendEvent() {
        return counter.incrementAndGet();
    }

    // 3. Triggered upon receiving a network message with remote timestamp
    public int receiveEvent(int remoteTimestamp) {
        while (true) {
            int current = counter.get();
            int next = Math.max(current, remoteTimestamp) + 1;
            if (counter.compareAndSet(current, next)) {
                return next;
            }
        }
    }

    public int getValue() {
        return counter.get();
    }
}

---

Part 5: Limitations of Lamport Timestamps

While Lamport Timestamps guarantee that if $a \rightarrow b$, then $L(a) < L(b)$, the reverse is NOT true:

$\text{If } L(a) < L(b) \nRightarrow a \rightarrow b$

If $L(a) = 2$ on Node 1 and $L(b) = 3$ on Node 2, you cannot determine whether $a$ caused $b$ or if $a$ and $b$ were independent concurrent events.

To detect true concurrency and causal independence, distributed systems require Vector Clocks.

---

Next Steps

Now that we understand physical clock drift and Lamport Timestamps, we will explore Vector Clocks and causal consistency in Part 3, dissecting how systems like DynamoDB detect and resolve concurrent write conflicts.

References & Further Reading

1. Lamport, L. (1978). Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM, 21(7), 558–565.
2. Fidge, C. (1988). Timestamps in Message-Passing Systems That Preserve the Partial Ordering. Proceedings of Australian Computer Science Conference.
3. Mattern, F. (1989). Virtual Time and Global States of Distributed Systems. Parallel and Distributed Algorithms, 215–226.

---