Demian Hespe, Lukas Hübner, Peter Sanders

Guido Zeitzmann

Fehlertoleranz ist wichtig in großen verteilten Systemen, da der Mittelwert für die Zeit zwischen Fehlern (Hardware versagen) abnimmt, je mehr Rechenknoten das System hat. Die erwartete Fehlerrate für ein System mit 100.000 Knoten und einem Mittelwert für die Zeit zwischen Fehlern von 10 Jahren pro Knoten beträgt 50 min. Wir testen verschiedene Methoden um die Fehlertoleranz von PageRank zu erhöhen. Wir zeigen, dass Methoden ohne Checkpoints zu Beginn des Algorithmus in den ersten 40% mit Fehlern umgehen können, ohne die Iterationszeit von PageRank zu erhöhen. Außerdem testen wir verschiedene Kompressionsverfahren um das Erstellen von Checkpoints zu beschleunigen. Dabei testen wir sowohl verlustfreie als auch verlustbehaftete Kompressionsmethoden. Wir zeigen, dass das Komprimieren von Checkpoints mit ZFP (verlustbehaftete) die Kosten zum Erstellen von Checkpoints im Vergleich zu nicht komprimierten Checkpoints um 40% reduziert. Wir können den Fortschritt von PageRank an der Konvergenz messen, was uns erlaubt, checkpointfreie Methoden in den ersten 40% zu benutzen und erst dann zu checkpointen. Dies reduziert die Kosten für die Fehlertoleranz um ca. 40%. Wir reduzieren die Checkpointkosten von ZFP weiter, indem wir differenzielle Checkpoints schreiben. Wir schreiben einen ZFP Checkpoint, gefolgt von drei stark komprimierten SZ3 (verlustbehaftete Kompression) Checkpoints, die die Differenz zum letzten ZFP Checkpoint speichern. Dies senkt die Kosten des checkpointens um weitere 12%. Unsere adaptive Methode benötigte in den meisten von unseren Experimenten keine extra Iterationen wenn ein Fehler aufgetreten ist und erhöht die Gesamtlaufzeit nur um 1∼2%.