Self-stabilization of wait-free shared memory objects

This paper proposes a general denition of self-stabilizing wait-free shared memory objects. The denition ensures that, even in the face of processor failures, every execution after a transient memory failure is linearisable except for a bounded number of actions. Shared registers have been used extensively as communication medium in self-stabilizing protocols. We give particular attention to the self-stabilizing implementation of such reg-isters, thus providing a large body of previous research with a more solid fundament. 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 inter-process 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.