Loading...
Please wait, while we are loading the content...
Similar Documents
Self-stabilization of wait-free shared memory objects (2002).
| Content Provider | CiteSeerX |
|---|---|
| Author | Hoepman, Jaap-Henk Papatriantafilou, Marina Tsigas, Philippas |
| 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 synchronisation. Based on this hardware, adaptations of well known wait-free implementations of regular and atomic shared registers are proven to be self-stabilizing. Key Words: shared memory, wait-free constructions, self-stabilization, fault tolerance, distributed computing |
| File Format | |
| Publisher Date | 2002-01-01 |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
