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.