Title :
Design and analysis of fault-detecting and fault-locating schedules for computation DAGs
Author :
Yajnik, Shalini ; Jha, Niraj K.
Author_Institution :
Dept. of Electr. Eng., Princeton Univ., NJ, USA
Abstract :
The paper investigates issues concerning the construction of fault-detecting and fault-locating schedules for multiprocessor systems. It develops conditions for a schedule to be fault-detecting or fault-locating and further uses these conditions to propose schemes for construction of the schedules. Lower-bounds on the length of the schedules are calculated and for the special case of binary computation trees, it is shown that the schedules meet the lower-bounds in most cases. A method for actual fault diagnosis from the results of the fault-locating schedules for binary computation trees is also proposed
Keywords :
computational complexity; directed graphs; fault tolerant computing; multiprocessing systems; parallel algorithms; scheduling; binary computation trees; computation DAGs; directed acyclic graphs; fault detecting schedules; fault diagnosis; fault-locating schedules; lower-bounds; multiprocessor systems; Contracts; Data flow computing; Fault detection; Fault diagnosis; Fault location; Flow graphs; Multiprocessing systems; Processor scheduling; Redundancy; Testing;
Conference_Titel :
Parallel Processing Symposium, 1992. Proceedings., Sixth International
Conference_Location :
Beverly Hills, CA
Print_ISBN :
0-8186-2672-0
DOI :
10.1109/IPPS.1992.223022
