Abstract
| Original language | Undefined |
|---|---|
| Pages (from-to) | 766-791 |
| Journal | Journal of parallel and distributed computing |
| Volume | 62 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - 2002 |
Keywords
- IR-74779
- wait-free constructions
- Distributed Computing
- METIS-211555
- Shared memory
- Fault Tolerance
- self-stabilization
Cite this
}
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 journal › Article › Academic › peer-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 -