Time synchronization algorithms are widely used.
For example, in Unix systems, the Make command is only used to compile newly modified code files. The Make command uses the clock of the running client to determine which files have been modified. However, if the code is placed on the file server and the time of the host running the make command is different from that of the file server, the make command may not work properly.
For example, when playing Dota, several clients need a synchronized clock to keep everyone's picture consistent. , For example, PC computer synchronization server time can achieve very high synchronization accuracy.
Time synchronization algorithm
Time synchronization algorithm has the following solutions:
Cristian's algorithm
The application background of Cristian's Algorithm algorithm is mainly when a process P is like a server S requesting time:
1. P sends a request packet to S to request the time.
2. After S receives P's request packet, it adds the current S time to the packet and then sends it back.
3. After P receives the data packet, it sets the current time to T+RTT/2.
RTT represents a Round Trip Time, which is the time from P sending to receiving a data packet. The algorithm assumes that sending and receiving packets takes the same amount of time on the network. And it is also assumed that S's time is negligible when processing requests. Based on the above assumptions, the algorithm can be improved as follows:
Send multiple request packets from P to S, and then take the smallest RTT as the RTT divided by two and add it to the time included in this packet.
Algorithm accuracy analysis: Assume that min is the shortest time from S to P, and T is the time included in the RTT defined above. Then, the range of P setting time should be [T+min, T+RTT-min]. In this way, the time deviation range is within RTT-2min. The accuracy of the improved algorithm should be RTT/2-min.
algorithm Berkeley algorithm
The usage environment of Berkeley algorithm is different from Cristian algorithm. The Cristian algorithm is used when a client requests the correct time from a server. The Berkeley algorithm is an algorithm for synchronizing clocks between several clients. The specific algorithm is as follows:
1. First select a node from a ring as the Master through Change and Robert's Algorithm.
2. A Master uses the Cristian algorithm to request the time of each node.
3. The Master evaluates the time deviation of each node by recording the average RTT and eliminating RTTs with large deviations.
4. The Master sends the time deviation of each node to each node, allowing the nodes to correct themselves.
After the client receives the time, generally speaking, it will not adjust the current time back. Because this will cause some inexplicable errors in the program. Because in many algorithms, it is a basic assumption that time will not be adjusted back. For example, make command.
There is a solution: just let the clock run slower. Take some time to adjust to the correct time.
In addition, the algorithm Change and Robert's Algorithm needs to be discussed. This algorithm is the same as the time synchronization algorithm and is needed when playing Dota. When dota is initialized, the clocks of each player need to be synchronized. After being offline, a specific algorithm must be used to find a new host:
Change and Robert's Algorithm
The Change and Robert's Algorithm algorithm assumes that each Process has a UID and that there can be a directionless communication channel in a Ring-shaped network. The algorithm is as follows:
1. First, each node in the ring identifies itself as non-participant.
2. When a process finds that the host is offline, it first identifies itself as a participant, and then sends a host-selected packet containing its own UID to the neighbor.
3. When the data packet reaches the neighbor, it first compares it with its own UID. If its own UID is larger than this UID, it identifies itself as a participant, modifies the UID in the data packet, and also sends this in the clockwise direction. data.
4. When a process receives a data packet and finds that the UID in the data packet is the same as its own UID, it starts the second phase of the algorithm:
5. This process identifies itself as non-participant and sends information about the selected host to the neighbor, including UID information.
6. This cycle continues until the process returns to the Process selected as the host. The entire process ends.
This is an algorithm for selecting a host in a distributed system. Of course, under specific circumstances, you can change the selection conditions, such as choosing the one with the fastest network speed or the fastest CPU as the host. At the same time, this algorithm can also avoid the situation where multiple processes find that the host is offline at the same time, and several processes seek the host at the same time.
The pseudocode of this algorithm can be described as follows:
Start : M:= i:
Send <i> to neighbor;
Upon receiving message <j>;
If M<j then M:=j;
Send <j> to neighbor;
Elseif M=j then leader;
Endif;
For detailed complexity analysis, mathematical models and statistical tables of this algorithm, please refer to this paper:
http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf
This article only analyzes several time synchronization algorithms in Centrilized System, and does not analyze the Network Time Protocol and Reference broadcast Synchronization algorithms in distributed systems. I will study NTP when I have time in the future.