Contribuições para escalabilidade em replicação máquina de estados

Abstract

The increasing use of online services has created the need for architectures that offer high availability and performance. In the context of high availability, the technique of State Machine Replication (SMR) is one of the most widely used solutions in diferent áreas such as cloud computing, database systems, synchronization mechanisms, and reliable communication. The concept of SMR is simple: since all replicas start with the same state and execute commands deterministically in the same order, the same changes in the state after the execution of each command are applied across all replicas of the system, ensuring strong consistency. However, this functioning model of SMR limits its performance. To increase the scalability of the SMR technique, different strategies have been proposed. One possible strategy to gain benefits from the technique is through better utilization of processor cores commonly available in modern servers. Different parallel architectures for SMR have been formulated with solutions that introduce concurrency in the ordering and execution of commands, considering that non-conflicting requests can be processed in parallel without affecting strong consistency. Generalized consensus protocols work with the same notion of conflict: non-conflicting commands do not require ordering during consensus. In the first part of this thesis, we propose the use of conflict information from generalized consensus protocols to enable parallel execution of commands in SMR. This proposal, not yet found in the literature, has been described, implemented, and evaluated, showing performance gains. Another strategy used to increase the scalability of the SMR technique is through state partitioning, allowing partitions to work independently. In addition to command ordering for each partition, multi-partition commands require ordering between the involved partitions. In this context, atomic multicast is a fundamental abstraction as it captures reliability and ordering requirements. ByzCast is the first atomic multicast protocol tolerant to Byzantine faults. To reuse ordering solutions for the Byzantine case, ByzCast uses a overlay tree for message dissemination between the involved partitions, with each partition implemented by a set of replicas operating under Byzantine consensus. In the second part of this thesis, we extend ByzCast from a Byzantine faulttolerant atomic multicast protocol to a partitioned SMR with Byzantine fault tolerance. To do so, we define and discuss different strategies for handling request and response return to SMR clients.