Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Towards self-stabilizing wait-free shared memory objects

Hoepmann, J.-H. and Papatriantafilou, Marina and Tsigas, Philippas

MPI-I-95-1-005. February 1995, 15 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

Past research on fault tolerant distributed systems has focussed on either
processor failures, ranging from benign crash failures to the malicious
byzantine failure types, or on transient memory failures, which can
suddenly corrupt the state of the system.
An interesting question in the theory of distributed computing is whether one
can device highly fault tolerant protocols which can
tolerate both processor failures as well as transient errors.
To answer this question we consider the construction of
self-stabilizing wait-free shared memory objects.
These objects occur naturally in distributed systems in which both processors
and memory may be faulty.
Our contribution in this paper is threefold. First, we propose a general
definition of a self-stabilizing wait-free shared memory object that
expresses safety guarantees even in the face of processor failures.
Second, we show that within this framework one cannot construct a
self-stabilizing single-reader single-writer regular bit from
single-reader single-writer safe bits. This result leads us to postulate a
self-stabilizing {\footnotesize\it dual\/}-reader single-writer safe bit with
which, as a
third contribution, we construct self-stabilizing regular and atomic registers.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s): KBytes; 206 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Hoepmann, J.-H. and Papatriantafilou, Marina and Tsigas, Philippas},
  TITLE = {Towards self-stabilizing wait-free shared memory objects},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-95-1-005},
  MONTH = {February},
  YEAR = {1995},
  ISSN = {0946-011X},