Detail

Executing requests concurrently in state machine replication

The ubiquity of computer systems, and the scale at which they operate, mean that failures are common and inevitable.
State machine replication (SMR) is the standard way to build fault-tolerant systems: the system maintains multiple replicas that both store a copy of the system’s data and execute operations on that data. The SMR protocol is as follows: replicas first agree on an order to execute the incoming operations, and then execute the operations sequentially in the agreed upon order, so that every replica reaches the same final state.
However, replicas are made up of multi-core processors, but taking advantage of the available processor cores to execute operations simultaneously is at odds with the SMR protocol. So we have a dilemma. On one hand, we want to take advantage of the available processor cores to execute operations simultaneously. But on the other hand, replicas must abide by the operation order that they agreed upon for the system to remain consistent.
This talk describes proposes a solution to the dilemma of exploiting multi-core processors in SMR. At a high level, we propose to use speculative execution techniques to execute operations simultaneously while nonetheless ensuring that their execution is equivalent to having executed the operations sequentially in the order the replicas agreed upon. To achieve this, we: (1) propose to execute operations as serializable transactions, and (2) develop a new concurrency control protocol that ensures that the concurrent execution of a set of transactions respects the order replicas agreed upon. Furthermore, since speculation is only effective if it is successful, we also (3) propose a modification to the typical API to declare transactions (e.g. begin, read, write, and commit). The proposed API allows transactions to execute their logic over an abstract replica state, which results in fewer conflicts between transactions and consequently in more successful speculative executions.