TU Darmstadt / ULB / tuprints

Time-Efficient Asynchronous Service Replication

Dobre, Dan :
Time-Efficient Asynchronous Service Replication.
TU Darmstadt
[Ph.D. Thesis], (2010)

[img]
Preview
PDF
thesis.pdf
Available under Creative Commons Attribution Non-commercial No Derivatives.

Download (1409Kb) | Preview
Item Type: Ph.D. Thesis
Title: Time-Efficient Asynchronous Service Replication
Language: English
Abstract:

Modern critical computer applications often require continuous and correct operation despite the failure of critical system components. In a distributed system, fault-tolerance can be achieved by creating multiple copies of the functionality and placing them at different processes. The core constitutes a distributed protocol run among the processes whose goal is to provide the end user with the illusion of sequentially accessing a single correct copy. Not surprisingly, the efficiency of the distributed protocol used has a severe impact on the application performance. This thesis investigates the cost associated with implementing fundamental abstractions constituting the core of service replication in asynchronous distributed systems, namely (a) consensus and (b) the read/write register. The main question addressed by this thesis is how efficient implementations of these abstractions can be. The focus of the thesis lies on time complexity (or latency) as the main effciency metric, expressed as the number of communication steps carried out by the algorithm before it terminates. Besides latency, important cost factors are the resilience of an algorithm (i.e. the fraction of failures tolerated) and its message complexity (the number of messages exchanged). Consensus is perhaps the most fundamental problem in distributed computing. In the consensus problem, processes propose values and unanimously agree on one of the proposed values. In a purely asynchronous system, in which there is no upper bound on message transmission delays, consensus is impossible if a single process may crash. In practice however, systems are not asynchronous. They are timely in the common case and exhibit asynchronous behavior only occasionally. This observation has led to the concept of unreliable failure detectors to capture the synchrony conditions sufficient to solve consensus. This thesis studies the consensus problem in asynchronous systems in which processes may fail by crashing, enriched with unreliable failure detectors. It determines how quickly consensus can be solved in the common case, characterized by stable executions in which all failures have reliably been detected, settling important questions about consensus time complexity. Besides consensus, the read/write register abstraction is essential to sharing information in distributed systems, also referred to as distributed storage for its importance as a building-block in practical distributed storage and le systems. We study fault-tolerant read/write register implementations in which the data shared by a set of clients is replicated on a set of storage base objects. We consider robust storage implementations characterized by (a) wait-freedom (i.e. the fact the read/write operations invoked by correct clients always return) and (b) strong consistency guarantees despite a threshold of object failures. We allow for the most general type of object failure, Byzantine, without assuming authenticated data to limit the adversary. In this model, we determine the worst-case time complexity of accessing such a robust storage, closing several fundamental complexity gaps.

Alternative Abstract:
Alternative AbstractLanguage
Für moderne sicherheitskritische Computeranwendungen ist eine ununterbrochene und fehlerfreie Funktion erforderlich, oft auch dem Ausfallkritischer Systemkomponenten zum Trotz. In einem verteilten System kann Fehlertoleranz dadurch erreicht werden, dass mehrere identische Kopien einer Applikation erstellt, und auf verschiedene, möglicherweise fehleranfällige Prozesse plaziert werden. Kern dieses Verfahrens ist ein verteiltes Protokoll, das von den Prozessen im verteilten System ausgeführt wird, mit dem Ziel eine einzelne und ausfallsichere Kopie zu simulieren. Endbenutzern wird der Eindruck vermittelt, auf eine korrekte, hochverfügbare Kopie sequentiell zuzugreifen. Wie nicht anders zu erwarten hat die Effizienz des verwendeten, verteilten Protokolls eine signifikante Auswirkung auf die Performanz der Applikation. Diese Dissertation untersucht die Kosten grundlegender Abstraktionen verteilten Rechnens, die den Kern der Replikation von Diensten in verteilten Systemen bilden, nämlich (a) Consensus und (b) das Lese-/Schreibregister. Die Hauptfragestellung dieser Arbeit ist wie effizient Implementierungen dieser Abstraktionen überhaupt sein können. Dabei liegt das Augenmerk der Dissertation auf der Zeitkomplexität (oder Latenzzeit) als maßgebliche Effizienzmetrik, gegeben durch die Anzahl der Kommunikationsphasen (oder -schritte) die ein verteiltes Protokoll benötigt bevor es terminieren kann. Zwei wichtige Kostenfaktoren neben der Latenzzeit sind die Ausfallsicherheit (die Anzahl der tolerierten Ausfälle) und die Nachrichtenkomplexität (die Anzahl der gesendeten Nachrichen) eines Protokolls. Consensus ist höchstwahrscheinlich das grundlegendste Problem auf dem Gebiet des verteilten Rechnens. Es kann wie folgt beschrieben werden: Prozesse schlagen jeweils einen Wert vor und müssen sich auf einen der vorgeschlagenen Werte einigen. In einem rein asynchronen System, in dem keine oberen Schranken für die Kommunikationszeit zwischen Prozessen existieren, ist Consensus unlösbar, selbst wenn nur ein einziger Prozess ausfallen darf. In der praktischen Anwendung sind allerdings solche Systeme meistens synchron (d.h. es gibt solche oberen Schranken), und sie verhalten sich nur gelegentlich asynchron. Diese Beobachtung führte zu dem Konzept des unverlässlichen Fehlerdetektors, der die hinreichenden Synchronitätsbedingungen für die Lösbarkeit von Consensus erfasst und abstrahiert. Diese Arbeit untersucht das Consensus-Problem in asynchronen Systemen mit Anhalte-Ausfällen von Prozessen, und Verfügbarkeit von Fehlerdetektoren, die auch unverlässliche Angaben über den Fehlerzustand von Prozessen machen dürfen. Es wird ermittelt wie schnell Consensus in Fällen die in der Praxis häufig auftreten gelöst werden kann in, z.B. in sogenannten stabilen Ausführungsinstanzen, in denen geschehene Ausfälle bereits verlässlich erkannt worden sind, und keine weiteren Ausfälle mehr stattfinden. Off ene Fragen nach der Latenzzeit von Consensus werden durch die Ergebnisse dieser Arbeit geklärt. Neben Consensus, ist auch das Lese- und Schreibregister eine grundlegende Abstraktion auf dem Gebiet des verteilten Rechnens, und ermöglicht den Prozessen in einem verteilten System auf gemeinsame Daten zuzugreifen. Das Lese- und Schreibregister wird oft auch, wegen seiner Relevanz als Baustein in praktischen verteilten Speicher- und Dateisystemen, als Storage bezeichnet. Diese Dissertation erforscht fehlertolerante Storage-Implementierungen, in denen Daten, die von Clients gemeinsam genutzt werden, aus Gründen der Verlässlichkeit und Hochverfügbarkeit auf mehrere Storage-Server repliziert und damit redundant gespeichert werden. Es werden robuste Storage-Implementierungen betrachtet, die sich (a) durch Wartefreiheit (d.h. von korrekten Clients aufgerufene Lese- und Schreiboperationen müssen stets terminieren) und (b) durch starke Konsistenzeigenschaften auszeichnen, trotz der Fehlfunktion von Storage-Servern und Clients. Das untersuchte Systemmodell erlaubt die allgemeinste Klasse von Funktionsfehlern, sogenannte Byzantinische Fehler, ohne eine Authentizierung der Daten anzunehmen um den Angreifer zu begrenzen. In diesem Rahmen wird die Worst-Case Latenzzeit von Lese- und Schreibzugriff en auf ein robustes Storage untersucht und ermittelt, und dadurch werden etliche grundlegende Komplexitätslücken geschlossen.German
Uncontrolled Keywords: Consensus, Distributed Storage, Atomic Broadcast, Byzantine failures, Time-complexity
Alternative keywords:
Alternative keywordsLanguage
Consensus, Distributed Storage, Atomic Broadcast, Byzantine failures, Time-complexityEnglish
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik > Dependable, Embedded Systems & Software Group (DEEDS Group)
Fachbereich Informatik > Theoretische Informatik
Fachbereich Informatik > Datenbanken und Verteilte Systeme
Date Deposited: 05 Oct 2010 09:59
Last Modified: 07 Dec 2012 11:58
URN: urn:nbn:de:tuda-tuprints-23007
License: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0
Referees: Suri, Prof. Neeraj and Raynal, Prof. Michel
Refereed: 30 September 2010
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/2300
Export:

Actions (login required)

View Item View Item