Marzullos Algorithmus - Marzullo's algorithm

Marzullos Algorithmus , erfunden von Keith Marzullo für seine Promotion Die Dissertation von 1984 ist ein Übereinstimmungsalgorithmus zur Auswahl von Quellen zur Schätzung der genauen Zeit aus einer Reihe von verrauschten Zeitquellen. Eine verfeinerte Version, die in " Schnittalgorithmus " umbenannt wurde, ist Teil des modernen Network Time Protocol . Der Marzullo-Algorithmus wird auch verwendet, um den entspannten Schnittpunkt von n Feldern (oder allgemeiner n Teilmengen von R n ) zu berechnen , wie dies für mehrere robuste Mengenschätzungsmethoden erforderlich ist .

Zweck

Der Marzullo-Algorithmus ist zeitlich effizient, um aus einer Reihe von Schätzungen mit Konfidenzintervallen einen optimalen Wert zu erzielen, wobei der tatsächliche Wert für einige Quellen außerhalb des Konfidenzintervalls liegen kann. In diesem Fall wird die beste Schätzung als das kleinste Intervall angenommen, das mit der größten Anzahl von Quellen übereinstimmt .

Wenn wir die Schätzungen 10 ± 2, 12 ± 1 und 11 ± 1 haben, dann sind diese Intervalle [8,12], [11,13] und [10,12], die sich schneiden, um [11,12] oder 11,5 ± 0,5 zu bilden als konsistent mit allen drei Werten.

Marzullos Algorithmus, Beispiel 1


Wenn stattdessen die Bereiche [8,12], [11,13] und [14,15] sind, gibt es kein Intervall, das mit all diesen Werten übereinstimmt, aber [11,12] stimmt mit der größten Anzahl von Quellen überein - nämlich zwei von ihnen.

Marzullos Algorithmus, Beispiel 2


Wenn schließlich die Bereiche [8,9], [8,12] und [10,12] sind, stimmen beide Intervalle [8,9] und [10,12] mit der größten Anzahl von Quellen überein.

Marzullos Algorithmus, Beispiel 3


Diese Prozedur bestimmt ein Intervall. Wenn das gewünschte Ergebnis ein bester Wert aus diesem Intervall ist, besteht ein naiver Ansatz darin, die Mitte des Intervalls als Wert zu verwenden, wie dies im ursprünglichen Marzullo-Algorithmus angegeben wurde. Ein differenzierterer Ansatz würde erkennen, dass dies nützliche Informationen aus den Konfidenzintervallen der Quellen wegwerfen könnte und dass ein Wahrscheinlichkeitsmodell der Quellen einen anderen Wert als das Zentrum zurückgeben könnte.

Beachten Sie, dass der berechnete Wert wahrscheinlich besser als "optimistisch" als als "optimal" beschrieben wird. Betrachten Sie beispielsweise drei Intervalle [10,12], [11, 13] und [11,99,13]. Der unten beschriebene Algorithmus berechnet [11.99, 12] oder 11.995 ± 0.005, was ein sehr genauer Wert ist. Wenn wir den Verdacht haben, dass eine der Schätzungen falsch ist, müssen mindestens zwei der Schätzungen korrekt sein. Unter dieser Bedingung ist die beste Schätzung [11,13], da dies das größte Intervall ist, das immer mindestens zwei Schätzungen schneidet. Der unten beschriebene Algorithmus kann leicht mit der maximalen Anzahl falscher Schätzungen parametrisiert werden.

Methode

Marzullos Algorithmus beginnt damit, eine Tabelle der Quellen zu erstellen, zu sortieren und dann (effizient) nach den Schnittpunkten von Intervallen zu suchen. Für jede Quelle gibt es einen Bereich [c - r, c + r], der durch c ± r definiert ist. Für jeden Bereich enthält die Tabelle zwei Tupel der Form <Offset, Typ>. Ein Tupel repräsentiert den Anfang des Bereichs, markiert mit Typ −1 als <c - r, −1> und das andere repräsentiert das Ende mit Typ +1 als <c + r, + 1>.

Die Beschreibung des Algorithmus verwendet die folgenden Variablen: best (größte Anzahl gefundener überlappender Intervalle), cnt (aktuelle Anzahl überlappender Intervalle), beststart und bestend (Anfang und Ende des bisher gefundenen besten Intervalls), i (Index) und die Tabelle der Tupel.

  2. Bauen Sie die Tabelle der Tupel.
  3. Sortieren Sie die Tabelle nach dem Versatz. (Wenn zwei Tupel mit demselben Versatz, aber entgegengesetzten Typen existieren, die anzeigen, dass ein Intervall genau so endet, wie ein anderes beginnt, ist eine Methode zur Entscheidung erforderlich, welches zuerst eintritt. Ein solches Auftreten kann als Überlappung ohne Dauer angesehen werden, die gefunden werden kann durch den Algorithmus, indem Typ -1 vor Typ +1 gesetzt wird. Wenn solche pathologischen Überlappungen als unerwünscht angesehen werden, können sie vermieden werden, indem in diesem Fall Typ +1 vor -1 gesetzt wird.)
  4. [initialisieren] best = 0 cnt = 0
  5. [loop] geht jedes Tupel in der Tabelle in aufsteigender Reihenfolge durch
  2. [aktuelle Anzahl überlappender Intervalle] cnt = cnt - Typ [i]
  3. wenn cnt> best dann best = cnt beststart = offset [i] bestend = offset [i + 1]
Kommentar: Das nächste Tupel bei [i + 1] ist entweder das Ende eines Intervalls (Typ = + 1). In diesem Fall endet es dieses beste Intervall, oder es ist der Anfang eines Intervalls (Typ = -1) ) und im nächsten Schritt am besten ersetzen.
Mehrdeutigkeit: Nicht angegeben ist, was zu tun ist, wenn best = cnt. Dies ist eine Bedingung für ein Unentschieden für die größte Überlappung. Die Entscheidung kann entweder getroffen werden, um den kleineren Wert von bestend-beststart und offset [i + 1] -offset [i] zu verwenden, oder einfach einen beliebigen der beiden gleich guten Einträge. Diese Entscheidung ist nur relevant, wenn Typ [i + 1] = + 1 ist.
  2. [Endschleife] gibt [beststart, bestend] als optimales Intervall zurück. Die Anzahl der falschen Quellen (diejenigen, die das zurückgegebene optimale Intervall nicht überlappen) ist die Anzahl der Quellen abzüglich des Werts der besten.

Effizienz

Marzullos Algorithmus ist sowohl räumlich als auch zeitlich effizient. Die asymptotische Raumnutzung ist O (n) , wobei n die Anzahl der Quellen ist. Bei der Berücksichtigung des asymptotischen Zeitbedarfs kann davon ausgegangen werden, dass der Algorithmus darin besteht, die Tabelle zu erstellen, zu sortieren und zu durchsuchen. Die Sortierung kann in O (n log n) -Zeit erfolgen, und dies dominiert die Bau- und Suchphasen, die in linearer Zeit durchgeführt werden können. Daher ist die Zeiteffizienz des Marzullo-Algorithmus O (n log n) .

Sobald die Tabelle erstellt und sortiert wurde, kann das Intervall für eine Quelle (wenn neue Informationen empfangen werden) in linearer Zeit aktualisiert werden. Daher kann das Aktualisieren von Daten für eine Quelle und das Finden des besten Intervalls in O (n) -Zeit erfolgen.

Verweise

  • Marzullo, KA (Februar 1984). "Aufrechterhaltung der Zeit in einem verteilten System: Ein Beispiel für einen lose gekoppelten verteilten Dienst" . Ph.D. Dissertation . Abteilung für Elektrotechnik. Universität in Stanford. ASIN  B000710CSC . OCLC  38621764 . DDC 3781.1984 M.

Externe Links