Schliessen
Titelaufnahme
Titelaufnahme
- TitelA lightweight approach for state machine replication in server-based and cloud-based systems / Jinfeng Dou ; Advisor: Prof. Dr. Christian Scheideler, Reviewers: Prof. Dr. Christian Scheideler, Prof. Dr. Lin Wang
- Autor
- Gutachter
- Erschienen
- Umfang1 Online-Ressource (ix, 136 Seiten) : Diagramme
- HochschulschriftUniversität Paderborn, Dissertation, 2026
- AnmerkungTag der Verteidigung: 22.10.2026
- Verteidigung2026-10-22
- SpracheEnglisch
- DokumenttypDissertation
- Schlagwörter (GND)
- URN
- DOI
Links
- Social MediaShare
- Nachweis
- IIIF
Download
Klassifikation
Zusammenfassung
Diese Dissertation stellt einen leichtgewichtigen und dezentralisierten Ansatz zur Replikation von Zustandsmaschinen mit kompakten Commitment-Zertifikaten unter adaptiv blockierenden Angreifern vor. Die Arbeit besteht aus zwei komplementären Teilen: einem serverbasierten Modell, das die theoretischen Grundlagen des Ansatzes schafft, und einem cloudbasierten Modell, das diese Grundlagen zu einer skalierbaren verteilten Architektur erweitert. Im serverbasierten Modell passen wir die Medianregel für stabilisierenden Kon- sens [Doe+11a] an ein Client–Server-Szenario an und analysieren sie unter der Annahme, dass ein Angreifer Server auf Grundlage früherer Systeminformationen adaptiv blockieren kann. Wir erweitern die Medianregel schrittweise, um stabilisierende Zustandsmaschinen-Replikation, kompakte Commitments, zertifizierte Commitments und Wiederherstellung zu unterstützen. Festgeschriebene Befehle können von den Servern ausgeführt und anschließend verworfen werden, während kompakte hashbasierte Zertifikate es Clients ermöglichen, nachzuweisen, dass ihre Befehle Bestandteil des festgeschriebenen Verlaufs sind. Das Protokoll benötigt keine digitalen Signaturen und erlaubt es den Servern, lediglich den gemeinsamen Zustand, noch nicht festgeschriebene Befehle und eine geringe Menge zusätzlicher Metadaten zu speichern. Es garantiert Liveness, solange höchstens ein konstanter Anteil der Server blockiert ist, gewährleistet Sicherheit unabhängig von der Anzahl der blockierten Server und ermöglicht eine schnelle Wiederherstellung, selbst nachdem alle Server blockiert worden sind. Darüber hinaus ist das Protokoll vollständig dezentralisiert und bleibt daher auch gegenüber Angreifern robust, die gezielt zentrale Server angreifen. Dies unterscheidet es von Leader-basierten Ansätzen. Das cloudbasierte Modell begegnet den Skalierbarkeitsbeschränkungen, die entstehen, wenn die gesamte Arbeitslast eines logischen Teilnehmers einem einzelnen Server zugewiesen wird. In diesem Modell wird jeder logische Teilnehmer durch eine Cloud kooperierender physischer Server repräsentiert. Dadurch können Speicherbedarf, Kommunikation und Berechnungen verteilt werden, während die Last jedes physischen Servers beschränkt bleibt. Wir führen die erweiterte (k, l)-Median- Cloud-Regel ein, um die serverbasierte erweiterte Medianregel zu simulieren. Die Konstruktion kombiniert ein verteiltes Protokoll zur Auswahl des Median-Logs, das Arrow-Protokoll zur Anordnung fehlender Befehle und das Order-Protokoll zur Zuweisung von Log-Positionen mit dem Hashbaum-Protokoll, um kompakte kryptografische Commitments zu erhalten. Wir beweisen die Sicherheit und Liveness dieser Komponenten und zeigen, dass eine Runde der serverbasierten erweiterten Medianregel in O(log m + log a) Runden simuliert werden kann, wobei m die Anzahl der physischen Server in einer Cloud und a die Anzahl der Befehle bezeichnet. Unter der Annahme, dass m und a polynomiell in n sind, wird die Simulation mit hoher Wahrscheinlichkeit innerhalb von O(log n) Runden abgeschlossen.
Abstract
This thesis presents a lightweight and decentralized approach to state machine replication with compact commitment certificates under adaptive blocking adversaries. The work consists of two complementary parts: a server-based model, which establishes the theoretical foundations of the approach, and a cloud-based model, which extends these foundations to a scalable distributed architecture. In the server-based model, we adapt and analyze the median rule for stabilizing consensus [Doe+11a] in a client–server setting where an adversary may adaptively block servers based on past system information. We extend the median rule step by step to support stabilizing state machine replication, compact commitment, certified commitment, and recovery. Committed commands can be executed and discarded by servers, while compact hash-based certificates allow clients to prove that their commands belong to the committed history. The protocol requires no digital signatures and allows servers to retain only the shared state, uncommitted commands, and a small amount of auxiliary metadata. It guarantees liveness when at most a constant fraction of servers is blocked, preserves safety regardless of the number of blocked servers, and supports fast recovery even after all servers have been blocked. Moreover, the protocol is fully decentralized and therefore remains robust against adversaries that selectively target key servers, unlike leader-based approaches. The cloud-based model addresses the scalability limitations of assigning the entire workload of a logical participant to a single server. In this model, each logical participant is represented by a cloud of cooperating physical servers, allowing storage, communication, and computation to be distributed while keeping the load on each physical server bounded. We introduce the extended (k,l)-median cloud rule to simulate the server-based extended median rule. The construction combines a distributed protocol for selecting the median log, the arrow protocol for ordering missing commands, and the order protocol for assigning log positions with the hash tree protocol for maintaining compact cryptographic commitments. We prove the safety and liveness of these components and show that one round of the server-based extended median rule can be simulated in O(log m + log a) rounds, where m is the number of physical servers in a cloud and a is the number of the commands. Under the assumptions m and a are polynomial in n, the simulation completes in O(log n) rounds with high probability.
Inhalt
Statistik
- Das PDF-Dokument wurde 18 mal heruntergeladen.
Lizenz-/Rechtehinweis

