Extending State Machine Replication through Composition

• Caroline Martins Alves UFSC
• Thais Bardini Idalino UFSC
• Odorico Mendizabal UFSC

Resumo

State Machine Replication (SMR) is a well-known approach for implementing highly available, fault-tolerant services. In the traditional SMR model, all replicas execute the same requests deterministically and in the same order, ensuring strong consistency. Over the decades, SMR has gained popularity, leading to extensive research that has enhanced its resilience, performance, and scalability. However, one aspect not yet addressed in SMR is service composition. This paper takes the first steps in this direction, presenting a formal definition of state machine replication and compositionality. By combining SMRs through composition, we enable the reuse of existing services to build more complex and reliable systems. This modular approach provides loosely coupled and flexible solutions, advancing the theoretical background of SMR and aligning with large-scale application development based on cloud computing and microservices. We demonstrate that using composition in SMR allows adding new features to existing SMR specifications and extends the service operation’s semantics by enabling different state machine replicas to perform complementary steps for the same operation. Sharding and state partitioning are also facilitated by SMR composition, as disjoint state variables can be assigned to separate SMRs. Finally, we illustrate the potential benefits of composing SMRs through running examples and discuss some open challenges.

Palavras-chave: Distributed computing, fault tolerance, state machine replication, composition