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 :
[Research Report] 2012
Liste complète des métadonnées

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

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


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00697198, version 2



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〉



Consultations de la notice


Téléchargements de fichiers