Properties of c-Correctability in Self-Diagnosing Systems
Abstract
We propose a distributed disabling algorithm for a multiprocessing system in which each processor or unit is prevented from doing computation when it fails some number of tests by other units. The goal is to disable all faulty units and to enable all fault-free units. Specifically, a unit is disabled iff it fails d or more tests by enabled units (d-disabling rule). A multiprocessor system is c-correctable using the disabling rue iff all faulty units are permanently disabled and all fault-free units are permanently enabled after a finite number of applications of the disabling rule, provided there are no more than c faulty units. This models an unattended system where the removal of faulty units is done locally by simple and reliable circuitry. We give a sufficient condition for c-correctability in general systems and a necessary and sufficient condition in general systems where c is less than d. Then, we give necessary and sufficient conditions for c-correctability of two types of systems, (1) complete digraphs and (2) a new class of systems called segmented systems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1988
- Accession Number
- ADA605418
Entities
People
- Jon T. Butler
- Yonina Rosen
Organizations
- Naval Postgraduate School