--- title: "Clock synchronization in DFS" subject: "Big Data Technologies" chapter: 1 key: "semester_8/big_data_technologies:clock-synchronization-dfs" source: https://www.bctengineer.com/q/semester_8/big_data_technologies/clock-synchronization-dfs site: BCT Engineering --- # Clock synchronization in DFS Big Data Technologies · Chapter 1: Introduction to Big Data - Asked in: 2075 Bhadra, 10 marks - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_8/big_data_technologies/clock-synchronization-dfs - Whole chapter: https://www.bctengineer.com/md/semester_8/big_data_technologies/chapter-1 ## Question Clock synchronization in DFS may be the big challenge. How this clock synchronization problem can be solved? ## Short answer Clock synchronization problems are addressed by physical clocks (NTP/Cristian's algorithm for approximate agreement) and logical clocks (Lamport for happened-before ordering, vector clocks for concurrency detection). File system designs like GFS assign master-chosen version numbers and leases to avoid relying on synchronized time for correctness. ## Answer In a distributed file system (DFS) every node has its own physical clock. Clocks run at slightly different speeds (**clock drift**) and show different times (**clock skew**), and there is no shared global clock. This matters because file timestamps, ordering of writes, cache validation, transaction order and log merging all depend on time. If node A writes a file at "10:00:05" by its clock and node B writes at "10:00:03" by its clock, the system may wrongly keep the older version. #### Problem - Hardware clocks drift (about 1 second in 10^5 to 10^6 seconds). - Network delay is variable, so a time message arrives late by an unknown amount. - Without agreement, conflicting updates, wrong "last modified" decisions and inconsistent replicas result. #### Solutions **A. Physical clock synchronization** 1. **Cristian's algorithm (time server):** a client asks a time server for the time. Let T0 be the send time and T1 the receive time on the client, and Tserver the server reply. `Tclient = Tserver + (T1 - T0)/2` Simple, but the server is a single point of failure. 2. **Berkeley algorithm (no UTC source):** a coordinator polls all nodes for their times, averages them (ignoring outliers), and sends each node the adjustment to make. The group agrees on one time even if it is not real time. 3. **NTP (Network Time Protocol):** a hierarchy of time servers (stratum 0 atomic/GPS clocks, stratum 1, 2 ...). Nodes synchronise with servers above them and correct delay statistically. Accuracy is a few milliseconds on a LAN. **B. Logical clocks (order matters, not real time)** 1. **Lamport logical clock:** each process keeps a counter C. - Before each event: C = C + 1. - When sending a message, attach C. - On receiving a message with timestamp t: C = max(C, t) + 1. This gives the "happened-before" ordering (a -> b implies C(a) < C(b)). 2. **Vector clocks:** each process keeps a vector with one counter per process. They can detect whether two events are causally ordered or concurrent (conflicting), which is useful for replica conflict detection (used in Dynamo-style stores). **C. Design choices in file systems** - GFS avoids dependence on clocks for correctness. The master gives **chunk version numbers** and **leases** (60 s) to decide the primary, and the primary assigns a serial order to mutations. Timestamps are only metadata. - HDFS uses a single NameNode that stamps all metadata with one clock, so no cross-node ordering problem arises. - Servers run NTP/chrony so that lease expiry is nearly consistent. #### Conclusion of approach Use NTP or Berkeley for approximate real-time agreement, and use logical clocks, version numbers, leases and a single ordering authority (master/primary) where correct ordering is required. #### Example of Cristian's algorithm Client sends request at T0 = 10:00:00.000 and receives the reply at T1 = 10:00:00.040 (round trip 40 ms). The server time in the reply is 10:00:05.000. Estimated one-way delay = 40/2 = 20 ms, so the client sets its clock to 10:00:05.020. #### Example of Berkeley algorithm Coordinator time 3:00, node A 3:25, node B 2:50. Differences from the coordinator: 0, +25, -10. Average = (0 + 25 - 10)/3 = +5. Adjustments sent: coordinator +5, A -20, B +15. All clocks become 3:05. Only relative offsets are sent, so network delay in transmitting absolute times does not matter. #### Example of Lamport clocks Process P1 has C = 4 and sends a message with timestamp 4. P2 has C = 2 when it receives it. P2 sets C = max(2, 4) + 1 = 5. So the receive event is ordered after the send event, even though P2's own clock was behind. #### Limitations - NTP gives millisecond, not exact, agreement; two writes within the error window can still be mis-ordered, so correctness-critical ordering should not rely on physical time alone. - Lamport clocks give a consistent order but cannot tell if two events were concurrent; vector clocks can, at the cost of larger timestamps. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Node A writes a file at 10:00:05 by its clock and node B writes at 10:00:03 by its clock, but B actually wrote later. What can go wrong? A. The files are automatically merged B. The network becomes faster C. The system may wrongly keep the older version D. Both nodes crash Answer: C. Without agreed time, timestamp-based decisions such as 'last modified' can pick the wrong version. (Key point: Why clocks matter in a DFS) 2. Client sends at T0 = 10:00:00.000, receives at T1 = 10:00:00.040, and the server time in the reply is 10:00:05.000. What time does the client set using Cristian's algorithm? A. 10:00:05.020 B. 10:00:05.040 C. 10:00:05.000 D. 10:00:04.980 Answer: A. Tclient = Tserver + (T1 - T0)/2 = 5.000 + 0.020 = 10:00:05.020. (Key point: Cristian's algorithm) 3. Coordinator time 3:00, node A 3:25, node B 2:50. What adjustment does the Berkeley algorithm send to node A? A. +25 minutes B. -5 minutes C. +5 minutes D. -20 minutes Answer: D. The average offset is (0 + 25 - 10)/3 = +5, so the agreed time is 3:05 and node A (3:25) must adjust by -20. (Key point: Berkeley algorithm) 4. P2 has C = 2 and receives a message with timestamp 4. What is P2's clock after the receive event? A. 3 B. 4 C. 6 D. 5 Answer: D. On receive, C = max(C, t) + 1 = max(2, 4) + 1 = 5. (Key point: Lamport logical clock) ## Related in Big Data Technologies - [DFS definition and HDFS client write](https://www.bctengineer.com/question.md?key=semester_8%2Fbig_data_technologies%3Adefine-dfs-hdfs-write) — Big Data Technologies, chapter 2 ## Related in other subjects - [Vector clock synchronization algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Avector-clock-algorithm) — Distributed System, chapter 5, asked 2× - [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 - [Physical clock synchronization algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-clock-sync-algorithm) — Distributed System, chapter 5