---
title: "Cristian's algorithm"
subject: "Distributed System"
chapter: 5
key: "semester_7/distributed_system:cristian-algorithm"
source: https://www.bctengineer.com/q/semester_7/distributed_system/cristian-algorithm
site: BCT Engineering
---

# Cristian's algorithm

Distributed System · Chapter 5: Time and State in Distributed Systems

- Asked in: 2076 Chaitra, 3 marks; 2072 Kartik, 4 marks; 2074 Chaitra, 1+2+5 marks (asked 3 times)
- Video: [Cristian's Algorithm Physical clock synchronization in Distributed Systems](https://www.youtube.com/watch?v=9RUmRzAI3jA) — Simplified Computer Science Concepts-Prof. Rutuja
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/cristian-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-5

## Question

Define clock synchronization. What is the need of clock synchronization? Explain Cristian's algorithm for physical clock synchronization along with necessary diagram.

## Short answer

Clock synchronization makes distributed clocks agree closely. Cristian's algorithm uses a UTC time server: the client records send time T0, receives server time Ts, notes arrival T1, and sets its clock to Ts + (T1 - T0)/2, assuming symmetric delay. Accuracy is plus or minus half round-trip time minus minimum delay.

## Answer

#### Clock synchronization
Clock synchronization is the process of making the clocks of the computers in a distributed system show the same time (or a time within a small bound). Each computer has its own crystal clock, and the clocks run at slightly different rates.

#### Need
- Time-stamped events (logs, transactions, file modification time) must be ordered correctly across machines; e.g. tools like `make` rebuild wrongly with inconsistent times.
- Distributed algorithms (mutual exclusion, deadlock detection, replication, security tickets with expiry) depend on a common time.
- Billing, auditing, scheduling and real-time control need agreed times.

#### Cristian's algorithm
It uses a **time server** (with a UTC receiver). A client asks for the time and corrects its clock using the reply, compensating for network delay.

```text
 Client                         Time Server
   |---- request (at T0) -------->|
   |                              | reads time T_S
   |<--- reply (T_S) -------------|
   | (reply arrives at T1)        |
```
Steps:
1. Client records T0 and sends a request to the time server.
2. Server replies with its current time T_S.
3. Client records arrival time T1. Round-trip time = T1 − T0.
4. Assuming symmetric delay, the reply took (T1 − T0)/2, so the client sets its clock to
   **T_new = T_S + (T1 − T0)/2**.

Accuracy is ± ((T1 − T0)/2 − Tmin), where Tmin is the minimum one-way delay. Improvements: take several measurements and use the one with the smallest round trip; never set the clock backwards (slow it down gradually).

Example: T0 = 10:00:00.000, T1 = 10:00:00.020, T_S = 10:00:05.000. Client sets T_new = 10:00:05.000 + 0.010 = 10:00:05.010.

Limitation: the single time server is a single point of failure and a bottleneck.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In Cristian's algorithm, which formula sets the client's clock?
   A. T_new = T_S + (T1 - T0)
   B. T_new = T_S - (T1 - T0)/2
   C. T_new = (T0 + T1)/2
   D. T_new = T_S + (T1 - T0)/2
   Answer: D. The reply is assumed to have taken half the round trip, so half the RTT is added to the server time. (Key point: Cristian formula)

2. T0 = 10:00:00.000, T1 = 10:00:00.020, T_S = 10:00:05.000. What is the new client time?
   A. 10:00:05.010
   B. 10:00:05.020
   C. 10:00:05.000
   D. 10:00:04.990
   Answer: A. RTT = 20 ms, half = 10 ms, so T_new = 5.000 + 0.010 = 5.010. (Key point: Calculation)

3. What assumption does Cristian's algorithm make about network delay?
   A. The delay is zero
   B. Request and reply delays are equal (symmetric)
   C. The delay is always the minimum
   D. Only the reply is delayed
   Answer: B. Using RTT/2 assumes symmetric delays; asymmetry causes error. (Key point: Assumption)

4. What is the main limitation of Cristian's algorithm?
   A. It needs vector clocks
   B. It averages the clocks of all machines
   C. A single time server is a single point of failure and a bottleneck
   D. It can only set clocks backwards
   Answer: C. Dependence on one server is the weakness that Berkeley and NTP address. (Key point: Weakness)

## Related in Distributed System

- [Physical clock synchronization algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-clock-sync-algorithm) — Distributed System, chapter 5
- [Need of logical clock synchronization](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alogical-clock-sync-need) — Distributed System, chapter 5
- [Clock synchronization need; Lamport](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aclock-sync-lamport-need) — Distributed System, chapter 5
- [Vector clock synchronization algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Avector-clock-algorithm) — Distributed System, chapter 5, asked 2×
- [Physical vs logical clock; sync method](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-clock-sync-difficulty) — Distributed System, chapter 5, asked 2×
- [Synchronising physical clock using logical clock](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Async-physical-with-logical) — Distributed System, chapter 5, asked 2×

## Related in other subjects

- [Clock synchronization in DFS](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Aclock-synchronization-dfs) — Big Data Technologies, chapter 1
- [Digital clock state diagram](https://www.bctengineer.com/question.md?key=semester_6%2Fobject_oriented_analysis_and_design%3Adigital-clock-state-diagram) — Object Oriented Analysis and Design, chapter 2