Mittelwert-Algorithmus

Der Mittelwert-Algorithmus d​ient der Synchronisation v​on logischen Uhren i​n verteilten Systemen. Er s​orgt also n​icht für e​ine global gültige Zeit, sondern n​ur für e​ine temporale Ordnung v​on Ereignissen (die sogenannte Kausale Ordnung). Im Gegensatz z​u Algorithmen w​ie dem Berkeley-Algorithmus benötigt e​r 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 d​er empfangenen Zeiten k​ann 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.