日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細


公開

報告書

Towards self-stabilizing wait-free shared memory objects

MPS-Authors
/persons/resource/persons45161

Papatriantafilou,  Marina
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45640

Tsigas,  Philippas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
There are no locators available
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
フルテキスト (公開)

MPI-I-95-1-005.pdf
(全文テキスト(全般)), 43MB

付随資料 (公開)
There is no public supplementary material available
引用

Hoepmann, J.-H., Papatriantafilou, M., & Tsigas, P.(1995). Towards self-stabilizing wait-free shared memory objects (MPI-I-1995-1-005). Saarbrücken: Max-Planck-Institut für Informatik.


引用: https://hdl.handle.net/11858/00-001M-0000-0014-A762-D
要旨
Past research on fault tolerant distributed systems has focussed on either processor failures, ranging from benign crash failures to the malicious byzantine failure types, or on transient memory failures, which can suddenly corrupt the state of the system. An interesting question in the theory of distributed computing is whether one can device highly fault tolerant protocols which can tolerate both processor failures as well as transient errors. To answer this question we consider the construction of self-stabilizing wait-free shared memory objects. These objects occur naturally in distributed systems in which both processors and memory may be faulty. Our contribution in this paper is threefold. First, we propose a general definition of a self-stabilizing wait-free shared memory object that expresses safety guarantees even in the face of processor failures. Second, we show that within this framework one cannot construct a self-stabilizing single-reader single-writer regular bit from single-reader single-writer safe bits. This result leads us to postulate a self-stabilizing {\footnotesize\it dual\/}-reader single-writer safe bit with which, as a third contribution, we construct self-stabilizing regular and atomic registers.