Table of contents
1 Turing Machine with faults, failures and recovery

Turing Machine with faults, failures and recovery


In contrast to practical situation an ordinary Turing Machine never fails.
Turing Machine with faults, failures and recovery is (weakly) non-deterministic Turing Machine consisting of :
  • five semi-infinite (to the right) tapes
    • Master Tape,
    • Synchro Tape,
    • Backup Tape,
    • Backup Synchro Tape,
    • User (Tester) Tape;
  • four controlling components (sets of rules)
    • Program,
    • Daemon,
    • Apparatus,
    • User.
Only daemon has non-deterministic behavior.

Tapes, alphabets

Master Tape corresponds to the tape of ordinary deterministic Turing Machine.
Head of Synchro Tape is synchronized with head of Master Tape.
Backup Tape is used to back Master Tape data up.
Backup Synchro Tape is used to back Synchro Tape data up.
User Tape is used to perform pure/ideal computation (without faults and failures).

Master Tape, Backup Tape, User Tape are using the same (user-defined) alphabet.
Synchro Tape, Backup Synchro Tape are using the same special (embedded, user-independent) alphabet.

States

Program contains :
- user-defined states (initial, internal and halting states),
- user-required check-point states (indirectly defined by user),
- embedded (user-independent) shutting down state.
Note 1. Some of user-defined rules an user may mark as check-points.
Check-point states are derived from these rules.
Note 2. Shutting down state differs from user-defined halting state.

Daemon contains three embedded (user-independent) states :
- passive,
- active,
- aggressive.

Apparatus contains two embedded (user-independent) states :
- normal,
- emergency.

User contains two embedded (user-independent) states :
- tracking,
- stabilizing.

Rules

There are three sets of rules :
a) Daemon's set of non-deterministic rules.
The set includes only daemon states.
b) Common set of deterministic rules
The set includes states of all controlling components (program, daemon, apparatus, user).
In fact, this common set consists of two subsets :
- program rules including
  • user-defined rules,
  • user-required check-point rules;
- outside rules including
  • deterministic daemon rules,
  • apparatus rules,
  • user rules.
c) Daemon-defined set of rules (fault rules).

Transitions

Each transition step consists of two half-steps (tacts) :
a) First tact. Daemon performs transition according to non-deterministic rule
from passive state to {passive, active, aggressive }
b) Second tact. One of three kinds of transitions is performed :
- normal transition, if daemon is in passive state,
- fault transition, if daemon is in active state,
- failure transition, if daemon is in aggressive state.
Note. On second tact daemon always goes into passive state.

Faults and failures

The difference between fault and failure is as follows.
- Fault transition :
  • apparatus stay in normal state.
  • illegal (daemon-defined) program rule is applied,
and the program continues computation.
- Failure transition :
  • apparatus go into in emergency state.
  • the program is unable to continue computation.

External link

http://alexvn.freeservers.com/s1/turing-s.html