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
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
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).
Type de document :
Rapport
[Research Report] PI-1958, 2010, pp.21
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00533620
Contributeur : Ist Rennes <>
Soumis le : lundi 8 novembre 2010 - 08:54:00
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : mercredi 9 février 2011 - 02:21:15

Fichier

PI-1958.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

386

Téléchargements de fichiers

204