A kappa-out-of-n : G system consists of a set of components, where each component is either faulty or fault-free.
The system is working if at least kappa components are fault-free.
The problem of finding an optimal diagnosis procedure for a given kappa-out-of-n : G system has been considered in several research fields including medical diagnosis, redundant-system testing, and searching data-files.
A polynomial-time algorithm for this problem was presented first by Salloum, and latter by Salloum & Breuer, and independently by Ben-Dov.
This paper implements the Salloum-Breuer-Ben-Dov algorithm, leading to an optimal diagnosis procedure that can determine the state of any given system in O (n. log (n)) time complexity and O (n) space complexity.
The efficiency is achieved by using a generalized radix sorting procedure that uses a heap data structure.
For some kappa-out-of-n : G systems, including those with equal testing costs for all components, the components along the leftmost & rightmost paths in the optimal diagnostic tree uniquely determine the other components in the tree.
This property is used to devise a faster optimal diagnosis procedure than the one for the general kappa-out-of-n : G system.
With regard to complexity, these procedures are the best solutions for the problem under consideration.
This conjecture is supported by the fact that all these procedures require a sorting operation which has O (n. log (n)) as a lower bound on its time complexity.
Mots-clés Pascal : Diagnostic, Application médicale, Système redondant, Système k parmi n, Fiabilité, Arbre binaire, Essai, Multiprocesseur
Mots-clés Pascal anglais : Diagnosis, Medical application, Redundant system, K out of n system, Reliability, Binary tree, Test, Multiprocessor
Notice produite par :
Inist-CNRS - Institut de l'Information Scientifique et Technique
Cote : 97-0410296
Code Inist : 002B30A01A1. Création : 19/12/1997.