Clock synchronization

Deep dive

How it works

Parts:

• Reference — GPS/atomic clock, or a server of lower stratum / better PTP priority.
• Timestamper — user space, kernel (SO_TIMESTAMPING) or NIC/PHY hardware.
• Clock filter — last N samples (NTP: 8), take the minimum-delay one.
• Selector — intersect confidence intervals over servers (Marzullo-style), cluster, combine.
• Servo — PI/PLL/FLL loop slewing phase and frequency; steps only above a threshold (NTP: 125 ms).
• Bound — root delay, dispersion and local offset exported as an error interval.

1. Client stamps t1 and sends; server stamps t2 on receive, t3 on send; client stamps t4.
2. θ = ((t2−t1) + (t3−t4))/2, δ = (t4−t1) − (t3−t2). With one-way delays d1, d2 the error is (d1−d2)/2 and |d1−d2| ≤ δ: ±δ/2, exact if d1 = d2.
3. Queueing only adds delay, so the minimum-δ sample has the tightest bound: use it once, never twice.
4. With several servers each gives θ ± (δ/2 + dispersion); the largest overlapping set are truechimers, the rest falsetickers.
5. Servo: slew θ with gain kp; integrate θ with ki into a frequency correction (skew).
6. PTP: the master multicasts Sync (two-step: exact t1 in Follow_Up); slaves send Delay_Req and get Delay_Resp. The best master clock algorithm elects the master from Announce messages. Boundary clocks re-time each hop; transparent clocks add residence time to a correction field.

ref ─Sync─► [boundary clock] ─Sync─► NIC (PHC, hw stamps t1..t4) ─► servo ─► system clock
                  ▲ residence-time correction            └► error bound ► application

Code

Compiled and run; assertions pass.

use std::collections::VecDeque;

/// Client clock in ns; the server is perfect and reads true time `now`.
pub struct Clock { pub value: f64, pub skew_ppm: f64, pub adj_ppm: f64 }
impl Clock {
    pub fn advance(&mut self, dt: f64) { self.value += dt * (1.0 + (self.skew_ppm + self.adj_ppm) * 1e-6); }
}

#[derive(Clone, Copy)]
pub struct Sample { pub theta: f64, pub delta: f64, pub seq: u64 }

/// One four-timestamp exchange; d1/d2 are the one-way delays, `hold` the server turnaround (all ns).
pub fn exchange(c: &mut Clock, now: &mut f64, d1: f64, hold: f64, d2: f64, seq: u64) -> Sample {
    let t1 = c.value;
    c.advance(d1); *now += d1;     let t2 = *now; // server receive
    c.advance(hold); *now += hold; let t3 = *now; // server send
    c.advance(d2); *now += d2;     let t4 = c.value;
    Sample { theta: ((t2 - t1) + (t3 - t4)) / 2.0, delta: (t4 - t1) - (t3 - t2), seq }
}

/// NTP clock filter: of the last N samples, return the one with minimum delay.
pub struct MinDelayFilter { win: VecDeque<Sample>, n: usize }
impl MinDelayFilter {
    pub fn new(n: usize) -> Self { Self { win: VecDeque::new(), n } }
    pub fn push(&mut self, s: Sample) -> Sample {
        if self.win.len() == self.n { self.win.pop_front(); }
        self.win.push_back(s);
        *self.win.iter().min_by(|a, b| a.delta.total_cmp(&b.delta)).unwrap()
    }
}

/// PI servo: kp slews a fraction of the offset, ki integrates it into a frequency correction.
pub struct Servo { kp: f64, ki: f64, last_seq: u64 }
impl Servo {
    pub fn new(kp: f64, ki: f64) -> Self { Self { kp, ki, last_seq: 0 } }
    pub fn update(&mut self, c: &mut Clock, s: Sample, poll_s: f64) {
        if s.seq <= self.last_seq { return; } // never reuse a sample
        self.last_seq = s.seq;
        c.value += self.kp * s.theta;                 // slew
        c.adj_ppm += self.ki * s.theta / poll_s * 1e-3; // theta ns per poll_s s = theta/poll_s ppb
    }
}

pub struct Rng(u64); // xorshift64*, uniform in [0,1)
impl Rng {
    pub fn next(&mut self) -> f64 {
        self.0 ^= self.0 >> 12; self.0 ^= self.0 << 25; self.0 ^= self.0 >> 27;
        (self.0.wrapping_mul(0x2545F4914F6CDD1D) >> 11) as f64 / (1u64 << 53) as f64
    }
}

fn main() {
    let mut r = Rng(88172645463325252);
    let jitter = |r: &mut Rng| 100_000.0 + r.next() * 400_000.0; // 100-500 us each way, independent

    // Symmetric: theta is exact.
    let mut now = 1e9;
    let mut c = Clock { value: now - 7e6, skew_ppm: 0.0, adj_ppm: 0.0 };
    assert_eq!(exchange(&mut c, &mut now, 250e3, 1e3, 250e3, 1).theta, 7e6);

    // Random asymmetry: |error| <= delta/2; min-delay beats raw.
    let (mut f, mut now) = (MinDelayFilter::new(8), 0.0);
    let mut c = Clock { value: now - 7e6, skew_ppm: 0.0, adj_ppm: 0.0 };
    let (mut raw, mut best) = (0.0, 0.0);
    for i in 1..=2000 {
        let s = exchange(&mut c, &mut now, jitter(&mut r), 1e3, jitter(&mut r), i);
        assert!((s.theta - 7e6).abs() <= s.delta / 2.0 + 1e-6);
        let b = f.push(s);
        if i >= 8 { raw += (s.theta - 7e6).abs(); best += (b.theta - 7e6).abs(); }
    }
    assert!(best <= raw);

    // Servo: 20 ppm skew, 5 ms offset, 1 s poll, 1 h.
    let (mut f, mut sv, mut now) = (MinDelayFilter::new(8), Servo::new(0.3, 0.01), 0.0);
    let mut c = Clock { value: 5e6, skew_ppm: 20.0, adj_ppm: 0.0 };
    for i in 1..=3600 {
        let s = exchange(&mut c, &mut now, jitter(&mut r), 1e3, jitter(&mut r), i);
        sv.update(&mut c, f.push(s), 1.0);
        let idle = 1e9 - (s.delta + 1e3); // rest of the 1 s poll
        c.advance(idle); now += idle;
    }
    assert!((now - c.value).abs() < 100e3);   // < 100 us
    assert!((c.adj_ppm + 20.0).abs() < 1.0);  // skew learned within 1 ppm
}

Complexity and constants

O(1) per exchange; an NTP packet is 48 bytes plus extensions. Unfiltered error ≤ δ/2: δ of 100 µs gives ±50 µs. Quartz drifts tens of ppm (20 ppm = 1.7 s/day), so between polls the error grows by skew × interval. RFC 5905 allows polls from 64 s to 36 h; chrony uses 64-1024 s.

Efficiency

• Cost: CPU is negligible. On this Mac (aarch64, release) Instant::now ≈ 17 ns, SystemTime::now ≈ 20 ns, the simulated exchange plus filter and servo ≈ 11 ns. The bound is timestamp quality and round-trip latency.
• Levers:
  • hardware timestamps — removes tens of µs of software jitter; sub-µs with PTP (chrony docs) — NIC with PHC.
  • minimum-delay filter — mean error 68 → 44 µs in the run above (synthetic jitter) — noisy queues.
  • longer poll once stable — fewer packets, the servo's frequency estimate bridges drift (chrony, NTP) — stable oscillator.
  • boundary clocks, local stratum-1 — fewer hops of delay variation — large networks.
  • interleaved mode — the previous hardware TX timestamp rides in the next packet (RFC 9769) — NTP with TX stamping; and slew, never step.
• Naive → standard → state of the art:
  • one SNTP request, set clock · error up to the RTT, time may jump back.
  • NTPv4/chrony: 8-sample filter, multi-server selection, slewing · order of ms over the internet.
  • PTP with hardware stamps and boundary clocks · sub-µs; Huygens (NIC stamps, SVM-purified probes) · 100 ns.

Implementation notes

• Enable SOF_TIMESTAMPING_RX_HARDWARE/TX_HARDWARE via SO_TIMESTAMPING; steer the PHC to the system clock with phc2sys or chrony's refclock PHC.
• Durations and timeouts use CLOCK_MONOTONIC; wall clock only for timestamps, so a step never breaks a timer.
• Publish the bound: ClockBound's is |local offset| + root dispersion + root delay/2. Wait it out before acting (commit-wait).
• Leap seconds: smear on the server (Google: 24 h linear, noon to noon; AWS Time Sync smears; chrony: quadratic) and never mix smeared and unsmeared sources.

Pitfalls

• Asymmetry is a permanent bias: no filter removes it, only hardware, calibration or PTP asymmetry correction.
• High kp/ki oscillates; reusing a sample double-counts.
• Virtual machines pause and migrate; the guest clock stalls, then jumps. Use a PHC or VMClock.
• Switches without boundary or transparent clocks add queueing variation.
• A free-running daemon must be reported as such; leases and fencing tokens must not trust the wall clock alone.

Variants and alternatives

In production

• Spanner TrueTime and AWS ClockBound expose [earliest, latest]; EC2 offers a PTP hardware clock (AWS Time Sync).
• Telecom/5G (ITU-T G.8275.1), power grids (IEEE C37.238), broadcast audio/video (AES67, SMPTE ST 2059/2110), market-data timestamping (RTS 25).

Implementations

Sources

• Mills et al., NTP Version 4, RFC 5905, 2010. rfc
• Franke et al., Network Time Security for NTP, RFC 8915, 2020. rfc
• Geng et al., Exploiting a Natural Network Effect for Scalable, Fine-grained Clock Synchronization, NSDI 2018. paper
• Corbett et al., Spanner: Google's Globally-Distributed Database, OSDI 2012. paper
• IEEE 1588-2019, Precision Clock Synchronization Protocol. standard
• Google leap smear · AWS EC2 precision clock · Linux timestamping · chrony comparison · RFC 9769
• Commission Delegated Regulation (EU) 2017/574 (RTS 25).