Skip to Main content Skip to Navigation
Reports

Read invisibility, virtual world consistency and permissiveness are compatible

Tyler Crain 1 Damien Imbs 1 Michel Raynal 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
Abstract : The aim of a Software Transactional Memory (STM) is to discharge the programmers from the management of synchronization in multiprocess programs that access concurrent objects. To that end, a STM system provides the programmer with the concept of a transaction. The job of the programmer is to design each process the application is made up of as a sequence of transactions. A transaction is a piece of code that accesses concurrent objects, but contains no explicit synchronization statement. It is the job of the underlying STM system to provide the illusion that each transaction appears as being executed atomically. Of course, for efficiency, a STM system has to allow transactions to execute concurrently. Consequently, due to the underlying STM concurrency management, a transaction commits or aborts. This paper studies the relation between two STM properties (read invisibility and permissiveness) and two consistency conditions for STM systems, namely, opacity and virtual world consistency. Both conditions ensures that any transaction (be it a committed or an aborted transaction) reads values from a consistent global state, a noteworthy property if one wants to prevents abnormal behavior from concurrent transactions that behave correctly when executed alone. A read operation issued by a transaction is invisible if it does not entail shared memory modifications. This is an important property that favors efficiency and privacy. An STM system is permissive with respect to a consistency condition if it accepts every history that satisfies the condition. This is a crucial property as a permissive STM system never aborts a transaction “for free”. The paper first shows that read invisibility, permissiveness and opacity are incompatible, which means that there is no permissive STM system that implements opacity while ensuring read invisibility. It then shows that invisibility, permissiveness and opacity are compatible. To that end the paper describes a new STM protocol called IR VWC P. This protocol presents additional noteworthy features: it uses only base read/write objects and locks which are used only at commit time; it satisfies the disjoint access parallelism property; and, in favorable circumstances, the cost of a read operation is O(1).
Document type :
Reports
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00533620
Contributor : Ist Rennes <>
Submitted on : Monday, November 8, 2010 - 8:54:00 AM
Last modification on : Tuesday, June 15, 2021 - 4:13:17 PM
Long-term archiving on: : Wednesday, February 9, 2011 - 2:21:15 AM

File

PI-1958.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00533620, version 1

Citation

Tyler Crain, Damien Imbs, Michel Raynal. Read invisibility, virtual world consistency and permissiveness are compatible. [Research Report] PI-1958, 2010, pp.21. ⟨inria-00533620⟩

Share

Metrics

Record views

446

Files downloads

276