Title :
Gracefully degradable pipeline networks
Author :
Cypher, Robert ; Laing, Ambrose K.
Author_Institution :
Dept. of Comput. Sci., Johns Hopkins Univ., Baltimore, MD, USA
Abstract :
A pipeline is a linear array of processors with an input node at one end and an output node at the other end. This paper presents k-gracefully-degradable graphs which, given any set of up to k faults, contain a pipeline that uses all the healthy processor nodes. Our constructions are designed to tolerate faulty input and output nodes, but they can be adapted to provide solutions when the input and output nodes are guaranteed to be healthy. All of our constructions are optimal in terms of the number of nodes and the maximum degree of the processor nodes
Keywords :
fault tolerant computing; graph theory; multiprocessor interconnection networks; faulty input nodes; faulty output nodes; gracefully degradable pipeline networks; input node; k-gracefully-degradable graphs; linear array of processors; processor nodes; Circuit faults; Computed tomography; Computer science; Degradation; Digital communication; Fault tolerance; Finite impulse response filter; IIR filters; Multiprocessor interconnection networks; Pipelines;
Conference_Titel :
Parallel Processing Symposium, 1997. Proceedings., 11th International
Conference_Location :
Genva
Print_ISBN :
0-8186-7793-7
DOI :
10.1109/IPPS.1997.580847
