Search: onr:"swepub:oai:research.chalmers.se:4f61d55b-765e-4298-875f-f86cc3513258" >
Self-Stabilization ...
Self-Stabilization in Wait-Free Shared Memory Objects
-
Hoepman, Jaap-Henk (author)
-
- Papatriantafilou, Marina, 1966 (author)
- Chalmers tekniska högskola,Chalmers University of Technology
-
- Tsigas, Philippas, 1967 (author)
- Chalmers tekniska högskola,Chalmers University of Technology
-
(creator_code:org_t)
- Elsevier BV, 2002
- 2002
- English.
-
In: Journal of Parallel and Distributed Computing. - : Elsevier BV. - 1096-0848 .- 0743-7315. ; 62:5, s. 818-842
- Related links:
-
http://dx.doi.org/10...
-
show more...
-
https://doi.org/10.1...
-
https://research.cha...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Keyword
- self-stabilization
- shared memory
- fault tolerance
- wait-free constructions
- distributed computing
Publication and Content Type
- art (subject category)
- ref (subject category)
Find in a library
To the university's database