Multiversion Conflict Notion for Transactional Memory Systems*

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)

[img]
Preview
Text
1509.04048.pdf - Submitted Version

Download (348kB) | Preview

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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Peri, SathyaUNSPECIFIED
Item Type: Conference or Workshop Item (Paper)
Additional Information: *A preliminary version of this work was presented at WTTM 2013 and published in --- Multi-version conflict notion. CoRR, abs/1307.8256, 2013
Uncontrolled Keywords: Distributed, Parallel, Cluster Computing
Subjects: Computer science > Special computer methods
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 22 Sep 2015 10:22
Last Modified: 11 Sep 2017 05:12
URI: http://raiith.iith.ac.in/id/eprint/1950
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 1950 Statistics for this ePrint Item