Accession Number : ADA191245

Title :   Compilation of Preprints.

Descriptive Note : Technical rept.

Corporate Author : STANFORD UNIV CA CENTER FOR RELIABLE COMPUTING

Report Date : AUG 1987

Pagination or Media Count : 10

Abstract : In part one of this document a new fault model for temporary failures is presented. This model is motivated and supported by recent experimental studies on a type of temporary failure which cannot be explained by existing models. This new fault is called a Byzantine fault in analogy with the well-known Byzantine Generals Problem in distributed systems. Effects of Byzantine faults on concurrent error checking circuits are discussed. Design techniques to eliminate the effects of Byzantine faults are presented. Part two states one of the major problems in pseudo-exhaustive testing has been the efficient determination of a good circuit segmentation. Two methods of reducing segmentation complexity are presented. The first, Circuit Reduction for Efficient Segmentation (CRES), consists of techniques that reduce a circuit to a smaller circuit that is equivalent under segmentation, as well as heuristic techniques that reduce the circuit complexity further while removing undesirable segmentation points. This smaller, less complex circuit can be used as input to any segmentation algorithm significantly reducing segmentation cost. The results can then be translated into a segmentation of the original circuit. The second method reducing the complexity of segmentation is the use of the maximal fanout-free regions of the circuit as an efficient initial segmentation. These techniques can be used together yielding even greater complexity reductions.

Descriptors :   *ALGORITHMS, *CIRCUITS, *FAULTS, *HEURISTIC METHODS, *REDUCTION, COSTS, DETERMINATION, DISTRIBUTION, EFFICIENCY, EXPERIMENTAL DATA, MODELS, SEGMENTED.

Subject Categories : Electrical and Electronic Equipment
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE