On speculative replication of transactional systems

•Main innovative idea: exploitation of speculative processing to overlap replica coordination and local computation phases in actively replicated transactional systems.•Speculation is based on the exploration of multiple transaction serialization orders associated with alternative final (definitive) message delivery orders.•Speculation takes into account actual conflict relations among transactions, which allows exploring non-redundant (already explored) serialization orders.•Definition of a formal framework specifying speculative replication of transactional systems in terms of correctness and optimality properties.•Assessment of the relevance of the proposed framework via a simulation study in the context of Software Transactional memory systems.

In this paper we investigate, from a theoretical perspective, the problem of how to build speculative replication protocols for transactional systems layered on top of an Optimistic Atomic Broadcast (OAB) service. The OAB service provides an early, possibly erroneous, guess on transactionʼs final serialization order. This can be exploited to speculatively execute transactions in parallel with the algorithm used to determine their final total delivery (and serialization) order. To maximize the chances of guessing their final serialization order, transactions are executed multiple times, speculating on the possible orderings eventually determined by the OAB service. We formalize the Speculative Transactional Replication (STR) problem by means of a set of properties ensuring that transactions are never activated on inconsistent snapshots, as well as the minimality and completeness of the set of speculatively explored serialization orders. Finally, we present a protocol solving the STR problem, along with simulation results assessing its effectiveness.