Probabilistic Quorum Systems for Dependable Distributed Data Management
Buch in deiner Nähe kaufen
Beschreibung
Unter fehleranfälligen, dynamischen, verteilten Systemen gibt es eine bedeutende Klasse von Systemen, die nach hoher Verfügbarkeit streben und mit inkonsistenten Daten umgehen können. Beispiele dafür sind Flugreservierungssysteme, die Überbuchungen erlauben, oder Rettungsdienstsysteme, die nicht immer korrekte – aber für eine Entscheidung ausreichende – Antworten geben. Datenreplikation ist eine bekannte Technik in verteilten Systemen, um Fehler zu tolerieren und Daten zuverlässig zu verwalten. Dafür werden oftmals Quoren benutzt, um Basisoperationen (neue Daten schreiben und vorher geschriebene Daten lesen) durchzuführen. Strikte Quorensysteme basieren auf einem strikten Konsistenzbegriff, der sogenannten sequentiellen Konsistenz. Dieser stellt den gegenseitigen Ausschluss konkurrierender Lese- und Schreiboperationen, bzw. zweier konkurrierender Schreiboperationen sicher. Die Gewährleistung der strikten Konsistenz beschränkt die Verfügbarkeit der Operationen. Probabilistische Quorensysteme erhöhen die Verfügbarkeit der Operationen durch die Abschwächung der vorher genannten gegenseitigen Ausschlüsse. Diese Abschwächung bezieht sich auf die Wahrscheinlichkeit der Überschneidung von Lese- und Schreibquoren, bzw. Schreib- und Schreibquoren: sie werden nur noch mit hoher Wahrscheinlichkeit gewährleistet.
Die Arbeit befasst sich mit der Konstruktion probabilistischer Quorensysteme, die auf strikten Quorensystemen als Eingabe basieren. Die Erzeugung, die Auswahl und die Integration der Quoren werden als Schritte der Konstruktion identifiziert. Im Integrationsschritt werden unterschiedliche Prioritäten für die Kombinati-on strikter und probabilistischer Quoren betrachtet, um unterschiedliche probabilistische Quorensysteme als Ergebnis zu erzielen. Diese Kombinationsarten der Quoren werden Integrationsstrategien genannt.
Danach erfolgt eine Analyse verschiedener probabilistischer Quorensysteme, resultierend aus den Konstruktionen, bzgl. des Trade-offs zwischen Datenkonsistenz und Operationsverfügbarkeiten. Die empirischen Ergebnisse der Markowkettenanalyse deuten stark darauf hin, dass bezüglich der Datenkonsistenz eine Ordnung zwischen den eingeführten Integrationsstrategien existiert. Schließlich geht es um die Optimierung probabilistischer Quorensysteme bzgl. Datenkonsistenz und Operationsverfügbarkeiten. In diesem Kontext wird ein graphisches Maß für die Datenkonsistenz eingeführt. Obwohl dieses Maß abstrakter ist als jenes, welches in der Markowkettenanalyse verwendet wurde, es ermöglicht die Identifizierung Quorensystemen, die maximale Datenkonsistenz bzgl. eines anderen Quorensystems und einer vorgegebenen, festen Operation haben.
Die Ergebnisse bzgl. der Integrationsstrategien werden abschließend formal bewiesen und verallgemeinert.
Autor*in
Kinga Kiss Iakab
Themen in »Probabilistic Quorum Systems for Dependable Distributed Data Management«
Datenreplikation Datenverfügbarkeit Fehleranfällige Systeme Fehlertoleranz Markowkettenanalyse Quoren Quorensysteme