Self-stabilizing Automata

摘要

Biological systems are known to be probabilistically self-stabilizing, i.e. with a high probability they can reach a stable state from any initial state. This property is very important to computer-based systems, too. However, building self-stabilizing systems is still very difficult. Proving that any given implementation is in fact self-stabilizing is even harder. Nature has a big advantage: Any living being must eventually die and limited energy limits the harm that an error can have on the system. This greatly simplifies the realization of self-stabilization. To transfer this concept to computer-based systems, we propose to modify the computational model on which software is currently being built. We introduce energy-awareness in Turing Machines (TMs). This will guarantee that any TM program that is correct in the absence of errors is at the same time self-stabilizing in the presence of errors.