ON THE COMPUTATIONAL POWER OF SELF-STABILIZING SYSTEMS

Authors
ABELLO J DOLEV S
Citation
J. Abello et S. Dolev, ON THE COMPUTATIONAL POWER OF SELF-STABILIZING SYSTEMS, Theoretical computer science, 182(1-2), 1997, pp. 159-170
Citations number
21
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
182
Issue
1-2
Year of publication
1997
Pages
159 - 170
Database
ISI
SICI code
0304-3975(1997)182:1-2<159:OTCPOS>2.0.ZU;2-B
Abstract
The computational power of self-stabilizing distributed systems is exa mined. Assuming availability of any number of processors, each with (s mall) constant size memory we show that any computable problem can be realized in a self-stabilizing fashion. The result is derived by prese nting a distributed system which tolerates transient faults and simula tes the execution of a Turing machine. The total amount of memory requ ired by the distributed system is equal to the memory used by the Turi ng machine (up to a constant factor).