Clock synchronization in DFS

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.