Synchronization in Distributed Systems

Distributed System is a collection of computers connected via the high speed communication network. In the distributed system, the hardware and software components communicate and coordinate their actions by message passing. Each node in distributed systems can share their resources with other nodes. So, there is need of proper allocation of resources to preserve the state of resources and help coordinate between the several processes. To resolve such conflicts, synchronization is used. Synchronization in distributed systems is achieved via clocks.

The physical clocks are used to adjust the time of nodes.Each node in the system can share its local time with other nodes in the system. The time is set based on UTC (Universal Time Coordination). UTC is used as a reference time clock for the nodes in the system.

The clock synchronization can be achieved by 2 ways: External and Internal Clock Synchronization.

1. External clock synchronization is the one in which an external reference clock is present. It is used as a reference and the nodes in the system can set and adjust their time accordingly.


2. Internal clock synchronization is the one in which each node shares its time with other nodes and all the nodes set and adjust their times accordingly.

There are 2 types of clock synchronization algorithms: Centralized and Distributed.

1. Centralized is the one in which a time server is used as a reference. The single time server propagates its time to the nodes and all the nodes adjust the time accordingly. It is dependent on single time server so if that node fails, the whole system will lose synchronization. Examples of centralized are- Berkeley Algorithm, Passive Time Server, Active Time Server etc.


2. Distributed is the one in which there is no centralized time server present. Instead the nodes adjust their time by using their local time and then, taking the average of the differences of time with other nodes. Distributed algorithms overcome the issue of centralized algorithms like the scalability and single point failure. Examples of Distributed algorithms are – Global Averaging Algorithm, Localized Averaging Algorithm, NTP (Network time protocol) etc.

2. Clock synchronization

2–1. Physical clock

Clock and clock skew

Most computers have circuitry to hold time, this device is called “clock”. This is based on vibration at frequencies that can clearly defined by the type of crystal, the cutting method, and the magnitude of pressure when adding tension to precisely machined quartz.

Although this frequency is reasonably stable, there is no guarantee that all the crystals of different computers will operate at exactly the same frequency. The difference in the time of synchronization caused by this is called clock skew.

Under this situation, especially in a real-time system, how to synchronize multiple clocks with the real world clock and how to synchronize the clocks is a problem.

The time in the real world was originally based on the mean solar second, but now the time for cesium 133 to transition 9,192,631,770 times is defined as one second, and the International Atomic Time and Universal Coordinated Time (UTC) is defined. In order to provide UTC to those who need accurate time, WWV is used and time is delivered with accuracy of ± 10 msec.

2–2. Clock Synchronization Algorithm

However, most machines do not have WWV receivers. For that reason, each machine needs time-tracking and management algorithms so that all machines can sync time as well as possible.

Incidentally, an error for determining whether resynchronization is necessary, that is, clock skew, is measured as follows.

Define H as the number of interrupts per second (tick number) due to vibration of the crystal counted by each machine, and let C be the value of this clock. Let Cp(t) denote the clock value of machine pwhen UTC time is t.

If Define ρ as the maximum drift rate that defines how much clock skew is allowed, it is assumed that it is operating within the following range.

1-ρ <= dC/dt <= 1+ρ

That is, after Δt seconds have elapsed from the previous synchronization, two clocks are separated by 2ρΔt at the maximum.

When guaranteeing that there is no deviation larger than δ at the time of operation execution, it is necessary to resynchronize the software at least every δ / 2ρ.

Network Time Protocol (NTP)

It is common in many protocols, the method first proposed by [Cristian, 1989] is a method of communicating clients with time servers. Since the time server has a WWV receiver or has an accurate clock, it can provide the current time. When communicating with the server, it is important to delay the time when message propagation delays are reported, but by estimating the delay, here it is possible to minimize the error. Currently, NTP is known to be able to achieve precision in the range of 1 to 50 milliseconds.

Berkeley algorithm

In many algorithms such as NTP, time servers are passive and only answer inquiries. On the other hand, in the Berrkeley algorithm, the time server receives the time held by each participating node and also changes its own time based on the average. When the time value does not have to have a relationship with the real world, it is easy to agree at the same current time and it is effective with this algorithm.

3. Logical Clock

Up to this point, although we described a method of synchronizing clocks with absolute time as reference in accordance with the real-world clock, it is often enough to only perform relative synchronization. Here, the concept of logic clock is used to determine the relative order.