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 sogenannte Kausale Ordnung). Im Gegensatz zu 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:

• Errechnen des arithmetischen Mittels (also des Durchschnitts aller Werte)
• Streichen der höchsten und tiefsten Extremwerte und Errechnen des arithmetischen Mittels
• Gewichtung jeder empfangenen Zeit mit einem Erwartungswert und Errechnen des gewichteten arithmetischen Mittels. Der Erwartungswert kann aus der Netzwerktopologie gefolgert werden.

Literatur

• Andrew S. Tanenbaum und Maarten van Steen Verteilte Systeme – Grundlagen und Paradigmen, Pearson Studium, 2003