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.


Dynamic Scalable State Machine Replication
L. L. Hoang, C. E. Bezerra and F. Pedone
46th IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2016)

Strong Consistency at Scale
C. E. Bezerra, L. L. Hoang and F. Pedone
Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, March 2016

Providing Scalability and Low Latency in State Machine Replication
C. E. Bezerra, F. Pedone, R. van Renesse, C. Geyer
USI Technical report, December 2015

Scalable State-Machine Replication
E. Bezerra, P. J. Marandi and F. Pedone
8th Workshop on Large-Scale Distributed Systems and Middleware (LADIS 2014)

Scalable State-Machine Replication
C. E. Bezerra, F. Pedone and R. van Renesse
44th International Conference on Dependable Systems and Networks (DSN 2014)

Project members

Paulo Rodolfo Coelho
Enrique Fynn
Long Le Hoang
Fernando Pedone

Funded by the Swiss National Science Foundation and Microsoft Research.