๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the computational power of self-stabilizing systems

โœ Scribed by James Abello; Shlomi Dolev

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
859 KB
Volume
182
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

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).

๐Ÿ“œ SIMILAR VOLUMES

Special Issue on Self-Stabilizing Distri
Special Issue on Self-Stabilizing Distributed Systems
โœ Sajal K. Das; Ajoy K. Datta; Vincent Villain ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 70 KB

The feasibility of distributed computing is well proven by the tremendous success of distributed systems in the past two decades. However, advantages of distributed systems and computer networks do not come for free. The design of such systems is quite complex, in part due to unpredictable faults an

On the computational power of context-fr
On the computational power of context-free PC grammar systems
โœ Niculae Mandache ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 132 KB

It is shown that non-returning parallel communicating grammar systems with -free contextfree components can generate any recursively enumerable language. Since it was proven that such systems can be simulated by returning PC grammar systems with context-free components, the result extends to those.

Limits on the computing power of biologi
Limits on the computing power of biological systems
โœ Michael Conrad; Arnon Rosenthal ๐Ÿ“‚ Article ๐Ÿ“… 1981 ๐Ÿ› Springer ๐ŸŒ English โš– 457 KB

The theory of computational complexity and certain explicitly-stated hypotheses imply limitations on the information processing power of biological systems. Parallelism, special purpose organization, and analog mechanisms may provide speedup critical for life processes, but have little power in the

On the computational power of pushdown a
On the computational power of pushdown automata
โœ A.V. Aho; J.D. Ullman; J.E. Hopcroft ๐Ÿ“‚ Article ๐Ÿ“… 1970 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 361 KB

We present a relation between the sets accepted by two-way pushdown automata and certain tape complexity classes of off-line Turing machines. Specifically, let L be a language accepted by a nondeterministic off-line Turing machine T. Let T have a t-symbol storage-tape alphabet. If for all but a fini