Mittelwert-Algorithmus

Der Mittelwert-Algorithmus dient der Synchronisation von logischen Uhren in verteilten Systemen. Er sorgt also nicht für eine global gültige Zeit, sondern nur für eine temporale Ordnung von Ereignissen (die Kausale Ordnung). Anders als bei Algorithmen wie dem Berkeley-Algorithmus benötigt er keine zentrale Komponente, sondern funktioniert mittels Broadcast.

Ablauf

Jeder Rechner in einem verteilten System muss in bestimmten Abständen seine Uhrzeit an alle Rechner mittels Broadcast senden. Die Zeitpunkte, an denen er sendet, sind fixiert durch einen a priori bekannten Start-Zeitpunkt T0 und einem fixen Intervall R namens Fixlängen-Resynchronisations-Intervall. Alle Rechner senden ihre Zeit dann zu den Zeitpunkten T0, T0+(1*R), T0+(2*R), ... Nach dem Abschicken der eigenen Zeit wartet der Rechner eine vordefinierte Zeit S (S ist kleiner R), in dem alle einkommenden Zeiten anderer Rechner gesammelt werden. Dann wird aus den gesammelten Zeiten ein Mittelwert berechnet und die eigene Uhr auf die neue Zeit gestellt bzw. verlangsamt, bis die eigene Zeit mit der neuen Zeit übereinstimmt.

Mögliche Mittelwertalgorithmen

Der Mittelwert der empfangenen Zeiten kann nach verschiedenen Vorgehensweisen errechnet werden:

Siehe auch