Self-Stabilization of Wait-Free Shared Memory Objects

J.H. Hoepman, Marina Papatriantafilou, Philippas Tsigas

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)

Abstract

This paper proposes a general definition of self-stabilizing wait-free shared memory objects. The definition ensures that, even in the face of processor failures, every execution after a transient memory failure is linearizable except for an a priori bounded number of actions. Shared registers have been used extensively as communication medium in self-stabilizing protocols. As an application of our theory, we therefore focus on self-stabilizing implementation of such registers, thus providing a large body of previous research with a more solid foundation. In particular, we prove that one cannot construct a self-stabilizing single-reader single-writer regular bit from self-stabilizing single-reader single-writer safe bits, using only a single bit for the writer. This leads us to postulate a self-stabilizing dual-reader single-writer safe bit as the minimal hardware needed to achieve self-stabilizing wait-free interprocess communication and synchronization. Based on this hardware, adaptations of well-known wait-free implementations of regular and atomic shared registers are proven to be self-stabilizing.
Original languageUndefined
Pages (from-to)766-791
JournalJournal of parallel and distributed computing
Volume62
Issue number5
DOIs
Publication statusPublished - 2002

Keywords

  • IR-74779
  • wait-free constructions
  • Distributed Computing
  • METIS-211555
  • Shared memory
  • Fault Tolerance
  • self-stabilization

Cite this

Hoepman, J.H. ; Papatriantafilou, Marina ; Tsigas, Philippas. / Self-Stabilization of Wait-Free Shared Memory Objects. In: Journal of parallel and distributed computing. 2002 ; Vol. 62, No. 5. pp. 766-791.
@article{2f127834fab042dfa8907690f5622294,
title = "Self-Stabilization of Wait-Free Shared Memory Objects",
abstract = "This paper proposes a general definition of self-stabilizing wait-free shared memory objects. The definition ensures that, even in the face of processor failures, every execution after a transient memory failure is linearizable except for an a priori bounded number of actions. Shared registers have been used extensively as communication medium in self-stabilizing protocols. As an application of our theory, we therefore focus on self-stabilizing implementation of such registers, thus providing a large body of previous research with a more solid foundation. In particular, we prove that one cannot construct a self-stabilizing single-reader single-writer regular bit from self-stabilizing single-reader single-writer safe bits, using only a single bit for the writer. This leads us to postulate a self-stabilizing dual-reader single-writer safe bit as the minimal hardware needed to achieve self-stabilizing wait-free interprocess communication and synchronization. Based on this hardware, adaptations of well-known wait-free implementations of regular and atomic shared registers are proven to be self-stabilizing.",
keywords = "IR-74779, wait-free constructions, Distributed Computing, METIS-211555, Shared memory, Fault Tolerance, self-stabilization",
author = "J.H. Hoepman and Marina Papatriantafilou and Philippas Tsigas",
year = "2002",
doi = "10.1006/jpdc.2001.1829",
language = "Undefined",
volume = "62",
pages = "766--791",
journal = "Journal of parallel and distributed computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",
number = "5",

}

Self-Stabilization of Wait-Free Shared Memory Objects. / Hoepman, J.H.; Papatriantafilou, Marina; Tsigas, Philippas.

In: Journal of parallel and distributed computing, Vol. 62, No. 5, 2002, p. 766-791.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Self-Stabilization of Wait-Free Shared Memory Objects

AU - Hoepman, J.H.

AU - Papatriantafilou, Marina

AU - Tsigas, Philippas

PY - 2002

Y1 - 2002

N2 - This paper proposes a general definition of self-stabilizing wait-free shared memory objects. The definition ensures that, even in the face of processor failures, every execution after a transient memory failure is linearizable except for an a priori bounded number of actions. Shared registers have been used extensively as communication medium in self-stabilizing protocols. As an application of our theory, we therefore focus on self-stabilizing implementation of such registers, thus providing a large body of previous research with a more solid foundation. In particular, we prove that one cannot construct a self-stabilizing single-reader single-writer regular bit from self-stabilizing single-reader single-writer safe bits, using only a single bit for the writer. This leads us to postulate a self-stabilizing dual-reader single-writer safe bit as the minimal hardware needed to achieve self-stabilizing wait-free interprocess communication and synchronization. Based on this hardware, adaptations of well-known wait-free implementations of regular and atomic shared registers are proven to be self-stabilizing.

AB - This paper proposes a general definition of self-stabilizing wait-free shared memory objects. The definition ensures that, even in the face of processor failures, every execution after a transient memory failure is linearizable except for an a priori bounded number of actions. Shared registers have been used extensively as communication medium in self-stabilizing protocols. As an application of our theory, we therefore focus on self-stabilizing implementation of such registers, thus providing a large body of previous research with a more solid foundation. In particular, we prove that one cannot construct a self-stabilizing single-reader single-writer regular bit from self-stabilizing single-reader single-writer safe bits, using only a single bit for the writer. This leads us to postulate a self-stabilizing dual-reader single-writer safe bit as the minimal hardware needed to achieve self-stabilizing wait-free interprocess communication and synchronization. Based on this hardware, adaptations of well-known wait-free implementations of regular and atomic shared registers are proven to be self-stabilizing.

KW - IR-74779

KW - wait-free constructions

KW - Distributed Computing

KW - METIS-211555

KW - Shared memory

KW - Fault Tolerance

KW - self-stabilization

U2 - 10.1006/jpdc.2001.1829

DO - 10.1006/jpdc.2001.1829

M3 - Article

VL - 62

SP - 766

EP - 791

JO - Journal of parallel and distributed computing

JF - Journal of parallel and distributed computing

SN - 0743-7315

IS - 5

ER -