URL: http://dl.acm.org/citation.cfm?id=2387903

State machine replication (SMR) is a powerful fault tolerance technique, it enforces replicas to deterministically process the same sequence of requests so that they produce the same sequence of outputs.

But this technique doesn't suit for parallel systems, because if different servers interleave requests’ instructions in different ways, the states and outputs of correct servers may diverge even if no faults occur. As a result, most SMR systems require servers to process requests sequentially.

In contrast, Eve partitions requests in batches and allows different replicas to execute requests within each batch in parallel. After each batch, it speculates that whether the results of these parallel executions (i.e. the system’s important state and output at each replica) will match across enough replicas. If such a correct state/output can be identified, Eve makes those incorrect replicas issue an incremental state transfer request to other replicas (by leveraging a Merkle tree). However, if too many replicas diverge so that the correct state/output cannot be identified, Eve guarantees safety and liveness by rolling back and sequentially and deterministically re-executing the requests.

Since diverges will seriously impair Eve's performance, it uses a mixer stage to apply application-specific criteria to produce groups of requests that are unlikely to interfere.

As a side effect, Eve is especially useful in tolerating concurrency bugs. First, Eve’s mixer reduces the likelihood of triggering latent concurrency bugs by attempting to run only unlikely-to-interfere requests in parallel; Second, Eve's execute-verify architecture allows Eve to detect and recover when concurrency causes executions to diverge.

In their experiments, Eve achieves a 2.6x ~ 6.5x speedup over traditional sequential execution replica and at most 4.7x speedup over the Remus primary-backup system. It also finds new concurrency bugs in H2 database.