TU Darmstadt / ULB / TUprints

Data Consistency and Coordination for Untrusted Environments

Majuntke, Matthias (2012)
Data Consistency and Coordination for Untrusted Environments.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
dissertation_matthias.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Data Consistency and Coordination for Untrusted Environments
Language: English
Referees: Suri, Prof. Dr. Neeraj ; Fetzer, Prof. Dr. Christof
Date: 19 September 2012
Place of Publication: Darmstadt
Date of oral examination: 21 September 2012
Abstract:

Users of today's computing devices are accustomed to having a permanent and capable connection to the Internet. Personal data and computational tasks are increasingly assigned to online services. Besides many advantages, online services may not be fully trusted by the users as they are usually hosted by a third party provider. Cryptographic techniques are able to prevent a provider from leaking or modifying sensitive user data. However, other attacks are still possible: When clients interact only through an untrusted online service, the latter may send diverging and inconsistent replies. In this context, fork-consistent semantics make it much easier for the clients to detect such violations. They ensure that if an untrusted service only once sent a wrong response to some client, then this client remains forever forked from those other clients to which the service replied differently. If fork-consistency is provided, clients may easily detect service misbehavior by out-of-band communication.

Recent research results have shown that it is impossible to implement a service that provides full consistency and wait-free operations in the fault-free case and gracefully degrades to fork-linearizability, the strongest notion of fork-consistency, if the service acts maliciously. All existing solutions are based on locks, and thus, client operations may block even if the service is correct. This thesis introduces the first lock-free implementations with fork-linearizability, providing abortable (and therefore obstruction-free) operations if the service behaves correctly. In practical settings, obstruction-free solutions can easily be boosted to wait-freedom.

In the context of fork-consistency, the thesis demonstrates that the underlying system assumptions can be significantly reduced. Existing works require the shared service to execute non-trivial computation steps. In the thesis at hand it is shown that for a wide range of fork-consistent implementations a service providing only a simple read/write interface is sufficient. For practical systems this makes a big difference in cost as full-fledged servers are typically more expensive than simple storage devices.

The second part of this thesis deals with the orthogonal question how to implement shared storage abstractions that do not exhibit malicious, i.e., Byzantine faulty, behavior. The basic principle is to achieve Byzantine fault-tolerance by replication over a set of replicas out of which a fraction may act maliciously. The thesis presents lightweight, Byzantine fault-tolerant implementations of an atomic register and a key-value-store as required for many modern services in the cloud. The notion of lightweight comprises several aspects to reduce the costs incurred by replication, e.g., a minimal number of replicas and communication rounds, no employment of self-verifying data, and the support of an unbounded number of possible malicious readers.

Alternative Abstract:
Alternative AbstractLanguage

Die Nutzer aktueller Computergeräte erwarten einen permanenten und leistungsfähigen Zugang zum Internet. Deshalb werden persönliche Daten und Aufgaben zunehmend von Online-Services verarbeitet. Neben vielen gebotenen Vorteilen können Benutzer solchen Services jedoch nicht vollumfänglich vertrauen, da diese Üblicherweise von Drittanbietern bereitgestellt werden. Mithilfe kryptographischer Techniken kann eine nichtauthorisierte Offenlegung oder Änderung von Benutzerdaten durch den Service-Anbieter wirkungsvoll verhindert werden. Andere Angriffe sind jedoch weiterhin möglich: Wenn Clients nur durch einen nicht vertrauenswürdigen Online-Service kommunizieren, kann dieser von\-einander abweichende und inkonsistente Antworten an die Clients versenden. In diesem Kontext erleichtert die Eigenschaft Verzweigungskonsistenz (fork-consistency) es den Clients, ein solches Fehlverhalten des Services zu erkennen. Verzweigungskonsistenz garantiert, dass, sobald ein nicht vertrauenswürdiger Service eine inkonsistente Antwort an einen Client sendet, dieser Client für immer isoliert (und damit verzweigt) von den anderen Clients bleibt. In einem System, das Verzweigungskonsistenz erfüllt, können Clients einen fehlerhaft agierenden Server durch systemexterne Kommunikation leicht detektieren.

Aktuelle Forschungsergebnisse zeigen, dass es nicht möglich ist einen Service zu implementieren, der volle Konsistenz und unabhängig terminierende (wait-free) Operationen im fehlerfreien Fall ermöglicht und, falls sich der Service bösartig verhält, niemals Verzweigungslinearisierbarkeit, die stärkste verzweigungskonsistente Eigenschaft, verletzt. Alle bislang existierenden Ansätze benötigen dafür Locks, so dass Operationen der Clients selbst dann blockieren können, wenn der Service korrekt ist. Diese Dissertation stellt die ersten lock-freien Implementierungen mit Verzweigungslinearisierbarkeit vor, die nebenläufige Operationen abbrechen um ein Blockieren zu verhindern. Für praktische Anwendungen können solche abbrechbaren Operation leicht in unabhängig terminierende Operationen überführt werden.

Weiterhin zeigt die vorliegende Dissertation wie im Kontext von Verzweigungskonsistenz die zugrundeliegenden Systemannahmen signifikant reduziert werden können. In existierenden Ansätzen muss der benötigte, gemeinsam genutzte Service nichttriviale Berechnungsschritte ausführen. In dieser Arbeit wird gezeigt, dass für ein großes Spektrum von verzeigungskonsistenten Implementierungen ein Service ausreicht, der nur eine einfache Schreib/Lese-Schnittstelle bereitstellt. Für Systeme in der Praxis besteht ein großer Kostenunterschied zwischen vollwertigen Servern und einfachen Speichermodulen.

Der zweite Teil der vorliegenden Dissertation behandelt die orthogonale Fragestellung, wie gemeinsam genutzter Speicher implementiert werden kann, der kein fehlerhaftes Verhalten zeigt. Das Grundprinzip ist, durch Replikation Fehlertoleranz gegenüber beliebigen Fehlertypen zu erreichen. Das bedeutet, dass aus einer Menge von replizierten Servern ein Teil der Server beliebiges, fehlerhaftes Verhalten aufweisen kann. In dieser Arbeit werden effiziente, fehlertolerante Implementierungen von atomischen Registern und Key-Value-Stores vorgestellt. Key-Value-Stores werden hauptsächlich in vielen modernen Cloud-Services eingesetzt. Die vorgestellten Implementierungen reduzieren in mehrfacher Hinsicht den durch Replikation verursachten Overhead, z.B.~durch eine minimale Anzahl von Replikas und Kommunikationsrunden, den Verzicht auf Datenauthentifizierung sowie die Unterstützung einer beliebingen Anzahl von möglicherweise bösartigen Lese-Clients.

German
Alternative keywords:
Alternative keywordsLanguage
fork-consistency, Byzantine fault-tolerance, atomic register, shared memory, key-value-storeEnglish
URN: urn:nbn:de:tuda-tuprints-31091
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Dependable Embedded Systems & Software
Date Deposited: 26 Sep 2012 11:54
Last Modified: 09 Jul 2020 00:12
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3109
PPN: 386256403
Export:
Actions (login required)
View Item View Item