On the computational power of self-stabilizing systems

James Abello Monedero, Shlomi Dolev

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

The computational power of self-stabilizing distributed systems is examined. Assuming availability of any number of processors, each with (small) constant size memory we show that any computable problem can be realized in a self-stabilizing fashion. The result is derived by presenting a distributed system which tolerates transient faults and simulates the execution of a Turing machine. The total amount of memory required by the distributed system is equal to the memory used by the Turing machine (up to a constant factor).

Original languageEnglish (US)
Pages (from-to)159-170
Number of pages12
JournalTheoretical Computer Science
Volume182
Issue number1-2
DOIs
StatePublished - Aug 15 1997
Externally publishedYes

Fingerprint

Turing machines
Distributed Systems
Turing Machine
Data storage equipment
Transient Faults
Computer systems
Availability

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

@article{6ea07f23f81749aeb95872f241dcb0ec,
title = "On the computational power of self-stabilizing systems",
abstract = "The computational power of self-stabilizing distributed systems is examined. Assuming availability of any number of processors, each with (small) constant size memory we show that any computable problem can be realized in a self-stabilizing fashion. The result is derived by presenting a distributed system which tolerates transient faults and simulates the execution of a Turing machine. The total amount of memory required by the distributed system is equal to the memory used by the Turing machine (up to a constant factor).",
author = "{Abello Monedero}, James and Shlomi Dolev",
year = "1997",
month = "8",
day = "15",
doi = "https://doi.org/10.1016/S0304-3975(96)00150-8",
language = "English (US)",
volume = "182",
pages = "159--170",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "1-2",

}

On the computational power of self-stabilizing systems. / Abello Monedero, James; Dolev, Shlomi.

In: Theoretical Computer Science, Vol. 182, No. 1-2, 15.08.1997, p. 159-170.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the computational power of self-stabilizing systems

AU - Abello Monedero, James

AU - Dolev, Shlomi

PY - 1997/8/15

Y1 - 1997/8/15

N2 - The computational power of self-stabilizing distributed systems is examined. Assuming availability of any number of processors, each with (small) constant size memory we show that any computable problem can be realized in a self-stabilizing fashion. The result is derived by presenting a distributed system which tolerates transient faults and simulates the execution of a Turing machine. The total amount of memory required by the distributed system is equal to the memory used by the Turing machine (up to a constant factor).

AB - The computational power of self-stabilizing distributed systems is examined. Assuming availability of any number of processors, each with (small) constant size memory we show that any computable problem can be realized in a self-stabilizing fashion. The result is derived by presenting a distributed system which tolerates transient faults and simulates the execution of a Turing machine. The total amount of memory required by the distributed system is equal to the memory used by the Turing machine (up to a constant factor).

UR - http://www.scopus.com/inward/record.url?scp=0031210524&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031210524&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/S0304-3975(96)00150-8

DO - https://doi.org/10.1016/S0304-3975(96)00150-8

M3 - Article

VL - 182

SP - 159

EP - 170

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-2

ER -