Cristian's algorithm

The algorithm Cristian (after Flaviu Cristian) is an algorithm for synchronizing physical clocks in distributed systems . It needs a time server with which computers that need the current time can synchronize. The round trip time (RTT) of the request must be shorter than twice the desired accuracy. The algorithm was published in 1989 by Flaviu Cristian.

procedure

The algorithm Cristian runs between the process and a time server , a source for UTC decreases. ${\displaystyle P}$ ${\displaystyle S}$

1. ${\displaystyle P}$asks for the time from at the time ${\displaystyle S}$ ${\displaystyle t_{0}}$
2. The request is processed by; this takes a period of time . ${\displaystyle S}$ ${\displaystyle I}$
3. The answer is from the time received ${\displaystyle C_{M}(t_{1})}$ ${\displaystyle P}$ ${\displaystyle t_{1}}$
4. ${\displaystyle P}$is set to the time , d. H. the time reported by the server plus the return time of the packet. ${\displaystyle C_{M}(t_{1})+{\frac {RTT}{2}}}$

The round trip time is calculated by . If the time period (execution time ) is known, the calculation can be improved: . It is assumed that the watch is read from immediately before it is returned to. ${\displaystyle RTT=(t_{1}-t_{0})}$ ${\displaystyle I}$ ${\displaystyle S}$ ${\displaystyle RTT=(t_{1}-t_{0}-I)}$ ${\displaystyle C_{M}(t_{1})}$ ${\displaystyle P}$ ${\displaystyle S}$

See also

• Berkeley algorithm

literature

• Andrew S. Tanenbaum, Maarten van Steen: Distributed Systems - Fundamentals and Paradigms. Pearson Studium, Munich 2003, ISBN 3-8273-7057-4 .

Individual evidence

1. ^ ^{A b} F. Cristian: Probabilistic clock synchronization. In: Distributed Computing. Volume 3, Issue 3, 1989, pp. 146-158. doi: 10.1007 / BF01784024