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.
23/10/2019 14:30
Computer Systems
Fernando Pedone is a full professor at the Faculty of Informatics at the University of Lugano (USI), Switzerland, and one of the faculty’s “founding members”. He received the Ph.D. degree from EPFL in 1999 and has been previously affiliated with Cornell University, USA, as a visiting professor, and Hewlett-Packard Laboratories (HP Labs), USA, as a researcher. Fernando Pedone’s research interests include the theory and practice of dependable distributed systems and dependable data management systems. He has authored several scientific papers and patents, and he is co-editor of the book “Replication: theory and practice”. Last but not least, Prof. Pedone is a windsurfing enthusiast.
