Composing State Machine Replication - Alves, Caroline Martins; de Souza, Matheus Antonio; Idalino, Thais Bardini; Mendizabal, Odorico Machado (Journal of Internet Services and Applications, 2025)
High availability is a fundamental requirement in large-scale distributed systems, where replication strategies are central in keeping applications operational despite a bounded number of failures. State Machine Replication (SMR) is one of the most widely adopted approaches for implementing highly available, fault-tolerant services, as it increases uptime while ensuring strong consistency. In recent years, research on SMR has yielded numerous variations tailored to enhance resilience, performance, and scalability. In this paper, we revisit SMR from a new perspective by introducing Composing State Machine Replication (CSMR), a method that enables fault-tolerant service composition. By composing SMRs, we promote the reuse of existing services to construct more complex and reliable systems. This modular approach fosters loosely coupled, flexible architectures, contributing to the theoretical foundations of SMR and aligning with common development practices in cloud computing and microservices. We formally define CSMR and demonstrate how composition can be used to extend existing SMR specifications with new features. For example, CSMR allows the semantics of a service operation to be extended by enabling different state machine replicas to execute complementary steps of the same operation. Additionally, SMR composition facilitates sharding and state partitioning by assigning disjoint state variables to separate SMRs. Beyond formalization, the paper provides illustrative examples of CSMR and introduces a high-level CSMR architecture that highlights the essential components, their responsibilities, and their interactions in supporting the composition process. To further demonstrate practicability, we present an API for building CSMR systems that combines RPC-based communication with declarative configuration in YAML format.