Detail

Boosting concurrency in Parallel State Machine Replication

State machine replication (SMR) is a well-known approach to implementing fault-tolerant services, providing high availability and strong consistency. To boost the performance of SMR, some proposals execute independent commands concurrently, while dependent commands execute sequentially in the total delivery order. The most general approach to handling command dependencies resorts to a directed acyclic graph (DAG), where nodes represent commands and edges represent dependencies. In this talk, I will show that a typical coarse-grained DAG implementation, where the whole graph is a critical section, results in a bottleneck in the replica. I will then present two improvements to the coarse-grained DAG approach: a fine-grained algorithm, using lock-coupling, and a lock-free algorithm. The fine-grain algorithm locks individual vertices in the DAG. The lock-free algorithm uses nonblocking synchronization, with atomic operations, and lazy synchronization to postpone physical removal of nodes. All algorithms were integrated in a parallel SMR prototype. Experimental evaluation revealed that the fine-grained algorithm is also subject to a bottleneck. The lock-free implementation, however, sports linear speedup with the number of working threads, in some cases scaling up to 64 threads.