CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Self-Stabilization in Wait-Free Shared Memory Objects

Jaap-Henk Hoepman ; Marina Papatriantafilou (Institutionen för datavetenskap, Datakommunikation och Distribuerade System) ; Philippas Tsigas (Institutionen för datavetenskap, Datakommunikation och Distribuerade System)
Journal of Parallel and Distributed Computing (0743-7315). Vol. 62 (2002), 5, p. 818-842.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: shared memory, wait-free constructions, self-stabilization, fault tolerance, distributed computing

Denna post skapades 2006-08-25. Senast ändrad 2013-02-14.
CPL Pubid: 1591


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, Datakommunikation och Distribuerade System (2002-2004)


Information Technology

Chalmers infrastruktur