How Does Clock Synchronization Work in a Distributed OS?
Learn clock synchronization in distributed operating systems — Cristian's algorithm, NTP, Lamport and vector clocks — explained with examples.
Expected Interview Answer
Clock synchronization in a distributed OS is the set of algorithms that keep independent machines’ local clocks close enough to a common notion of time (physical clock sync like Cristian’s algorithm and NTP) or that establish a consistent event ordering without true clocks at all (logical clocks like Lamport timestamps and vector clocks).
Physical clocks drift because every machine’s crystal oscillator ticks at a slightly different rate, so without correction, clocks on different nodes diverge by milliseconds to seconds over time. Cristian’s algorithm has a client ask a trusted time server for the time and adjusts for network round-trip delay by estimating one-way latency as half the round trip; NTP extends this with a hierarchical set of time servers (stratum layers) and statistical filtering across many samples to reach sub-millisecond accuracy on a LAN. Because perfect physical synchronization is impossible over an asynchronous network with unbounded delay, Lamport logical clocks instead assign a monotonically increasing counter to each event and bump it on every message send/receive so that causally related events are always ordered correctly, though concurrent events cannot be distinguished. Vector clocks extend this by keeping one counter per node, letting the system detect whether two events are causally related or truly concurrent, which is essential for conflict detection in distributed databases and version control systems.
- Enables consistent event ordering across nodes with no shared clock
- Cristian/NTP give usable wall-clock time for logging, TLS, and timeouts
- Lamport clocks provide cheap causal ordering with a single integer
- Vector clocks distinguish causality from true concurrency for conflict resolution
AI Mentor Explanation
Clock sync is like every ground’s stadium clock being checked against the official match referee’s watch before play starts, adjusting for the seconds it takes a runner to relay the time back to the scoreboard operator, similar to Cristian’s algorithm correcting for round-trip delay. A Lamport-style approach is simpler: instead of matching exact times, the scorer just numbers every ball bowled in strictly increasing order across all grounds, so nobody needs a synchronized watch, only a shared counter that increases whenever a delivery or a message about a delivery happens.
Step-by-Step Explanation
Step 1
Detect drift
Each node's local oscillator ticks at a slightly different rate, so clocks diverge without periodic correction.
Step 2
Physical sync request
A client contacts a time server; Cristian's algorithm or NTP estimates one-way delay as half the measured round trip and adjusts the local clock.
Step 3
Statistical filtering
NTP polls multiple servers repeatedly, discards outliers, and applies a weighted correction to smooth out jitter.
Step 4
Logical fallback
For strict causal ordering without true time, Lamport or vector clocks increment counters on local events and message sends/receives.
What Interviewer Expects
- Explanation of why clocks drift on independent machines
- Correct description of Cristian's algorithm or NTP round-trip correction
- Understanding that perfect physical sync is impossible over an asynchronous network
- Ability to explain Lamport vs vector clocks and what each can/cannot distinguish
Common Mistakes
- Assuming NTP gives perfectly identical time on every machine
- Confusing logical clocks with physical wall-clock time
- Not knowing vector clocks can detect concurrency, unlike Lamport clocks
- Forgetting that clock skew, not just drift, complicates synchronization
Best Answer (HR Friendly)
“Clock synchronization is how separate machines in a distributed system agree on time or at least agree on the order events happened in. Some systems periodically check in with a trusted time server and correct for network delay, while others skip real time entirely and use a shared counter that increases with every message, which is enough to know what happened before what.”
Code Example
long local_clock = 0;
long on_local_event(void) {
local_clock++;
return local_clock;
}
long on_send_message(void) {
local_clock++;
return local_clock; /* stamp attached to outgoing message */
}
void on_receive_message(long msg_timestamp) {
long max_seen = (msg_timestamp > local_clock) ? msg_timestamp : local_clock;
local_clock = max_seen + 1;
}Follow-up Questions
- How does Cristian's algorithm differ from the Berkeley algorithm?
- What is clock skew and how does NTP bound it?
- When would you choose vector clocks over Lamport timestamps?
- How does clock synchronization affect distributed transaction ordering?
MCQ Practice
1. What does Cristian's algorithm correct for when synchronizing a client clock to a time server?
Cristian's algorithm estimates one-way network delay as half the measured round-trip time and adjusts the client clock accordingly.
2. What can a vector clock detect that a Lamport clock cannot?
Vector clocks keep a per-node counter, allowing the system to distinguish true concurrency from a causal happens-before relationship, which a single Lamport counter cannot do.
3. Why is perfect physical clock synchronization impossible over an asynchronous network?
Network delay is variable and there is no upper bound in a fully asynchronous system, so any correction based on measured round trip carries residual uncertainty.
Flash Cards
What does Cristian's algorithm do? — Synchronizes a client clock to a time server by adjusting for half the measured round-trip network delay.
What is a Lamport clock? — A single monotonically increasing counter per node, incremented on events and messages, giving causal ordering.
What is a vector clock? — A per-node array of counters that can distinguish causally related events from truly concurrent ones.
Why can distributed clocks never be perfectly synchronized? — Because network delay is variable and unbounded in an asynchronous system.