  State Machine Replication (SMR) is a fundamental approach to designing
service with fault tolerance. However, its requirement for the deterministic
execution of transactions often results in single-threaded replicas, which
cannot fully exploit the multicore capabilities of today's processors.
Therefore, parallel SMR has become a hot topic of recent research. The basic
idea behind it is that independent transactions can be executed in parallel,
while dependent transactions must be executed in their relative order to ensure
consistency among replicas. The dependency detection of existing parallel SMR
methods is mainly based on pairwise transaction comparison or batch comparison.
These methods cannot simultaneously guarantee both effective detection and
concurrent execution. Moreover, the scheduling process cannot execute
concurrently, which introduces extra scheduling overhead as well. In order to
further reduce scheduling overhead and ensure the parallel execution of
transactions, we propose an efficient scheduler based on a specific index
structure. The index is composed of a Bloom Filter and the associated
transaction queues, which provides an efficient dependency detection and
preserve necessary dependency information respectively. Based on the index
structure, we further devise an elaborated concurrent scheduling process. The
experimental results show that the proposed scheduler is more efficient,
scalable and robust than the comparison methods.
