Many current online services have stringent availability and performance requirements. State machine replication is a well-established approach to configurable availability but only provides limited performance scalability. This happens because every replica must execute all requests, and thus, increasing the number of replicas results in bounded improvements in performance.
Scalable performance of stateful services is typically achieved with state partitioning (also known as sharding). The idea is to divide the state of a service in multiple partitions so that most commands access one partition only and are equally distributed among partitions.
In this project, we investigate state partitioning in the context of state machine replication. Since most services cannot be perfectly partitioned, that is, the service state cannot be divided in a way that commands access one partition only, Scalable State Machine Replication (S-SMR) must cope with multi-partition commands, which raises new and interesting correctness and performance issues.