Deterministic Fuzzy Checkpoints - Eischer, Michael; Büttner, Markus; Distler, Tobias (Proceedings of the 38th International Symposium on Reliable Distributed Systems (SRDS '19), 2019)
Replicated systems tolerating arbitrary (Byzantine) faults require periodic and deterministic application-state checkpoints to perform essential tasks such as initializing new replicas, enabling faulty replicas to recover, and garbage-collecting old agreement-protocol messages. Existing techniques to create checkpoints in these systems make it necessary to temporarily suspend request execution in order to capture a consistent checkpoint, causing significant service disruptions for applications with large states. Unfortunately, state-of-the-art approaches from the domain of crash-tolerant systems also are not directly applicable, because the checkpoints they produce are not comparable across replicas and therefore cannot be validated in an environment in which replicas may fail arbitrarily and do not trust each other. In this paper, we address these problems by proposing deterministic fuzzy checkpoints (DFC), a novel technique that enables all correct replicas in a system to create consistent and matching checkpoints in parallel to processing requests. As a consequence, DFC increases service availability while still allowing replicas to verify the correctness of a checkpoint before applying it to their local states. In addition to our general approach, we present different alternatives to implement DFC within a replication library and furthermore discuss support for the creation of differential checkpoints. Experiments with a key-value store show that DFC is able to snapshot states of 3 GB while sustaining high performance throughout the entire checkpointing process.
UnivIS-Import:2019-08-15:Pub.2019.tech.IMMD.IMMD4.determ
Keywords: Checkpointing; State Machine Replication; Fault Tolerance

Egalitarian Byzantine Fault Tolerance - Eischer, Michael; Distler, Tobias (2021 IEEE 26th Pacific Rim International Symposium on Dependable Computing (PRDC), 2021)
Minimizing end-to-end latency in geo-replicated systems usually makes it necessary to compromise on resilience, resource efficiency, or throughput performance, because existing approaches either tolerate only crashes, require additional replicas, or rely on a global leader for consensus. In this paper, we eliminate the need for such tradeoffs by presenting ISOS, a leaderless replication protocol that tolerates up to f Byzantine faults with a minimum of 3 f + 1 replicas. To reduce latency in wide-area environments, ISOS relies on an efficient consensus algorithm that allows all participating replicas to propose new requests and thereby enables clients to avoid delays by submitting requests to their nearest replica. In addition, ISOS minimizes overhead by limiting message ordering to requests that conflict with each other (e.g., due to accessing the same state parts) and by already committing them after three communication steps if at least f + 1 replicas report each conflict. Our experimental evaluation with a geo-replicated key-value store shows that these properties allow ISOS to provide lower end-to-end latency than existing protocols, especially for use-case scenarios in which the clients of a system are distributed across multiple location

Geo-Replicated Byzantine Fault-Tolerant State-Machine Replication with Low Latency - Eischer, Michael (Friedrich-Alexander-Universität Erlangen-Nürnberg, 2024)
Protocols tolerating Byzantine faults allow a service to maintain correctness even if some of its parts misbehave. However, they significantly increase the overhead for processing client requests. Especially for geo-replicated systems, response times can grow to several hundred milliseconds. As the communication latency between remote locations is limited by the speed of light, minimizing these delays requires optimized protocols. This thesis investigates different approaches to reduce the response times of strongly consistent Byzantine fault-tolerant state-machine replication protocols that only require a low number of replicas in a geo-replicated setting. It first reviews the steps necessary to process client requests with strong consistency and derives approaches to minimize the delay introduced by the client communication, the agreement and the execution. To minimize the latency for submitting a client request to the system, each replica is enabled to immediately initiate the ordering for a request, thus allowing a client to communicate with the nearest replica. The proposed Byzantine fault-tolerant egalitarian protocol, which only uses the minimum number of 3f+1 replicas to tolerate f faults, accordingly removes the need for a central leader replica by instead agreeing on conflicts between requests. The agreement can complete on a fast path if the involved replicas propose matching conflicts. Before execution, requests are sorted according to their conflicts to ensure a consistent order across replicas. To minimize the latency of the agreement protocol, this thesis introduces an approach based on the architecture of modern clouds. The replicas are split into a central agreement group, which determines the execution order for all client requests, with at least 3f+1 replicas and multiple execution groups with only 2f+1 replicas. Each group of replicas is located in one region, with its replicas distributed across multiple availability zones to minimize the risk of correlated failures. Thus, replicas in a group can communicate with each other with low latency, thereby allowing the agreement to work with low latency. The groups use an abstraction called inter-regional message channel, which allows them to exchange client requests and the agreement results reliably. To minimize the execution latency, this thesis reduces response-time spikes caused by the periodic creation of checkpoints during which the request execution must be paused. Instead, it introduces a concurrent state-capture phase, which starts before reaching the point at which to create the checkpoint. The resulting fuzzy snapshot together with a list of state modifications made by requests executed in the meantime, can be combined into a regular checkpoint that is identical on all replicas. The application interface offers two variants providing different trade-offs regarding simplicity and efficiency. These approaches successfully reduce the client-perceived response times while also reducing the performance variation caused by different configurations and periodic task

Latency-Aware Leader Selection for Geo-Replicated Byzantine Fault-Tolerant Systems - Eischer, Michael; Distler, Tobias (Proceedings of the 48th International Conference on Dependable Systems and Networks Workshops (DSN-W '18), 2018)
In a geo-replicated setting, the response time of a leader-based Byzantine fault-tolerant (BFT) protocol often differs significantly depending on which of the replicas in the system is currently acting as leader. Identifying a single optimal leader position in general is impossible due to workload characteristics usually varying over the course of the day. As a consequence, the approach used in many existing BFT replication protocols, which assign the leader role in a static manner and only change the leader in case of suspected or detect faulty behavior, results in unnecessarily high latency in wide-area environments. In this paper we address this problem with Archer, a latency-aware mechanism to select the leader of a geo-replicated BFT system based on end-to-end response times measured by clients. To prevent faulty replicas from gaining an unfair advantage by sending protocol messages early, Archer relies on a hash-chain-based approach that enables clients to detect if a protocol phase has been skipped. In addition, Archer offers means to tolerate incorrect latency values reported by faulty clients and can also be extended to solve other selection problems such as the placement of active and passive replicas in resource-efficient BFT systems.
UnivIS-Import:2018-09-06:Pub.2018.tech.IMMD.IMMD4.latenc
Keywords: REFIT

Low-Latency Geo-Replicated State Machines with Guaranteed Writes - Eischer, Michael; Straßner, Benedikt; Distler, Tobias (Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data, PaPoC 2020, 2020)
When deployed in geo-distributed environments, existing state-machine replication protocols require at least one wide-area communication step for establishing a total order on client requests. For use cases in which clients are not interested in the actual result of a request, but just need a guarantee that the request will be processed eventually, this property usually incurs unnecessarily high response times. To address this problem we present Weave, a cloud-based geo-replication protocol that relies on replica groups in multiple geographic regions to efficiently assign stable sequence numbers to incoming requests. This approach enables Weave to offer guaranteed writes which in the absence of faults only wait for communication within a client’s local replica group to produce an execution guarantee for a particular sequence number. Our experiments with a distributed queue and a replicated log show that guaranteed writes can significantly improve response times of geo-replicated applications.
CRIS-Team Scopus Importer:2021-04-19
Keywords: Cloud; Consistency; Geo-replication; State-machine replication; Wide-area networks

Micro Replication - Distler, Tobias; Eischer, Michael; Lawniczak, Laura (Proceedings of the 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN '23), 2023)
State-machine replication protocols represent the foundation of many fault-tolerant services. Unfortunately, their inherent complexity makes existing implementations notoriously difficult to debug and test. To address this problem, we propose a novel design approach, micro replication, whose main goal is to reduce bugs and enable replication protocols with improved debuggability properties. At its core, our concept consists of a set of principles that, if followed during protocol design, later significantly facilitate crucial tasks such as bug-source isolation, state-information retrieval, as well as root-cause identification. To achieve this, micro replication organizes a protocol as a composition of specialized modules ('micro replicas') that each encapsulate a particular protocol phase or mechanism, and therefore are easier to test and monitor than traditional monolithic replicas. Besides discussing the underlying ideas of our approach, to show its feasibility we also present and evaluate Mirador, the first micro-replicated Byzantine fault-tolerant protocol.
CRIS-Team Scopus Importer:2023-09-08
Keywords: Debuggability; Fault Tolerance; Replication

Resilient Cloud-based Replication with Low Latency - Eischer, Michael; Distler, Tobias (Middleware 2020 - Proceedings of the 2020 21st International Middleware Conference, 2020)
Existing approaches to tolerate Byzantine faults in geo-replicated environments require systems to execute complex agreement protocols over wide-area links and consequently are often associated with high response times. In this paper we address this problem with Spider, a resilient replication architecture for geo-distributed systems that leverages the availability characteristics of today's public-cloud infrastructures to minimize complexity and reduce latency. Spider models a system as a collection of loosely coupled replica groups whose members are hosted in different cloud-provided fault domains (i.e., availability zones) of the same geographic region. This structural organization makes it possible to achieve low response times by placing replica groups in close proximity to clients while still enabling the replicas of a group to interact over short-distance links. To handle the inter-group communication necessary for strong consistency Spider uses a reliable group-to-group message channel with first-in-first-out semantics and built-in flow control that significantly simplifies system design.
CRIS-Team Scopus Importer:2021-04-19
Keywords: Byzantine fault tolerance; Geo-replication

Scalable Byzantine Fault Tolerance on Heterogeneous Servers - Eischer, Michael; Distler, Tobias (Proceedings of the 13th European Dependable Computing Conference (EDCC '17), 2017)
When provided with more powerful or extra hardware, state-of-the-art Byzantine fault-tolerant (BFT) agreement protocols are unable to effectively exploit the additional computing resources: On the one hand, in settings with heterogeneous servers existing protocols cannot fully utilize servers with higher performance capabilities. On the other hand, using more servers than the minimum number of replicas required for Byzantine fault tolerance in general does not lead to improved throughput and latency, but instead actually degrades performance.In this paper, we address these problems with Omada, a BFT protocol that is able to benefit from additional hardware resources. To achieve this property while still providing strong consistency, Omada first parallelizes agreement into multiple groups and then executes the requests handled by different groups in a deterministic order. By varying the number of requests to be ordered between groups as well as the number of groups that a replica participates in between servers, Omada offers the possibility to individually adjust the resource usage per server. Moreover, the fact that not all replicas need to take part in every group enables the protocol to exploit additional server
UnivIS-Import:2017-12-18:Pub.2017.tech.IMMD.IMMD4.scalab
Keywords: Byzantine Fault Tolerance; State-Machine Replication; Scalability; Heterogeneity; Resource Efficiency

Scalable Byzantine Fault-tolerant State-Machine Replication on Heterogeneous Servers - Eischer, Michael; Distler, Tobias (Computing, 2018)
When provided with more powerful or extra hardware, state-of-the-art Byzantine fault-tolerant (BFT) replication protocols are unable to effectively exploit the additional computing resources: on the one hand, in settings with heterogeneous servers existing protocols cannot fully utilize servers with higher performance capabilities. On the other hand, using more servers than the minimum number of replicas required for Byzantine fault tolerance in general does not lead to improved throughput and latency, but instead actually degrades performance. In this paper, we address these problems with Omada, a BFT system architecture that is able to benefit from additional hardware resources. To achieve this property while still providing strong consistency, Omada first parallelizes agreement into multiple groups and then executes the requests handled by different groups in a deterministic order. By varying the number of requests to be ordered between groups as well as the number of groups that a replica participates in between servers, Omada offers the possibility to individually adjust the resource usage per server. Moreover, the fact that not all replicas need to take part in every group enables the architecture to exploit additional server
UnivIS-Import:2018-09-05:Pub.2018.tech.IMMD.IMMD4.scalab
Keywords: Byzantine fault tolerance; State-machine replication; Scalability; Heterogeneity; Resource efficiency

Spider: A BFT Architecture for Geo-Replicated Cloud Services - Eischer, Michael; Distler, Tobias (2024)