Web-basierte Online-Dienste beinhalten in zunehmendem Maße die Verarbeitung sensibler personenbezogener Daten. Die steigende Tendenz, solche Daten in der “Cloud” zu speichern und zu verwalten, erh¨oht den Bedarf verlässlicher Realisierungen dieser Funktionen für eine steigende Anzahl Web-basierter Anwendungen, wie etwa E-Mail, Kalender, Fotoalben oder Online-Banking. Dieser Trend erklärt die zunehmende Verwendung fehlertoleranter Replikationsalgorithmen bei der Implementierung Web-basierter Anwendungen. Die zur Anwendung kommenden Implementierungen reichen von klassischer, stark konsistenter Replikation in Systemen wie Chubby [Bur06] und ZooKeeper [HKJR10] hin zu hochverfügbarer, schwach konsistenter Replikation, etwa in Amazons Dynamo [DHJ+07] oder Yahoo!s PNUTS [CRS+08]. Die vorliegende Arbeit stellt neuartige Algorithmen für fehlertolerante Replikation vor, mit dem Ziel die Effizienz, Verfügbarkeit und Wirtschaftlichkeit dieser Mechanismen zu erhöhen. Wenngleich die vorgestellten Algorithmen allgemein anwendbar sind, erfüllen sie zwei Eigenschaften, die wesentlich durch den Einsatz in Web-basierten Systemen motiviert sind. Die erste Eigenschaft ist die Toleranz von Worstcase-Fehlern, in der Literatur auch als “Byzantine” [LSP82a] bezeichnet, um eine zuverlässige Verarbeitung sensibler personenbezogener Daten zu gewährleisten. Die zweite Eigenschaft ist die Entwicklung einer geeigneten Semantik schwacher Konsistenz für Systeme, für die höchstmögliche Verfügbarkeit und geringstmöglicher Zusatzaufwand hinsichtlich Performanz und Replikation sicherzustellen, Abschwächungen der Konsistenz aber weitgehend zu vermeiden sind. Toleranz von “Byzantine” Fehlern: Die Toleranz von “Byzantine” Fehlern (englisch Byzantine Fault Tolerance, BFT) wurde kürzlich zum Gegenstand intensivierter Forschung mit dem vordergründigen Ziel, ihren implizierten Zusatzaufwand (bzgl. Performanz und erforderlicher Replikation) auf ein Maß zu reduzieren, das mit dem herkömmlicher Fehlertoleranzmechanismen vergleichbar ist. BFT wird zumeist durch die Replikation von Zustandsautomaten erzielt, indem die Illusion eines einzelnen zuverlässigen Servers durch die (für den Nutzer transparente) Koordination mehrerer unzuverlässiger Server erzeugt wird [Sch90]. Als ultimatives Ziel dieser Forschungsrichtung ist die Anwendbarkeit dieses Ansatzes für Web-basierte Systeme zu sehen [CKL+09], um die so implementierten kritischen Anwendungen vor folgenschwerem Fehlverhalten, wie es etwa in [Das] beschrieben ist, zu schützen. Die vorliegende Arbeit stellt neue Algorithmen vor, die den Performanz- und Replikationsaufwand von BFT reduzieren. Zunächst wird gezeigt, wie dieses Ziel ohne die Annahme vertrauenswürdiger Komponenten erreicht werden kann. Nach der Vorstellung des einflussreichen PBFT-Algorithmus [CL99] wurde eine Reihe schneller BFT-Algorithmen, wie zum Beispiel [MA06; DGV04; KAD+07] entwickelt. Diese Arbeiten zeigen unter der Annahme fehlerbehafteter Repliken einen inhärenten Kompromiss zwischen optimaler Redundanz und minimaler Latenz auf. In Web-basierten Systemen, in denen “Byzantine” Fehler nur selten, Ausfälle von Repliken hingegen häufig auftreten, stellt sich dieser unvermeidbare Kompromiss als problematisch heraus. Der in dieser Arbeit vorgestellte Algorithmus “Scrooge” reduziert den Replikationsaufwand schneller BFT-Replikation in Gegenwart nicht reagierender Repliken. Scrooge zeigt, dass der zusätzliche Replikationsaufwand zur Erzielung einer höheren Geschwindigkeit ausschließlich von der Anzahl der zu tolerierenden fehlerbehafteten Repliken abhängt und nicht von der Anzahl zu tolerierender Ausfälle. Als Konsequenz erzielt Scrooge optimale Robustheit für die Toleranz eines einzelnen “Byzantine”-Fehlers und einer beliebigen Anzahl von Ausfällen. Solche Szenarien sind charakteristisch für Web-basierte Systeme, in denen “Byzantine”-Fehler selten sind. Anschließend daran untersucht die vorliegende Arbeit potenzielle Vorteile der Verwendung vertrauenswürdiger Komponenten. Es wird gezeigt, dass diese zu einer signifikanten Reduktion der Latenz und durch Redundanz verursachten Kosten in anwendungstypischen asynchronen Systemen führen können [SS07]. Dies verwirft die These früherer Arbeiten [CNV04; Ver06], dass eine Kostenre- duktion durch vertrauenswürdige Komponenten zwingend die Verfügbarkeit synchroner Kommunikationskanäle erfordert. Diese zusätzliche Forderung nach Synchronität führt zu einer deutlichen Beschränkung möglicher Einsatzgebiete bestehender Lösungen, beispielsweise in Web-basierten Systemen. In dreistufig organisierten Web-basierten Systemen, zum Beispiel, kann man sich zunutze machen, dass Server in der ersten Ebene des Systems (die Webserver) üblicherweise standardisiert, stabiler und weniger fehleranfällig sind als beispielsweise Application- Server. Der “HeterTrust” Protokoll, der in dieser These eingeführt wird, erfordert eine zur Anzahl der zu tolerierenden Fehler lineare Anzahl von Repliken um die Vertraulichkeit von Daten sicher zu stellen, und hat konstante Komplexität. Dies ist eine Deutliche Verbesserung gegenüber bestehenden Ansätzen, die zwar keine vertrauenswürdigen Komponenten erfordern, aber quadratische Redundanzkosten und lineare Latenzen mit sich bringen [YMV+03]. Ebenfalls im Gegensatz zu anderen die Vertraulichkeit berücksichtigenden BFT-Ansätzen verwendet HeterTrust symmetrische Kryptoverfahren anstelle von Public-Key-Verfahren. HeterTrust beinhaltet einige interessante Ideen in den Bereichen der Spekulation [KAD+07] und der Toleranz von Denial-of-Service-Angriffen [ACKL08; CWA+09], deren Eigenschaften in weiteren Arbeiten untersucht und in unmittelbarer Folge von [SS07] publiziert wurden. In der selben Zeit wie der vorliegende Arbeit wurde die Verwendung vertrauenswürdiger Komponenten in asynchronen Systemen unabhängig in [CMSK07] untersucht. Schwache Konsistenz: Für einige Web-basierte Anwendungen ist die Zusicherung starker Konsistenzeigenschaften wie Linearisierbarkeit nicht möglich [HW90]. Die Ursache dafür liegt in der Unmöglichkeit einer Implementierung von “Shared Objects”, wie zum Beispiel Databases, in Fällen von Partitionierung oder Asynchronität [GL02]. Allerdings geben bis auf wenige Ausnahmen alle diese Systeme Linearisierbarkeit auch in Betriebsabschnitten auf, in denen weder Partitionierung, noch Asynchronität vorliegen. Da dieser Lockerung der Konsistenz für einige Anwendungen problematisch ist, konzentriert sich neuliche Forschung auf stärkere Konsistenzeigenschaften, die sich mit Hochverfügbarkeit kombinieren lassen. Die vorliegende Arbeit führt “Eventual Linearizability” als neue Konsistenzeigenschaft ein, die eine Verletzung der Linearisierbarkeit für endliche Zeitabschnitte gestattet. Sie beschreibt weiterhin Aurora, einen Algorithmus zur Sicherstellung von Linearisierbarkeit in Phasen, in denen ein einzelner Leader im System vorhanden ist. Die Leistungsfähigkeit von Aurora vermindert sich schrittweise im Falle sich verschlechternder Ausführungsbedingungen. Aurora verwendet einen einzelnen a priori nicht näher bestimmten Fehlerdetektor, von dessen Stärke aber Eigenschaften Auroras abhängen. “Eventual Linearizability” erfordert einen <>S Fehlerdetektor. In Phasen von Asynchronität, in denen die Pünktlichkeit von Nachrichten und die Präsenz eines einzelnen Leaders nicht gewährleistet werden kann, reduziert sich die von Aurora getroffene Zusicherung auf “Eventual Consistency” [FGL+96; Vog09] und “Causal Consistency” [Lam78]. Für diese Eigenschaften benötigt Aurora lediglich einen Fehlerdetektor C mit “Strongly Complete”-Eigenschaft. Für die Durchführung sogenannter “Strong Operations”, die “Linearizability” erfordern, wird ein <>P Fehlerdetektor verwendet. Dieser ist stärker als <>S, welches der schwächste Fehlerdetektor für die Implementierung von “Consensus” ist [CHT96] und somit auch “Linearizable Shared Objects”. Die vorliegende Arbeit zeigt, dass ein inhärenter Aufwand bei der Kombination von “Eventual Linearizability” und “Linearizability” existiert.