Average value algorithm

The mean value algorithm is used to synchronize logical clocks in distributed systems . So it does not ensure a globally valid time, but only a temporal order of events (the so-called causal order ). In contrast to algorithms like the Berkeley algorithm , it does not require a central component, but works by means of broadcast .

procedure

Each computer in a distributed system must send its time to all computers at certain intervals by means of broadcast . The times at which it sends are fixed by a start time T0 known a priori and a fixed interval R called the fixed-length resynchronization interval. All computers then send their time at times T0, T0 + (1 * R), T0 + (2 * R), ... After sending its own time, the computer waits for a predefined time S (S is less than R) in which all incoming times from other computers are collected. Then an average value is calculated from the collected times and your own clock is set to the new time or slowed down until your own time matches the new time.

Possible mean value algorithms

The mean value of the times received can be calculated using various methods:

• Calculating the arithmetic mean (i.e. the average of all values)
• Delete the highest and lowest extreme values ​​and calculate the arithmetic mean
• Weighting of each received time with an expected value and calculation of the weighted arithmetic mean. The expected value can be deduced from the network topology.

literature

• Andrew S. Tanenbaum and Maarten van Steen Distributed Systems - Fundamentals and Paradigms , Pearson Studium, 2003