direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Petr Kuznetsov's Publications

Computing with Reads and Writes in the Absence of Step Contention
Citation key AGK-CRWASC-05
Author Attiya, Hagit and Guerraoui, Rachid and Kouznetsov, Petr
Title of Book Proceedings of the 19th International Conference on Distributed Computing (DISC '05)
Pages 122–136
Year 2005
ISBN 978-3-540-29163-3
ISSN 0302-9743
DOI http://dx.doi.org/10.1007/11561927_11
Location Krakow, Poland
Address Berlin / Heidelberg, Germany
Volume 3724
Publisher Springer
Series Lecture Notes in Computer Science (LNCS)
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.
Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions