Universal Constructions that Ensure Disjoint-Access Parallelism and Wait-Freedom

Abstract : Disjoint-access parallelism and wait-freedom are two desirable properties for implementations of concurrent objects. Disjoint-access parallelism guarantees that processes operating on different parts of an implemented object do not interfere with each other by accessing common base objects. Thus, disjoint-access parallel algorithms allow for increased parallelism. Wait-freedom guarantees progress for each non-faulty process, even when other processes run at arbitrary speeds or crash. A universal construction provides a general mechanism for obtaining a concurrent implementation of any object from its sequential code. We identify a natural property of universal constructions and prove that there is no universal construction (with this property) that ensures both disjoint- access parallelism and wait-freedom. This impossibility result also holds for transactional memory implementations that require a process to re-execute its transaction if it has been aborted and guarantee each transaction is aborted only a finite number of times. Our proof is obtained by considering a dynamic object that can grow arbitrarily large during an execution. In contrast, we present a universal construction which produces concurrent implementations that are both wait-free and disjoint-access parallel, when applied to objects that have a bound on the number of data items accessed by each operation they support.
Type de document :
Rapport
[Research Report] 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00697198
Contributeur : Corentin Travers <>
Soumis le : mardi 15 mai 2012 - 16:59:04
Dernière modification le : mercredi 30 mai 2018 - 10:26:02
Document(s) archivé(s) le : jeudi 15 décembre 2016 - 07:45:57

Fichier

dap-main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00697198, version 2

Collections

Citation

Faith Ellen, Panagiota Fatourou, Eleftherios Kosmas, Alessia Milani, Corentin Travers. Universal Constructions that Ensure Disjoint-Access Parallelism and Wait-Freedom. [Research Report] 2012. 〈hal-00697198v2〉

Partager

Métriques

Consultations de la notice

156

Téléchargements de fichiers

339