Time Synchronization in Distributed Systems

Why Time Is Hard in Distributed Systems

In a distributed system, there is no single global clock. Every machine has its own clock, and those clocks inevitably drift apart — even with NTP synchronization, clocks across a data center can differ by tens to hundreds of milliseconds. This makes ordering events from different machines fundamentally difficult.

The Problem: Clock Skew

Imagine two servers, A and B. Server A processes an event at T=100ms, then sends a message to B. B processes a reply at T=90ms (its clock is slightly behind). Naively, B's event appears to have happened before A's original event — a causality violation. This breaks assumptions that many algorithms depend on.

Logical Clocks: Lamport Timestamps

Leslie Lamport's 1978 solution: replace physical time with a logical counter that tracks causal order:

# Each process maintains a counter L
# Rules:
# 1. Increment L before every event
# 2. When sending a message, include current L
# 3. When receiving a message with timestamp T:
#    L = max(L, T) + 1

class LamportClock:
    def __init__(self):
        self.time = 0

    def tick(self):
        self.time += 1
        return self.time

    def update(self, received_time: int) -> int:
        self.time = max(self.time, received_time) + 1
        return self.time

Lamport clocks guarantee: if event A caused event B, then L(A) < L(B). But the converse is not true — two events with L(X) < L(Y) may be causally unrelated.

Vector Clocks

Vector clocks extend Lamport clocks to track causality completely. Each process maintains a vector of counters, one per process:

# Example with 3 processes (A, B, C)
# A sends message: VC_A = [3, 0, 0]
# B receives it:   VC_B = [max(0,3)+0, 1, 0] = [3, 1, 0]
# Now we know B's event happened after A's event at [3,0,0]

Vector clocks allow determining whether events are concurrent (neither caused the other) or ordered. Used in Amazon DynamoDB, Riak, and version control systems.

Hybrid Logical Clocks (HLC)

Hybrid Logical Clocks combine physical time with logical counters to get the best of both worlds — real timestamps while maintaining causal ordering even when physical clocks drift:

# HLC format: (physical_time, logical_counter)
# Events: (T=1000ms, L=0), (T=1000ms, L=1), (T=1001ms, L=0)
# Used by: CockroachDB, YugabyteDB

TrueTime: Google's Approach

Google's Spanner database uses TrueTime, which provides time as an interval [earliest, latest] rather than a point. Using GPS and atomic clocks in every data center, the uncertainty interval is kept under 7 milliseconds. Spanner waits out the uncertainty interval before committing transactions to guarantee global consistency.

Practical Recommendations

Use NTP with multiple sources and monitor clock drift
Include timestamps in all messages for debugging
Use vector clocks or HLC for systems where causal ordering matters
Design your system to tolerate clock skew — never assume two events with close timestamps are ordered correctly