Universal Constructions that Ensure Disjoint-Access Parallelism and Wait-Freedom - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 2012

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.
Fichier principal
Vignette du fichier
dap-main.pdf (585.55 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00697198 , version 1 (14-05-2012)
hal-00697198 , version 2 (15-05-2012)

Identifiers

  • HAL Id : hal-00697198 , version 2

Cite

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⟩

Collections

CNRS LARA ANR
90 View
542 Download

Share

Gmail Facebook X LinkedIn More