CoreConcept & Pseudocode Entry

Cristian's Algorithm

Synchronizes a client's physical wall clock with a reference time server by measuring round-trip network delay and setting time to T_server + RTT / 2.

Explore relationships Open 3D GraphBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Distributed Systems
Difficulty: Beginner
Family: Physical & Logical Clock Synchronization
Tier: Core
Status: Reviewed
Review: AI Reviewed
Sources: 1
Formulas: 1
Relationships: 4
Code example: Not ready
Visualization: Ready
Aliases: Cristian Clock Synchronization, RTT-Compensated Physical Clock Sync

Overview

Cristian's Algorithm is a probabilistic physical clock synchronization method where a client polls a time server connected to an accurate reference (such as UTC/GPS). Using local monotonic timestamps T0 (request sent) and T1 (response received), the client estimates one-way network transit time as half the round-trip delay (T1 - T0 - I_server) / 2 and slews its clock accordingly.

Core Concepts

round-trip time (RTT)symmetric path delay estimationclock slewingerror bound

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1) per poll

Average

O(1) per poll

Worst

O(k) for k-sample min-RTT filter

Space

O(1)

Interactive Runtime & Memory Budget Calculator

Estimate wall-clock latency, operation count, and working memory for Cristian's Algorithm across input scales.

Input Scale N:

JIT-compiled JS/TS (~350M primitive ops/sec)

Est. Average TimeO(1) per poll

11 ns

Sub-microsecond~4

Est. Worst-Case TimeO(k) for k-sample min-RTT filter

428.6 µs

60 FPS Frame-Safe (<16ms)~150.0k ops

Est. Working MemoryO(1)

128 B

L2/L3 Cache FriendlyN=100,000

When to Use

Use Cristian's Algorithm when a client needs to synchronize its physical wall clock to an authoritative UTC/reference time server over a low-jitter network.
Use repeated probes and keep the sample with the minimum RTT to minimize asymmetric queueing error.

When Not to Use

Avoid relying on a single server without backup or outlier filtering (use Marzullo's algorithm / NTP across multiple servers, or Berkeley algorithm when no external UTC reference exists).

What It Does

Synchronizes a client node's physical wall-clock time to an authoritative time server over a network
Bounds clock offset error by +/- (RTT - min_transit) / 2 using round-trip latency measurements

Use Cases

Low-latency intranet physical clock synchronization against a reference time server
Discard-high-RTT repeated polling to tighten wall-clock accuracy bounds
Foundation for client-server NTP request/response offset estimation

Inputs

Client send time T0, client receive time T1, and server timestamp T_server (plus optional server processing time I)

Outputs

Estimated current physical time T_sync = T_server + (T1 - T0 - I) / 2 and error bound

Key Formulas (1)

Cristian Offset Estimate

T_client = T_server + (T₁ − T₀ − I) / 2

T_client = T_server + (T_1 - T_0 - I) / 2

Adds half the net round-trip network delay to the server's reported timestamp.

Pseudocode

1.Record local monotonic timestamp T0 and send time request to reference server
2.Server records its UTC reference clock T_server (and interrupt handling time I) and replies
3.Client records local monotonic receipt timestamp T1 upon arrival
4.Compute round-trip network transit RTT = (T1 - T0) - I
5.Set target synchronized clock to T_server + RTT / 2 (slew gradually if behind)

Algorithmic Specification & Pseudocode

Concept & Pseudocode Entry

This entry is part of the 1,000-algorithm concept catalog and provides high-level pseudocode, complexity bounds, and relationship links rather than a standalone in-browser benchmark engine.

⚡ Explore 63 Live Benchmarked Implementations →

Structured Execution Steps

Record local monotonic timestamp T0 and send time request to reference server
Server records its UTC reference clock T_server (and interrupt handling time I) and replies
Client records local monotonic receipt timestamp T1 upon arrival
Compute round-trip network transit RTT = (T1 - T0) - I
Set target synchronized clock to T_server + RTT / 2 (slew gradually if behind)

Canonical Example

Input: T0 = 100.0 ms, T1 = 112.0 ms, I = 2.0 ms, T_server = 5000.0 ms
Output: T_sync = 5000.0 + (112.0 - 100.0 - 2.0) / 2 = 5005.0 ms
Explanation: Subtracting 2 ms server handling from the 12 ms round trip leaves 10 ms network transit, or 5 ms estimated one-way delay.

Implementation Notes

Measure T1 - T0 using a local monotonic hardware counter rather than the adjustable wall clock.

Common Pitfalls

Setting the local clock backward abruptly when T_sync < T_local, which breaks monotonic timestamps and timers; slew the clock rate gradually instead.
Assuming symmetric network delay during congestion spikes; discard responses whose RTT exceeds a tight threshold.