Exploiting Concurrency in Sharded Parallel State Machine Replication

State machine replication (SMR) is a well-known approach to implementing fault-tolerant services, providing high availability and strong consistency. In classic SMR, commands are executed sequentially, in the same order by all replicas. To improve performance, two classes of protocols have been proposed to parallelize the execution of commands. Early scheduling protocols reduce scheduling overhead but introduce costly synchronization of worker threads; late scheduling protocols, instead, reduce the cost of thread synchronization but suffer from scheduling overhead. Depending on the characteristics of the workload, one class can outperform the other. We introduce a hybrid scheduling technique that builds on the existing protocols. An experimental evaluation has revealed that the hybrid approach not only inherits the advantages of each technique but also scales better than either one of them, improving the system performance by up to 3x in a workload with conflicting commands.

Automated summary

State machine replication (SMR) is a fault-tolerant approach to provide high availability and strong consistency in services. To improve performance, two classes of protocols have been proposed, with each having its own advantages and disadvantages depending on the workload characteristics. To reconcile the advantages, a hybrid scheduling technique has been introduced, which demonstrated improved system performance by up to 3x compared to individual protocols in a workload with conflicting commands.