Uma Implementação Fiel do Algoritmo Generalized Paxos e uma CStruct para o Problema de Coordenação de Lease Distribuído

Abstract

State Machine Replication is a broadly accepted approach to build a fault-tolerant distributed system. In this technique, replicas agree on a sequence of commands that they will execute. This consists in the fundamental Consensus problem in distributed systems. The classical Consensus problem and its solutions do not leverage the fact that the sequence of commands executed by the replicas does not need to follow a total order. The algorithm entitled Generalized Paxos solves a more generic and versatile version of the Consensus problem by requiring that the replicas agree on a partially ordered sequence of commands. As well as being one of the most optimized solutions to implement state machine replication, Generalized Paxos is also capable of solving diferent agreement problems. However, due to its high complexity and the small amount of research attesting its beneĄts, the algorithmŠs potential is not fully explored. This work aims at diminishing the gap between theory and practice regarding Generalized Paxos, through an implementation of the algorithm and optimizations that can be applied to it. Furthermore, to advocate the use of Generalized Paxos in real-world problems, this work provides a new construct that allows the algorithm to solve a variation of the lease coordination problem in distributed systems.