Towards Fast and Adaptive Byzantine State Machine Replication for Planetary-Scale Systems

  • State machine replication (SMR) is a classical approach for building resilient distributed systems. In Byzantine fault-tolerant (BFT) systems, no concrete assumptions are made about the behavior of faulty replicas. With the advancement of distributed ledger technologies (DLT), planetary-scale BFT SMR ist becoming practical and necessary as it can serve as a consensus primitive to keep the ledger consistent. In our view, the alignment of BFT SMR to DLT brings new challenges, for instance the scalability aspect, where recent research works less frequently address latency improvements than throughput improvements. Further challenges include the geographic dispersion of replicas within a planetary-scale system and the need of a BFT SMR protocol to react to environmental changes during runtime. This thesis has the objective to improve BFT SMR for planetary-scale systems by lowering the protocol latency observed by clients and by making the BFT SMR system adaptive, i.e., enabling replicas to react to perceived changes such as changingState machine replication (SMR) is a classical approach for building resilient distributed systems. In Byzantine fault-tolerant (BFT) systems, no concrete assumptions are made about the behavior of faulty replicas. With the advancement of distributed ledger technologies (DLT), planetary-scale BFT SMR ist becoming practical and necessary as it can serve as a consensus primitive to keep the ledger consistent. In our view, the alignment of BFT SMR to DLT brings new challenges, for instance the scalability aspect, where recent research works less frequently address latency improvements than throughput improvements. Further challenges include the geographic dispersion of replicas within a planetary-scale system and the need of a BFT SMR protocol to react to environmental changes during runtime. This thesis has the objective to improve BFT SMR for planetary-scale systems by lowering the protocol latency observed by clients and by making the BFT SMR system adaptive, i.e., enabling replicas to react to perceived changes such as changing network characteristics or faulty replicas. As a first contribution of this thesis, we discover that fast, consensus-free (read-only) operations is a flawed optimization in seminal BFT SMR frameworks, such as PBFT and BFT-SMaRt. We explain how the read-only optimization can violate the protocol's liveness by showing an attack and then present a solution that makes the overall, optimized protocol both live and linearizable. The second contribution is Adaptive Wide-Area Replication (AWARE), which enables a geo-replicated system to adapt to its environment, thus improving the geographical scalability of consensus if replicas are dispersed across the world. Essentially, AWARE is an automated and dynamic voting-weight tuning and leader positioning scheme, which supports the emergence of fast consensus quorums in the system and builds upon previous work, the WHEAT protocol. AWARE combines reliable self-monitoring with a consensus latency prediction model, thus striving to minimize the system’s consensus latency at runtime, which subsequently results in latency improvements observed by clients scattered across the globe, which we validate through experiments. The third contribution presents FlashConsensus, a protocol derived from AWARE, that also adjusts the resilience threshold. The core idea is the tentative use of a lower resilience threshold which leads to smaller consensus quorums and thus consensus acceleration in common-case scenarios where we expect only few faulty replicas. FlashConsensus achieves threat-level awareness through the incorporation of two modes of operation and BFT forensic support and guarantees liveness and linearizability under optimal resilience. Moreover, FlashConsensus allows for client-side speculation by using incremental consistency guarantees to further lower request latency. Additionally, we investigate on the question whether we can reason about the performance of large-scale systems utilizing simulations. We discover, that we can faithfully forecast the performance of BFT protocols by plugging real protocol implementations into a high-performance network simulator. For instance, simulation results reveal that, using 51 replicas scattered across the planet, FlashConsensus can finalize operations in less than 0.4 s, which is half of the time required for a PBFT-like protocol in the same network, and matching the latency of this protocol running on the best possible internet links (transmitting at 67% of the speed of light).show moreshow less
  • Die Zustandsmaschinenreplikation (ZMR) ist ein klassischer Ansatz für zuverlässige verteilte Systeme. In Byzantinischen fehlertoleranten (BFT) Systemen werden keine konkreten Annahmen über das Verhalten von fehlerhaften Replikaten gemacht. Mit dem Voranschreiten der sog. „Distributed Ledger Technologien“ (DLT) wird planetare BFT ZMR praktikabel und notwendig, da sie als Konsensusprimitiv dienen kann, um die Konsistenz einer Blockchain aufrechtzuerhalten. Unserer Ansicht nach bringt die Ausrichtung von BFT ZMR an DLT neue Herausforderungen mit sich, z.B. den Skalierbarkeitsaspekt, bei dem jüngste Forschungsarbeiten seltener Latenzverbesserungen als Durchsatzverbesserungen untersuchen. Weitere Herausforderungen umfassen die geografische Verteilung von Replikaten innerhalb eines planetaren Systems sowie die Notwendigkeit eines BFT ZMR Protokolls während der Laufzeit auf Veränderungen zu reagieren. Diese Dissertation verfolgt das Ziel, die BFT ZMR für planetare Systeme durch Senkung der von Clients beobachteten Protokolllatenz zuDie Zustandsmaschinenreplikation (ZMR) ist ein klassischer Ansatz für zuverlässige verteilte Systeme. In Byzantinischen fehlertoleranten (BFT) Systemen werden keine konkreten Annahmen über das Verhalten von fehlerhaften Replikaten gemacht. Mit dem Voranschreiten der sog. „Distributed Ledger Technologien“ (DLT) wird planetare BFT ZMR praktikabel und notwendig, da sie als Konsensusprimitiv dienen kann, um die Konsistenz einer Blockchain aufrechtzuerhalten. Unserer Ansicht nach bringt die Ausrichtung von BFT ZMR an DLT neue Herausforderungen mit sich, z.B. den Skalierbarkeitsaspekt, bei dem jüngste Forschungsarbeiten seltener Latenzverbesserungen als Durchsatzverbesserungen untersuchen. Weitere Herausforderungen umfassen die geografische Verteilung von Replikaten innerhalb eines planetaren Systems sowie die Notwendigkeit eines BFT ZMR Protokolls während der Laufzeit auf Veränderungen zu reagieren. Diese Dissertation verfolgt das Ziel, die BFT ZMR für planetare Systeme durch Senkung der von Clients beobachteten Protokolllatenz zu verbessern und die BFT ZMR-Systeme anpassungsfähig zu machen, indem Replikate auf wahrgenommene Änderungen wie sich ändernde Netzwerkcharakteristiken oder fehlerhafte Replikate reagieren können. Als erster Beitrag dieser Dissertation zeigen wir, dass schnelle, konsensusfreie (nur-lesende) Operationen in grundlegenden BFT ZMR Protokollen, wie PBFT und BFT-SMaRt, eine fehlerhafte Optimierung sind. Wir erklären, wie die nur-lesende Optimierung die Liveness (Verfügbarkeit von Operationen) des Protokolls verletzen kann, indem wir einen Angriff präsentieren und dann eine Lösung vorschlagen, die das insgesamt optimierte Protokoll sowohl live (verfügbar) als auch linearisierbar („linearizable“ -- streng konsistent) macht. Der zweite Beitrag ist Adaptive Wide-Area Replication (AWARE), mit der ein geo-repliziertes System sich an seine Umgebung anpassen kann und damit die geografische Skalierbarkeit des Konsensus verbessert, wenn Replikate auf der ganzen Welt verteilt sind. Im Wesentlichen ist AWARE ein automatisches und dynamisches Stimmgewichtseinstellungs- und Anführerpositionierungs-schema, das die Entstehung schneller Konsensusquoren im System unterstützt und auf früheren Arbeiten, wie dem WHEAT-Protokoll, aufbaut. AWARE kombiniert zuverlässige Selbstüberwachung mit einem Konsensuslatenzvorhersagemodell und strebt danach, die Konsensuslatenz des Systems zur Laufzeit zu minimieren, was letztendlich zu Latenzgewinnen führt, die von Clients auf der ganzen Welt beobachtbar sind, was wir durch Experimente bestätigen. Der dritte Beitrag stellt FlashConsensus vor, ein Protokoll, das aus AWARE abgeleitet ist und auch die Resilienzschwelle anpasst. Die Kernidee ist die vorübergehende Verwendung einer niedrigeren Resilienzschwelle, die zu kleineren Konsensusquoren und damit zu einer Beschleunigung des Konsensus in häufigen Fällen führt, in denen nur wenige fehlerhafte Replikate erwartet werden. FlashConsensus erkennt und reagiert auf Bedrohungen durch die Einbeziehung von zwei Betriebsarten und BFT-Forensikunterstützung und garantiert Liveness sowie Konsistenz unter optimaler Resilienz. Darüber hinaus ermöglicht es die Spekulation auf Clientseite durch die Verwendung inkrementeller Konsistenzgarantien, um die Clientlatenz weiter zu senken. Zusätzlich werden wir uns mit der Frage beschäftigen, ob wir die Performanz von groß-skalierten Systemen mittels Simulationen beurteilen können. Wir stellen fest, dass wir die Performanz von BFT Protokollen durch das Einstöpseln von echten Protokollimplementierungen in einen hochleistungsfähigen Netzwerksimulator zuverlässig vorhersagen können. Beispielsweise zeigen Simulationen, dass FlashConsensus mit 51 Replikaten, die auf der ganzen Welt verteilt sind, Operationen in weniger als 0,4 s linearisierbar verarbeiten kann, was die Hälfte der Zeit ist, die für ein PBFT-ähnliches Protokoll im gleichen Netzwerk erforderlich ist und ähnlich schnell ist wie dieses Protokoll mit bestmöglichen Internetverbindungen (Übertragung mit 67% der Lichtgeschwindigkeit).show moreshow less

Download full text files

Export metadata

Metadaten
Author:Christian BergerORCiD
URN:urn:nbn:de:bvb:739-opus4-15059
Advisor:Hans P. Reiser, Jérémie Decouchant
Document Type:Doctoral Thesis
Language:English
Year of Completion:2024
Date of Publication (online):2024/11/06
Date of first Publication:2024/11/06
Publishing Institution:Universität Passau
Granting Institution:Universität Passau, Fakultät für Informatik und Mathematik
Date of final exam:2024/10/28
Release Date:2024/11/06
Tag:Byzantine fault tolerance; adaptiveness; consensus; planetary-scale; state machine replication
Page Number:ix, 181 Seiten
Institutes:Fakultät für Informatik und Mathematik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
open_access (DINI-Set):open_access
Licence (German):License LogoCreative Commons - CC BY-SA - Namensnennung - Weitergabe unter gleichen Bedingungen 4.0 International