TU Berlin

Internet Network ArchitecturesPublications by Type: Technical Reports

Page Content

to Navigation

Publications by Type: Technical Reports

Computing with Reads and Writes in the Absence of Step Contention
Citation key AGK-CRWASC-tr-05
Author Attiya, Hagit and Guerraoui, Rachid and Kouznetsov, Petr
Year 2005
Note No. LPD-CONF-2005-005 / IC-EPFL ID:2005006
Institution École Polytechnique Fédérale de Lausanne, Switzerland
Abstract This paper studies implementations of concurrent objects that exploit the absence of step contention. These implementations use only reads and writes when a process is running solo. The other processes might be busy with other objects, swapped-out, failed, or simply delayed by a contention manager. We study in this paper two classes of such implementations, according to how they handle the case of step contention. The first kind, called obstruction-free implementations, are not required to terminate in that case. The second kind, called solo-fast implementations, terminate using powerful operations (e.g., C\&S). We present a generic obstruction-free object implementation that has a linear contention-free step complexity (number of reads and writes taken by a process running solo) and uses a linear number of read/write objects. We show that these complexities are asymptotically optimal, and hence generic obstruction-free implementations are inherently slow. We also prove that obstruction-free implementations cannot be gracefully degrading, namely, be nonblocking when the contention manager operates correctly, and remain (at least) obstruction-free when the contention manager misbehaves. Finally, we show that any object has a solo-fast implementation, based on a solo-fast implementation of consensus. The implementation has linear contention-free step complexity, and we conjecture solo-fast implementations must have non-constant step complexity, i.e., they are also inherently slow.
Bibtex Type of Publication Technical Report
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe