Technical report detail

Providing Scalability and Low Latency in State Machine Replication

by Carlos Eduardo Bezerra, Fernando Pedone, Robbert van Renesse, Claudio Geyer


State machine replication (SMR) is a well-known replication technique that ensures strong consistency (linearizability) for distributed services. Even though SMR ensures strong consistency, it provides limited throughput scalability, since every replica executes every command. We propose Scalable SMR (S-SMR), a technique that provides throughput scalability by means of partitioning the service state and partially ordering commands across partitions, along with two optimizations: caching and state prefetching. We also propose Fast-SSMR, which changes S-SMR by providing an extended interface between clients and servers. Fast-SSMR implements two state machines at each server replica: an optimistic state machine and a conservative state machine. Both state machines respond to each command, resulting in a fast optimistic reply, which is correct with a high probability, and a conservative reply, which is always correct and confirms the optimistic reply. This way, Fast-SSMR does not require the service to be able to undo operations. We have implemented both S-SMR and Fast-SSMR as a Java library, along with a collection of representative applications. Our experiments show that both S-SMR and Fast-SSMR achieve throughput scalability with the number of partitions, and that the optimistic replies are significantly faster than the conservative replies.


Technical report 2015/06, December 2015

BibTex entry

@techreport{15providing, author = {Carlos Eduardo Bezerra and Fernando Pedone and Robbert van Renesse and Claudio Geyer}, title = {Providing Scalability and Low Latency in State Machine Replication}, institution = {University of Lugano}, number = {2015/06}, year = 2015, month = dec }
Allegati