Eischer M (2024)
Publication Type: Thesis
Publication year: 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 tasks.
APA:
Eischer, M. (2024). Geo-Replicated Byzantine Fault-Tolerant State-Machine Replication with Low Latency (Dissertation).
MLA:
Eischer, Michael. Geo-Replicated Byzantine Fault-Tolerant State-Machine Replication with Low Latency. Dissertation, 2024.
BibTeX: Download