Many distributed systems require coordination between the servers involved. At the same time, with increasing number of servers, these systems become more prone to single-server failures. Therefore, a high-quality service deployed on these systems must enable coordination, while tolerating failures. This can be achieved through state-machine replication. State-machine replication is fault tolerant through redundancy and coordination is achieved through strong consistency. This in turn requires ordering user requests and propagating them to all replicas, which execute them deterministically and sequentially, i.e., in total order. Guaranteeing this total order requires the execution of a distributed agreement algorithm, such as consensus or atomic broadcast. Consequently, strong consistency adds a considerable performance overhead, with typical state-machine replication request rates being orders of magnitude lower than the request rates of non-replicated services. The aim of this dissertation is to devise new efficient solutions that reduce this performance overhead. This dissertation presents three novel algorithms -- DARE, AllConcur, and AllConcur+ -- that stretch the performance boundaries of state-machine replication. The three algorithms target two contrasting use cases of replication -- replicating a service as a mechanism to achieve high availability and replicating a service as a requirement of the application. Replication is a well-known approach to high availability. Providing strong consistency among replicas, allows a distributed service to hide failures and appear to its users as a coherent and centralized service. In such cases, scaling out state-machine replication to more than a handful of servers is not necessary. However, most existing algorithms rely on message-passing for communication. DARE is a novel high-performance state-machine replication algorithm that replaces the message-passing mechanism with remote direct memory access (RDMA) one-sided primitives. Therefore, DARE enables operators to fully utilize the new capabilities of the growing number of RDMA-capable networks. Besides providing high availability, having multiple consistent replicas may be a requirement of the application, as is the case for distributed ledgers. In such cases, scaling out to hundreds of servers is not uncommon. Most practical state-machine replication approaches were designed mainly to enable highly available distributed services and they are not well suited for large-scale deployments. AllConcur is a novel leaderless concurrent atomic broadcast algorithm that enables state-machine replication to scale out to hundreds of servers, while achieving high performance. Besides adopting a decentralized approach, AllConcur reduces the work by replacing the traditional all-to-all communication pattern adopted by many existing algorithms with a digraph-based communication model that relies on a sparse digraph. This results in sublinear work per broadcast message and is the main reason for the high performance at scale. Moreover, AllConcur employs a novel early termination mechanism that reduces latency. As a result, AllConcur is highly competitive with regard to existing solutions at scale and outperforms standard leader-based approaches, such as Libpaxos. The sparse digraph used by AllConcur for communication reduces the work per broadcast message. However, to reliably disseminate messages, the digraph must also be resilient; this resiliency entails redundancy, which limits the reduction of work. AllConcur+ is a novel leaderless concurrent atomic broadcast algorithm that lifts this limitation by adopting a dual-digraph approach: During intervals with no failures, it achieves minimal work by using a redundancy-free digraph. When failures do occur, it automatically recovers by switching to the resilient digraph. As a result, by leveraging redundancy-free execution during intervals with no failures, AllConcur+ achieves significantly higher throughput and lower latency than both AllConcur and other state of the art atomic broadcast algorithms. Overall, this dissertation addresses the challenges of designing novel algorithms with the purpose of enhancing the performance of state-machine replication for both small- and large-scale deployments. We believe that the research contributions made by the three algorithms presented will serve as a good foundation for many use cases and furthermore facilitate the future improvements of state-machine replication.

Viele verteilte Systeme erfordern Koordination zwischen den beteiligten verteilten Ressourcen. Gleichzeitig werden diese Systeme mit zunehmender Anzahl von Ressourcen anfälliger auf Ausfälle einzelner Ressourcen. Um auf einem solchen System eine hochwertige Anwendung mit hoher Verfügbarkeit bereitstellen zu können, müssen die Ressourcen koordiniert und gleichzeitig Ausfälle toleriert werden können. Dies kann durch State-Machine Replication (SMR) gewährleistet werden. SMR aufgrund ihrer Redundanz fehlertolerant und die Koordination wird durch starke Konsistenz erreicht. SMR erfordert jedoch die Kommunikation aller Befehle (Benutzeranfragen) an alle Repliken und zugleich deren strikte Ordnung: dadurch kann jede Replik alle Befehle deterministisch und sequentiell ausführen. Diese totale Ordnung lässt sich durch spezielle Algorithmen für Konsensus bzw. atomarer Broadcast erreichen. Die Verwendung von SMR ist jedoch mit erheblichen Kosten. Typische Anfrageraten sind für SMR um Größenordnungen niedriger für nicht-replizierte Anwendungen. Das Ziel dieser Doktorarbeit ist neue effiziente Lösungen zu entwickeln, die die Kosten für den Einsatz von SMR reduzieren. In dieser Doktorarbeit werden drei neue Algorithmen ausgearbeitet, DARE, AllConcur und AllConcur+, die die Leistungsgrenzen von SMR signifikant erweitern. Die Algorithmen zielen auf unterschiedliche Anwendungsszenarien ab: replizieren einer Anwendung für maximale Verfügbarkeit, bzw. skalierbare Replikation einer Anwendung. Replikation ist eine bekannte Methode für Verfügbarkeit. Durch die starke Konsistenz unter den Repliken kann ein verteilte Anwendung Hardware-Ausfälle verbergen und für seine Benutzern kohärent und zentralisiert auftreten. Die meisten verfügbaren Algorithmen realisieren solche SMR durch explizite Kommunikation mittels Nachrichten. DARE ist ein neuartiger, hochperformanter SMR Algorithmus, der diese Kommunikation mittels Remote Direct Memory Access (RDMA) realisiert. Dadurch ermöglicht es DARE, die volle Funktionalität neuartiger, RDMA-fähiger Netzwerke für SMR zu nutzen. Skalierbare Replikation kann eine intrinsische Anforderung einer Anwendung sein, beispielsweise bei Distributed Ledger. In solchen Fällen ist eine Skalierung auf Hunderte von Ressourcen nicht ungewöhnlich. Die meisten SMR Algorithmen wurden für hohe Verfügbarkeit der Anwendungen entworfen und eignen sich nicht für hohe Skalierung. AllConcur ist ein neuartiger Algorithmus für atomaren Broadcast, der ohne Anführer auskommt und es ermöglicht, SMR mit hoher Performanz auf Hunderte von Ressourcen zu skalieren. Neben dem Verzicht auf einen Anführer, wodurch eine bessere Skalierung gewährleistet werden kann, reduziert AllConcur die Kosten weiter, indem das traditionelle All-to-All Kommunikationsmuster durch einen dünnbesetzten Digraphen. Dies ermöglicht sublinearer Kosten pro Benutzeranfrage. Dazu kommt, dass AllConcur einen neuartigen Mechanismus zur frühzeitigen Beendung des atomaren Broadcasts verwendet. Infolgedessen übertrifft AllConcur die Performanz herkömmlicher Algorithmen wie Libpaxos signifikant für hochskalige Anwendungen. Der dünnbesetzte Digraph, den AllConcur für die Kommunikation verwendet, muss jedoch auch robust sein, um fehlertolerant zu sein. Dies hat Redundanz zur Folge, die maximale Performanz begrenzt. AllConcur+ ist ein neuartiger Algorithmus, der diese Einschränkung umgeht, indem er zwischen zwei Digraphen hin und her wechselt: In Intervallen ohne Hardware-Ausfälle wird durch Verwendung eines redundanzfreien Digraphen maximale Performanz erzielt. Wenn doch Ausfälle auftreten, schaltet AllConcur+ automatisch auf den fehlertoleranten Digraphen um. Während Intervallen ohne Ausfälle erreicht AllConcur+ somit signifikant höhere Performanz als AllConcur, sowie andere moderne atomare Broadcast Algorithmen. Insgesamt behandelt diese Dissertation die Herausforderungen beim Entwurf neuartiger Algorithmen mit dem Ziel, die Performanz von SMR sowohl für klein- als auch großskalige Anwendungen zu verbessern. Wir glauben, dass die hier vorgestellten Forschungsbeiträge eine solide Grundlage für zahlreiche Anwendungsfälle, sowie für algorithmische Weiterentwicklungen darstellen.

Aktualisierung der zweiten Seite der Dissertation: Vervollständigung der Gutachter