Clock Skew and Drift

Introduction

Every node in a distributed system has a local clock.
These clocks are never perfectly synchronized.
The gap between any two clocks at a given instant is called clock skew.
The rate at which a clock deviates from a reference over time is called clock drift.
These two phenomena are distinct but related, and together they represent one of the most fundamental challenges in distributed computing.

Understanding clock skew and drift is not merely academic.
They directly affect the correctness of protocols that depend on timestamps for ordering events, enforcing lease durations, expiring caches, or detecting failures.
Systems like Google's Spanner, Apache Cassandra, and TLS certificate validation all must account for imperfect clocks.
Getting this wrong leads to subtle, hard-to-reproduce bugs: stale reads, phantom writes, premature lease expirations, and split-brain scenarios.

Physical Clocks and Their Imperfections

Computers typically keep time using a quartz crystal oscillator.
The oscillator vibrates at a nominal frequency, and the operating system counts these vibrations to advance the clock.
The problem is that no oscillator vibrates at exactly its rated frequency.
Temperature fluctuations, voltage variations, aging of the crystal, and manufacturing tolerances all cause the actual frequency to differ from the ideal.

Another source of clock discontinuity worth noting is the leap second.
Because the Earth's rotation is irregular, UTC occasionally inserts or removes a second to stay aligned with solar time.
Leap seconds can cause local clocks to jump or repeat a second, which has historically caused outages in distributed systems unprepared for non-monotonic time.

Drift Rate

The drift rate (often denoted ρ) describes how fast a clock diverges from real time per unit of real time.
A typical quartz oscillator drifts at roughly 10 to 100 parts per million (ppm).
At 100 ppm, a clock gains or loses about 8.6 seconds per day.
Over a week, that is a full minute.

For a clock C(t) representing the local time at real time t, drift is captured by the derivative dC/dt.
A perfect clock has dC/dt = 1.
A drifting clock has dC/dt = 1 + ρ, where ρ is small but nonzero and may vary over time.

Skew

Skew is the instantaneous difference between two clocks.
If nodes A and B have clocks C_A(t) and C_B(t), the skew at time t is C_A(t) - C_B(t).
Skew accumulates as a consequence of differing drift rates.
Even if two clocks are synchronized at time t₀, their skew at time t₀ + Δ is bounded in the worst case by 2ρΔ — this worst case occurs when both clocks drift by the maximum rate ρ in opposite directions.

This distinction matters operationally.
Skew is what you observe and try to correct.
Drift is why skew keeps reappearing after correction.

Clock Synchronization Protocols

Since drift is unavoidable, distributed systems use synchronization protocols to periodically bound skew.

NTP (Network Time Protocol)

NTP is the most widely deployed clock synchronization protocol on the internet.
A client exchanges timestamps with one or more NTP servers and computes the offset between its local clock and the server's clock, accounting for network round-trip time.
NTP achieves synchronization accuracy of roughly 1 to 50 milliseconds on the public internet.
On well-configured LANs, accuracy typically reaches 1 to 10 milliseconds; sub-millisecond accuracy generally requires GPS-disciplined local time servers or hardware-assisted protocols such as PTP.

NTP uses a hierarchical stratum model.
Stratum-0 devices are reference clocks (GPS receivers, and atomic clocks).
Stratum-1 servers synchronize directly to stratum-0 devices.
Stratum-2 servers synchronize to stratum-1, and so on.

PTP (Precision Time Protocol)

IEEE 1588 PTP achieves sub-microsecond synchronization by using hardware timestamping at the network interface.
It requires support from switches and NICs, making it more expensive to deploy but far more accurate.

Cristian's Algorithm and the Berkeley Algorithm

Cristian's algorithm is the simplest synchronization approach: a client asks a time server for the current time, measures the round-trip delay, and estimates the one-way delay as half the round-trip.
This provides accuracy bounded by (RTT/2 - d_min), where d_min is the minimum possible one-way network latency.
When RTT is large or the network is asymmetric, accuracy degrades.

The Berkeley algorithm takes a different approach.
A coordinator polls all nodes, filters out outliers, computes the average time across the remaining nodes, and instructs each node to adjust its clock by the appropriate delta.
This is useful when no single authoritative time source exists, because no node's clock is treated as ground truth.

Walkthrough

The following walkthrough illustrates Cristian's algorithm step by step, including how drift and network delay introduce error.

Cristian's Algorithm: Step-by-Step

1. Client records local time T1.
2. Client sends a time request to the server.
3. Server receives the request. After a small processing delay,
   the server records its current time T_server.
4. Server sends T_server back to the client.
5. Client receives the response at local time T2.
6. Client computes round-trip time: RTT = T2 - T1.
7. Client estimates server's current time as:
       T_estimated = T_server + RTT / 2
   (This assumes symmetric network delay and negligible server
    processing time. Both assumptions introduce error in practice.)
8. Client sets its clock to T_estimated.

Error bound: The true server time when the response arrives is somewhere in the interval [T_server + d_min, T_server + RTT - d_min], where d_min is the minimum possible one-way network delay.
The half-width of this uncertainty interval — and therefore the maximum synchronization error — is (RTT/2 - d_min).
If RTT is large or the network is asymmetric, accuracy degrades significantly.

Drift re-enters the picture: After synchronization, the client's clock immediately begins drifting again.
If the drift rate is ρ and the resynchronization interval is I, the maximum skew that can accumulate before the next sync is ρ × I.
This means the system designer must choose I such that ρ × I remain below the application's tolerance for clock disagreement.

Bounding Skew Between Resyncs

Given:
  ρ     = maximum drift rate (e.g., 200 ppm, accounting for both clocks)
  ε     = synchronization error after each NTP sync
  I     = resynchronization interval

Maximum skew at any point in time:
  skew_max = ε + ρ × I

Example:
  ρ = 200 × 10⁻⁶ (two clocks drifting in opposite directions)
  ε = 10 ms (typical NTP accuracy on a LAN)
  I = 30 seconds

  skew_max = 10 ms + (200 × 10⁻⁶ × 30 s)
           = 10 ms + 6 ms
           = 16 ms

This formula is critical for any system that uses physical timestamps to make ordering or validity decisions.

Practical Consequences

Leases and Timeouts

A lease grants a node exclusive access to a resource for a fixed duration.
If the lease holder's clock runs fast, it may believe the lease is still valid after it has actually expired from the lease grantor's perspective.
Another node may then acquire the lease, leading to two nodes believing they hold it simultaneously.
Google's Chubby lock service explicitly accounts for clock skew by having the client assume its lease expires earlier than the nominal duration.

Last-Write-Wins Conflict Resolution

In systems like Cassandra that use last-write-wins (LWW) conflict resolution, the "winning" write is determined by its timestamp.
If node A's clock is 500 ms ahead of node B's, writes from A will systematically overwrite concurrent writes from B.
This is not a theoretical concern; it is a documented operational problem.

TrueTime in Google Spanner

Spanner's TrueTime API explicitly exposes clock uncertainty.
Instead of returning a single timestamp, TrueTime returns an interval [earliest, latest] that is guaranteed to contain the true time.
Spanner then waits out the uncertainty before committing a transaction, ensuring that if transaction T1 commits before T2 starts, T1's commit timestamp is less than T2's.
This wait (typically a few milliseconds, thanks to GPS and atomic clocks in each datacenter) is the direct cost of clock uncertainty made explicit.

Logical Clocks as an Alternative

Lamport clocks and vector clocks sidestep the problem entirely by tracking causal ordering rather than wall-clock time.
They guarantee that if event A causally precedes event B, then the logical timestamp of A is less than the logical timestamp of B.
This holds regardless of physical clock skew.
The tradeoff is that logical clocks cannot capture real-time ordering between causally unrelated events.
Hybrid logical clocks (HLC) attempt to combine the benefits of both by tracking physical time augmented with a logical component, allowing systems to preserve causality while staying close to wall-clock time.

Measurement and Monitoring

In production systems, clock health should be monitored continuously.
Key metrics include:

• NTP offset: the measured difference between local time and the NTP server. Alerting thresholds typically range from 50 ms to 500 ms depending on the application.
• NTP jitter: the variance in offset measurements, indicating instability.
• Drift rate: can be estimated by measuring offset changes between synchronization cycles.
• Stratum: a sudden increase in NTP stratum may indicate loss of connectivity to accurate time sources.

Tools like chrony provide detailed statistics on drift rate estimation and correction.
On Linux, the kernel's adjtimex system call allows fine-grained control over clock frequency adjustments.

Key Points

• Clock skew is the instantaneous difference between two clocks; clock drift is the rate at which a clock deviates from real time. They are related but distinct.
• Typical quartz oscillators drift at 10 to 100 ppm, accumulating seconds of skew per day without correction.
• NTP bounds skew to single-digit or tens of milliseconds on LANs and up to ~50 ms on the public internet, but cannot eliminate it.
• Maximum skew between synchronization events is bounded by ε + ρ × I, where ε is sync error, ρ is drift rate, and I is the resync interval.
• Leases, LWW conflict resolution, and transaction ordering are all vulnerable to incorrect behavior under clock skew.
• Leap seconds introduce additional discontinuities that distributed systems must handle explicitly.
• Google Spanner's TrueTime makes clock uncertainty explicit and waits it out, converting a correctness problem into a latency cost.
• Logical and hybrid logical clocks offer skew-independent causal ordering but cannot replace physical time for all use cases.

References

Lamport, L. "Time, Clocks, and the Ordering of Events in a Distributed System." Communications of the ACM, 21(7), 1978.

Mills, D. "Internet Time Synchronization: The Network Time Protocol." IEEE Transactions on Communications, 39(10), 1991.

Corbett, J. C., et al. "Spanner: Google's Globally-Distributed Database." Proceedings of OSDI, 2012.

Kulkarni, S., et al. "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases." Proceedings of HotDep, 2014.

Coulouris, G., Dollimore, J., Kindberg, T., and Blair, G. "Distributed Systems: Concepts and Design." 5th Edition, Addison-Wesley, 2011.