Self-Stabilization of Wait-Free Shared Memory Objects


Hoepman, Jaap-Henk and Papatriantafilou, Marina and Tsigas, Philippas (2002) Self-Stabilization of Wait-Free Shared Memory Objects. Journal of Parallel and Distributed Computing, 62 (5). pp. 818-842. ISSN 0743-7315

[img] PDF
Restricted to UT campus only
: Request a copy
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.
Item Type:Article
Copyright:© 2002 Elsevier
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 211555