Kumar, Priyanka and Peri, Sathya
(2013)
Multiversion Conflict Notion for Transactional Memory Systems*.
In: 5th Workshop on the Theory of Transactional Memory, October 14, 2013, Jerusalem, Israel.
(Submitted)
Abstract
In recent years, Software Transactional Memory systems (STMs) have garnered significant interest
as an elegant alternative for addressing concurrency issues in memory. STM systems take optimistic
approach. Multiple transactions are allowed to execute concurrently. On completion, each
transaction is validated and if any inconsistency is observed it is aborted. Otherwise it is allowed to
commit.
In databases a class of histories called as conflict-serializability (CSR) based on the notion of
conflicts have been identified, whose membership can be efficiently verified. As a result, CSR is the
commonly used correctness criterion in databases In fact all known single-version schedulers known
for databases are a subset of CSR. Similarly, using the notion of conflicts, a correctness criterion,
conflict-opacity (co-opacity) which is a sub-class of can be designed whose membership can be
verified in polynomial time. Using the verification mechanism, an efficient STM implementation
can be designed that is permissive w.r.t co-opacity. Further, many STM implementations have been
developed that using the notion of conflicts.
By storing multiple versions for each transaction object, multi-version STMs provide more concurrency
than single-version STMs. But the main drawback of co-opacity is that it does not admit
histories that are uses multiple versions. This has motivated us to develop a new conflict notions for
multi-version STMs. In this paper, we present a new conflict notion multi-version conflict. Using
this conflict notion, we identify a new subclass of opacity, mvc-opacity that admits multi-versioned
histories and whose membership can be verified in polynomial time. We show that co-opacity is a
proper subset of this class.
An important requirement that arises while building a multi-version STM system is to decide
“on the spot” or schedule online among the various versions available, which version should a transaction
read from? Unfortunately this notion of online scheduling can sometimes lead to unnecessary
aborts of transactions if not done carefully. To capture the notion of online scheduling which avoid
unnecessary aborts in STMs, we have identified a new concept ols-permissiveness and is defined
w.r.t a correctness-criterion, similar to permissiveness. We show that it is impossible for a STM system
that is permissive w.r.t opacity to such avoid un-necessary aborts i.e. satisfy ols-permissiveness
w.r.t opacity. We show this result is true for mvc-opacity as well.
Actions (login required)
 |
View Item |
Altmetric
Altmetric