Clock synchronization #

Introduction #

In a centralized system, time is unique. The operating system usually sets the clock. This means that all processes on the same operating system are consistent. For example, if a file was saved and then compiled, the result will have a newer time than the source file. It does not matter if the clock is off by a few seconds, because the relative order is correct.

However, when working in a distributed system it is not so easy to know the correct time. Nevertheless, it is very important. Imagine a file synchronization of several computers with wrong clocks. Which version is the latest?

NTP - Network Time Protocol #

If several computers need the identical time, they could ask a third party to tell them. This works, but is not completely accurate, because the transmission time can only be estimated.

In a diagram the protocol looks like this:

B sends the current time \(T_1\) to A. A notes the received time in \(T_2\) and returns a reply with \(T_2\) and current time \(T_3\) . B receives the message and stores the received time in \(T_4\) . So B knows all timestamps from \(T_1\) to \(T_4\) .

\(\Delta t_{req}\) and \(\Delta t_{res}\) is now the difference in arrival times i.e. the time it takes to deliver the message.

It is calculated as follows:

\(\Delta t_{req} = T_2 - T_1\) and \(\Delta t_{res} = T_4 - T_5\) .

So it can be estimated that the transmission time is about half of both values:

The correct time at time \(T_4\) for B is therefore \(T_3 + \Delta t_{rtt}\) . Consequently, B must correct the clock as follows:

Berkley Algorithmus #

With NTP, the timeserver is passive. With the Berkley algorithm, the timeserver regularly asks the computers for the current time and calculates an average. It then informs the computers of the correct time so that they can correct it. This algorithm has the decisive advantage that it does not require network access. Thus, several computers that are not connected to the network can be synchronized. However, it should be noted that the correct time is probably not the same as the correct time. But as long as the system of computers does not communicate with other computers, this is not a tragedy, because the relative time is correct.

Lamport’s logical clock #

The Lamport clock defines “only” a logical clock, that means there is no absolute time as we know it from alarm clocks and the like. Lamport has defined a relationship between two “events”, which he calls “happens-before”. In most texts the events are exchanged between processes. Processes can be understood here in a broader sense, i.e. systems with a clock as a counter. Each event then increments this counter. Lamport also establishes two important rules.

1. If a and b are events in the same process and a happens before b, then a happens-before b (a -> b) is true.
2. If a is a “send event” sent by one process and b is the corresponding “receive event” received by another process, then a happens-before b (a -> b) is also true. Because only something can be received that was sent before.

Example #

There are 3 processes (P1 to P3) that exchange 4 events ( \(e_1\) to \(e_4\) ) with each other. The 3 processes have a relative clock that starts at 0 and ticks at different speeds. The table below shows this situation.

However, this way no global order can be created. Therefore, in the next step, the clock is to be corrected in each case as soon as it has been recognized that the clock is too behind. This for the following result:

Now a partial order is possible. However, there is still the situation that equal counters can occur. We can prevent this by appending the process ID in the counter. For example, the counter 20 in process 1 is then 20.1 and in process 3 then 20.3. It should be noted that even with this extension no global order can be established. This is because process 2 and 3 are concurrent up to \(e_2\) , for example.