TU Berlin

Internet Network ArchitecturesPublications by Type: Conference and Workshop Papers


zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Conference and Workshop Publications

see also conference papers, workshop papers, demos, and posters. (under construction)

Computing with Reads and Writes in the Absence of Step Contention
Zitatschlüssel AGK-CRWASC-05
Autor Attiya, Hagit and Guerraoui, Rachid and Kouznetsov, Petr
Buchtitel Proceedings of the 19th International Conference on Distributed Computing (DISC '05)
Seiten 122–136
Jahr 2005
ISBN 978-3-540-29163-3
ISSN 0302-9743
DOI http://dx.doi.org/10.1007/11561927_11
Ort Krakow, Poland
Adresse Berlin / Heidelberg, Germany
Jahrgang 3724
Verlag Springer
Serie Lecture Notes in Computer Science (LNCS)
Zusammenfassung 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 Eintrag



Schnellnavigation zur Seite über Nummerneingabe