Time Synchronization

Why there are timing issues in distributed systems?

 Global Clock – Graphical distribution
 Clock Drift of different systems
 Processes might take varying time to execute on different machines.
 Communication delays in processes.
Synchronization refers to the coordination of actions between processes to ensure they execute in a
desired order or at specific times. The need for synchronization arises due to various reasons:
1. Mutual Exclusion: Primary reason for synchronization is to enforce mutual exclusion, which ensures
that only one process can access a shared resource at a time. This prevents conflicts and data
corruption that may occur when multiple processes try to access the same resource simultaneously.
Example: In a scenario where multiple processes need to print to a shared printer, synchronization
mechanisms like semaphores can be used to coordinate access and prevent printing conflicts.

2. Event Ordering: Synchronization is essential for determining the order of events in a DS. It helps in
establishing a consistent timeline of events and ensuring that processes agree on the sequence in
which events occurred. By synchronizing clocks and using coordination mechanisms, such as
message passing protocols, DS can maintain event ordering and prevent inconsistencies and
improve their reliability.
Example: Was message “x” from process P sent before or after message “y” from process Q?
Modules might be working on different parts of the program, but result is delayed by the slowest
part, example matrix multiplication.

3. Coordination: Facilitating communication and cooperation between processes to achieve a

common goal or perform a task efficiently.
Clock Synchronization
It is the process of ensuring that the clocks in a DS are aligned to a common time reference. It can be
achieved using physical clocks, or logical clocks. It is essential for maintaining event ordering and
coordination among processes. Group coordination is essential for ensuring that processes work
together and make collective decisions.
 Physical Clocks: (Focus) - They rely on absolute time references, such as Coordinated Universal Time
(UTC), to synchronize across different machines. By periodically adjusting their clocks to match the
reference time, physical clocks ensure consistency in timekeeping and event ordering in DS.
 Logical Clocks: They synchronize based on the relative time or ordering of events rather than
absolute time. It assign timestamps to events based on causality, allowing processes to establish a
partial ordering of events even in the absence of a global clock. It is not run locally, they are import.
1|Page
Synchronization Based on Coordination: In some cases, groups of processes may need to appoint a
coordinator to facilitate synchronization and decision-making. Election algorithms can be used to select
a suitable coordinator among processes. Sometimes server uses predefined protocols for selection.
Distributed Mutual Exclusion: Processes must coordinate access to shared resources to prevent
conflicts. By appointing a coordinator to manage access to critical resources, processes can ensure
mutual exclusion and prevent concurrent access issues.
Synchronization in Centralized Systems: Synchronization in Distributed Systems:
In centralized systems or parallel systems, Synchronization here poses greater challenges
synchronization is primarily achieved through due to the absence of shared memory and no
shared memory mechanisms, such as common clock. As each machine operates with
semaphores. These synchronization primitives its own clock, which may drift in their rates over
help coordinate access to shared resources and time due to clock inaccuracies or faults. As a
ensure that processes execute in a synchronized result, achieving synchronization among
manner. Event ordering in centralized systems is distributed clocks and maintaining a consistent
clear, as all events are timed by the same clock, global time reference across is difficult, leading
allowing for great synchronization and to challenges in maintaining event ordering and
coordination. coordination.
Physical Clocks: Computer "clocks" are actually timers (some physical entity) that help track time
intervals and synchronize events within a system. A timer typically consists of a precisely machined
quartz crystal that oscillates at a well-defined frequency when kept under tension, oscillating frequency
depends on the kind of crystal and amount of tension.
 Quartz crystal oscillators are commonly used in CS as timing references due to their stable and
predictable oscillation frequencies. By applying voltage, it vibrates at a precise frequency, serving as
the basis for timekeeping and synchronization in electronic devices.
 The accuracy and stability of a computer clock depend on the quality of the quartz crystal and the
circuitry used to maintain its oscillation frequency. Factors such as temperature variations, voltage
fluctuations, and aging can affect the accuracy of the clock over time.
Clock Drift: Different rates of counting time.
 Physical variations of underlying oscillators. Variance with temperature.
 Even extremely small differences accumulate over a large number of oscillations, leading to
observable difference in the counters.
Drift Rate: Difference in reading between a clock and a nominal “perfect clock” per unit of time
measured by the reference clock.
 A drift of 1% (i.e. 1/100=10-2) means the clock adds or loses a second every 100 seconds.
 10-6 seconds/sec for quartz crystals.
 10-7 - 10-8 seconds/sec for high precision quartz crystals.

2|Page
Network Time Protocol (NTP)
Goals
 It is used globally in the networks system.
 It utilizes a hierarchical system of time servers to distribute time information and adjust clock
offsets. It provides the ability to synchronize clients across internet to UTC. It runs on specific times
(boot time or trigger points to synchronize).
 In NTP there is condition that network should have access to the internet, global clock of internet is
considered as server and all the physical clocks on the system are basically local clocks, which are
synchronized by fetching global clock and matching their times.
 It provides reliable service tolerating lengthy losses of connectivity. It enables clients to
resynchronize sufficiently frequently to offset typical hardware drift rates.
 It provides protection against interference. It uses authentication techniques to check that timing
data originated from the claimed trusted sources.
 Clients rely on their local clocks to do their normal procedures.
Authentication Techniques for Synchronization
Authentication techniques play a crucial role in ensuring the integrity and security of synchronization
data in computer systems. By verifying that timing data originates from trusted sources, authentication
mechanisms help prevent unauthorized access, tampering, or interference.
Various authentication mechanisms can be employed to secure synchronization data.
 Digital Signatures: These are cryptographic techniques used to verify the authenticity and
integrity of messages exchanged between parties.
 Cryptographic Protocols: Such as Transport Layer Security (TLS) and Secure Sockets Layer (SSL),
provide secure communication channels for transmitting timing data securely over networks. By
encrypting data and authenticating communication endpoints, it safeguard synchronization
processes.
 Secure Communication Channels: By using encrypted connections between clients and servers
and using secure protocols, systems can ensure the confidentiality and integrity of
synchronization information exchanged over networks.
Applications of NTP: Used in a production system where the live sound is recorded (broadcasting
infrastructures). Used where file system updates needed to be carried out across multiple computers.
Used to implement security mechanism which depend on consistent time keeping over network.
Advantages of NTP:
 It provides internet synchronization between the devices with enhanced security.
 It is used in the authentication systems like Kerberos.
 It provides network acceleration which helps in troubleshooting problems.
 It is used in file systems that are difficult in network synchronization.
3|Page
Disadvantages of NTP:
 When the servers are down the sync time is affected across a running communication.
 Servers are prone to error due to various time zones and conflict may occur.

Synchronization Subnet:
Primary and secondary servers form a logical hierarchy called synchronization subnet.
 Primary Servers (Connected to UTC)
 Secondary Servers (Synchronized to primary servers)
The establishment of a synchronization subnet facilitates accurate, reliable, and scalable clock
synchronization in distributed systems. This hierarchical architecture ensures that time-critical
applications and services operate with synchronized time references, enhancing system performance
and coordination across networked nodes.

Cristian’s Algorithm
Cristian's algorithm is a classic clock synchronization algorithm designed for distributed systems to
achieve time synchronization among networked machines without requiring a global clock or shared
memory. The algorithm addresses challenges of clock drift and lack of a common time reference in DS.
Cristian's algorithm operates on the client-server model, where a time server responds to time requests
from client machines seeking synchronization. It aims to minimize clock skew and synchronize the client
clocks with the server time by adjusting the local clocks based on the calculated offset.
Algorithm Steps:
 Client Request: At regular intervals, each client machine sends a time synchronization request
to the time server, asking for the current time.
 Server Response: On receiving client request, the time server reads its own time and sends back
a response message containing the current time (CUTC) to the client.
 Client Adjustment: The client machine adjusts its local clock based on the received server time.
4|Page
It removes shortcomings of NTP protocol. Server can be in the environment, not necessary to
synchronize to the internet. Time fetched from the server and reached to the client has some delay,
which need to be process and we have to calculate time difference between messages and we have to
cater time delays as well.
It is sensitive to network delays, message processing times, and variations in communication latencies,
which can impact the accuracy of clock synchronization.
Exercise: A client attempts to synchronize with
a time server. It records the round-trip times
and timestamps returned by the server in the
table below. 3 records for accuracy.

1. Which of these times should it use to set its clock?

2. To what time should it set it?
3. Estimate the accuracy of the setting with respect to the serve’s clock.
4. If it is known that the time between sending and receiving a message in the system concerned is at
least 8ms, do your answers change?
Answers:
1. The client should choose the one with the minimum round trip time (error less) which is 20ms.
2. It sets the time to 10:54:28:342 + 20/2 ms = 10:54:28:352. (not absolute – has error)
(We divide by 2 because time is approximately to be taken out at half of the round-trip).
3. The accuracy is ±((Tround/2) - min(processing delay)) = ±10ms. (processing delay yet = 0)
4. If the minimum message transfer time is known to be 8 ms, then the setting remains the same but
the accuracy improves to ±2 ms, because the accuracy is ±(Tround/2 – min(delay)), where min=8ms.

5|Page
Berkeley Algorithm
In NTP and Cristian algorithm, the time server is passive.
Berkeley algorithm is server initiated, the time server (one daemon process running on one of the
machine) is active that periodically polls every machine to ask what time is there. Then on the reply, it
computes the average and tells machines to advance or slow their clocks to new time. Suitable for
systems, which have no access to UTC source.
If there was 3’0 clock initially on server and time server take difference from the clients, (0, -10, +25),
then subtracts average value (15/3=5) from all clocks, and also drifts itself with network.
 5–0=5  5 – (-10) = 15  5 – (25) = -20

i. Time daemon periodically polls clock reading from all other machines in the systems.
ii. All the machines reply
iii. Time daemon calculates the clock offset for each machine by comparing its local time with the
time reported by the machines and then calculates an average time (including itself) and sends
adjustment messages to the slave machines to synchronize their clocks accordingly.
In DS, global clock is not important but clock synchronization is important.
The Berkeley Algorithm is prominent clock synchronization algorithm developed to address time
discrepancies among networked machines. It operates on the concept of a master-slave architecture,
where master machine coordinates clock synchronization process among multiple slaves.
Unlike Cristian's algorithm, the Berkeley Algorithm decentralizes the synchronization process by
allowing each machine to contribute to the calculation of the average clock offset, allowing distributed
systems to maintain coordinated time references without relying on a central time server.
By implementing the Berkeley Algorithm, distributed systems can achieve effective clock
synchronization by leveraging the collaborative efforts of all machines to adjust their clocks and
maintain time consistency across the network. This decentralized approach enhances the accuracy of
time synchronization in distributed computing environments.

6|Page